[Python-ideas] Add the imath module

[Steven D'Aprano]

On Thu, Jul 12, 2018 at 05:35:54PM -0500, Tim Peters wrote:
> [David Mertz]
> 
> > Miller-Rabin or other pseudo-primality tests do not produce false
> > negatives IIUC.
> >
> 
> That's true if they're properly implemented ;-)  If they say False, the
> input is certainly composite (but there isn't a clue as to what a factor
> may be); if the say True, the input is "probably" a prime.

I'm sure Tim knows this, but that's only sometimes true. Since I had no 
formal education on primality testing and had to pick this up in dribs 
and drabs over many years, I was under the impression for the longest 
time that Miller-Rabin was always probabilitistic, but that's not quite 
right.

Without going into the gory details, it turns out that for any N, you 
can do a brute-force primality test by checking against *every* 
candidate up to some maximum value. (Which is how trial division works, 
only Miller-Rabin tests are more expensive than a single division.) Such 
an exhaustive check is not practical, hence the need to fall back on 
randomly choosing candidates.

However, that's in the most general case. At least for small enough N, 
there are rather small sets of candidates which give a completely 
deterministic and conclusive result. For N <= 2**64, it never requires 
more than 12 Miller-Rabin tests to give a conclusive answer, and for 
some N, as few as a single test is enough.

To be clear, these are specially chosen tests, not random tests.

So in a good implementation, for N up to 2**64, there is never a need 
for a "probably prime" result. It either is, or isn't prime, and there's 
no question which.

In principle, there could be similar small sets of conclusive tests for 
larger N too, but (as far as I know) nobody has discovered them yet. 
Hence we fall back on choosing Miller-Rabin tests at random. The chances 
of an arbitrary composite number passing k such tests is on average 
1/4**k, so we can make the average probability of failure as small as we 
like, by doing more tests. With a dozen or twenty tests, the probability 
of a false positive (a composite number wrongly reported as prime) is of 
the same order of magnitude as that of a passing cosmic ray flipping a 
bit in memory and causing the wrong answer to appear.



-- 
Steve