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 <20200505105859.GD16433@ando.pearwood.info>
In-reply-to <1588672402.9.0.793846038994.issue40028@roundup.psfhosted.org>
Content
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.

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases
History
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