This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author steven.daprano
Recipients jfine2358, mark.dickinson, remi.lapeyre, rhettinger, serhiy.storchaka, steven.daprano, tim.peters, trrhodes
Date 2020-05-05.11:03:31
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
In-reply-to <>
Miller-Rabin is known to be deterministic for all N < 2**64 too.

To be pedantic, M-R is known to be deterministic if you check every 
value up to sqrt(N), or possibly 2*log(N) if the generalized Riemann 
hypothesis is true. The question is whether there is a smaller set of 
values that is sufficient to make M-R deterministic, and that has been 
proven for N up to 2**64.

Wikipedia has more details including some small sets of bases which are 
deterministic. There may be even smaller sets, but for N < 2**64, just 
12 M-R tests with the following set of bases is sufficient to give a 
deterministic result:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.
Date User Action Args
2020-05-05 11:03:31steven.dapranosetrecipients: + steven.daprano, tim.peters, rhettinger, mark.dickinson, serhiy.storchaka, remi.lapeyre, jfine2358, trrhodes
2020-05-05 11:03:31steven.dapranolinkissue40028 messages
2020-05-05 11:03:31steven.dapranocreate