[Steve Barnes] > Looking for some information on how long it has taken to generate large > primes I stumbled across > https://arxiv.org/ftp/arxiv/papers/1709/1709.09963.pdf which makes > interesting reading. It concentrates on giving no false negatives (never > saying n is not a prime when it is) but giving an increasing probability > that n is a prime as testing goes on. >
That's a very nice, gentle introduction! Thanks for sharing it. The `pp()` function I posted before is a Python implementation of the Miller-Rabin test they ended with. The latter is very widely used, because the code is relatively simple. short, and fast, and has no "bad cases". For _generating_ primes, the article uses other tricks to weed out sure-to-be-composite candidates before bothering with probable-prime testing. But the tricks they use in the paper are specific to a base 10 representation. In binary, it's common to skip candidates such that gcd(candidate, 2 * 3 * 5 * ...) > 1 where the product-of-small-primes second argument is picked to be the largest such that bigint division by it is exceptionally fast (usually one "digit" in whatever internal power-of-2 base is used by the bigint implementation). I did find an article from 2016 that mentioned M77232917 (a 23,249,425 > digit Mersenne prime) and M74207281 (22,338,618 digit Mersenne prime) > with the latter taking a month to check with the Lucas-Lehmer test. > More, it's a special version of Lucas-Lehmer (LL) that only works for testing candidates of the form 2**p-1 where p is itself an odd prime. In that context, it's not probabilistic - it definitively answers whether 2**p-1 is prime. Fast as it is, Miller-Rabin is impractical for guessing about numbers of this size. And as enormously faster as _it_ is, the special version of LL used for Mersenne testing is largely hand-coded in assembler to squeeze out every possible machine cycle. I don't want any of that in Python's standard library either ;-) Here! You should enjoy this account of the even larger Mersenne prime discovered this year: https://www.mersenne.org/primes/press/M77232917.html Note that the hyper-optimized testing code they use is so historically error-prone (& so good at provoking HW errors on overheated machines!) that they now verify each new Mersenne prime by 4 entirely different LL implementations, on 4 different machines.
_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/