Primality and Factorization

• Probabilistic primality testing (Miller-Rabin)
• Rigorous primality testing (Morain's Elliptic Curve Primality Prover)
• Primality certificates; Verification of certificates
• Generation of primes
• Elementary factorization techniques: Trial division, SQUFOF, Pollard $\rho$, Pollard p-1
• Elliptic curve method for integer factorization (A. Lenstra)
• Multiple prime multiple polynomial quadratic sieve algorithm for integer factorization (A. Lenstra)
• Database of factorizations of integers of the form $p^n \pm 1$

The Elliptic Curve Primality Prover (ECPP) designed and implemented by François Morain at INRIA is installed in Magma. This provides fast rigorous primality proofs for integers having several hundred digits. The primality of a 100 digit integer is established in 24 seconds (on a Sun 200Mhz SPARC workstation 2).