(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