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 _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
