Steven D'Aprano <steve+pyt...@pearwood.info> added the comment:
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 ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue40028> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
