Message368128
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 |
|
Date |
User |
Action |
Args |
2020-05-05 11:03:31 | steven.daprano | set | recipients:
+ steven.daprano, tim.peters, rhettinger, mark.dickinson, serhiy.storchaka, remi.lapeyre, jfine2358, trrhodes |
2020-05-05 11:03:31 | steven.daprano | link | issue40028 messages |
2020-05-05 11:03:31 | steven.daprano | create | |
|