[Python-ideas] Add the imath module

[Tim Peters]

[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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20180715/5ad9aa4c/attachment.html>