(gmp.info.gz) Prime Testing Algorithm
Info Catalog
(gmp.info.gz) Other Algorithms
(gmp.info.gz) Other Algorithms
(gmp.info.gz) Factorial Algorithm
Prime Testing
-------------
Functions::) first does some trial division by small factors and then
uses the Miller-Rabin probabilistic primality testing algorithm, as
described in Knuth section 4.5.4 algorithm P ( References).
For an odd input n, and with n = q*2^k+1 where q is odd, this
algorithm selects a random base x and tests whether x^q mod n is 1 or
-1, or an x^(q*2^j) mod n is 1, for 1<=j<=k. If so then n is probably
prime, if not then n is definitely composite.
Any prime n will pass the test, but some composites do too. Such
composites are known as strong pseudoprimes to base x. No n is a
strong pseudoprime to more than 1/4 of all bases (see Knuth exercise
22), hence with x chosen at random there's no more than a 1/4 chance a
"probable prime" will in fact be composite.
In fact strong pseudoprimes are quite rare, making the test much more
powerful than this analysis would suggest, but 1/4 is all that's proven
for an arbitrary n.
Info Catalog
(gmp.info.gz) Other Algorithms
(gmp.info.gz) Other Algorithms
(gmp.info.gz) Factorial Algorithm
automatically generated byinfo2html