[Python-ideas] Add the imath module
tim.peters at gmail.com
Sun Jul 15 02:27:40 EDT 2018
> 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
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:
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-ideas