Digital Library of Mathematical Functions
About the Project
NIST
27 Functions of Number TheoryComputation

§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 cfrac27.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 1016. Provable PrimeQ uses the Atkin–Goldwasser–Kilian–Morain Elliptic Curve Method to prove primality. FactorInteger tries Brent–Pollard rho, Pollard p-1, 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.