§27.22 Software

In this section we provide links to the known sources of software for factorization and primality testing, as well as additional Web-based resources for information on these topics.

• Maple. isprime combines a strong pseudoprime test and a Lucas pseudoprime test. ifactor uses cfrac (§27.19) after exhausting trial division. Brent–Pollard rho, Square Forms Factorization, and ecm are available also; see §27.19.

• Mathematica. PrimeQ combines strong pseudoprime tests for the bases 2 and 3 and a Lucas pseudoprime test. No known composite numbers pass these three tests, and Bleichenbacher (1996) has shown that this combination of tests proves primality for integers below . Provable PrimeQ uses the Atkin–Goldwasser–Kilian–Morain Elliptic Curve Method to prove primality. FactorInteger tries Brent–Pollard rho, Pollard , and then cfrac after trial division. See §27.19. ecm is available also, and the Multiple Polynomial Quadratic sieve is expected in a future release.

  For additional Mathematica routines for factorization and primality testing, including several different pseudoprime tests, see Bressoud and Wagon (2000).

• Cunningham Project. This includes updates of factorization records.

• ECMNET Project. Links to software for elliptic curve methods of factorization and primality testing.

• GIMPS. This includes updates of the largest known Mersenne prime.

• Number Theory Web. References and links to software for factorization and primality testing.

• Prime Pages. Information on primes, primality testing, and factorization including links to programs and lists of primes.

• Wolfram’s Mathworld. Descriptions, references, and Mathematica algorithms for factorization and primality testing.