[Search][Subject Index][MathMap][Tour][Help!]

	ABOUT: [Introduction][History][Related areas][Subfields] POINTERS: [Texts][Software][Web links][Selected topics here] 11Y05: Factorization and primality testing

Introduction

The simple task of decomposing an integer into its prime factors is hard. This is the topic under discussion here. Naturally this is related to number theory, and when we replace the ring of integers with more general rings, (in particular rings of polynomials) we are in the realm of commutative rings. For some of the questions at hand, it is important to understand elliptic curves. One important application is to the field of cryptography.

History

Applications and related fields

See also 11-04

Subfields

Parent field: 11Y: Computational number theory.

Textbooks, reference works, and tutorials

Software and tables

Factorizations of b^n +- 1 (The Cunningham project). (Consult the other sister directories there for factorizations of other numbers, large primes, etc.) A U.S. site maintained by Sam Wagstaff also carries tables of Fermat (2^N+1) and other numbers with factors and/or primality information, although that site seems to be frequently unavailable.

Yves Gallot: Proth's Theorem for Win95 (Factoring Mersenne numbers)

There is an online primality-verifier which uses the Elliptic Curve primality test.

Likewise an online factorer.

Other web sites with this focus

• One of the pages devoted to Mersenne primes etc.

Selected topics at this site

Several techniques are available for factoring large integers quickly.

• Survey of techniques and literature on integer factorization
• An older summary of factorization techniques (with citations to the literature).
• Coding advice for fast integer factorization (and GCD calculation)
• What is the Pollard "rho" method of integer factorization?
• Detailed descriptions of the elliptic curve method.
• A free implementation of the Elliptic Curve method of factorization.
• Citations for the number field sieve
• Sources and background: the Number Field Sieve for factoring.
• What is MPQS (Multiple Polynomial Quadratic Sieve factorization technique)
• Citation for PPMPQS (including its use in factoring RSA 129 -- see below).
• An offbeat technique (still theoretical) is the use of quantum computing.

Several large-scale factoring projects involving many machines and many people.

There is a list of current Most-wanted composites of many common types (Cunningham numbers, partition numbers, etc.) along with software and some background information. This is perhaps the easiest up-to-date source for data about which numbers have been factored; begin here if you wish to contribute some CPU cycles for factorization. (Be warned that the tables of "interesting" composites whose factorization is desired begins at about 120 decimal digits).

• Ongoing computer search for Mersenne primes (pointers and Call For Participation).
• RSA129 was a certain 129-digit number containing a coded message (as a test). Here is a call for participants, which resulted in a completed factorization.
• The factorization of RSA129.
• technical discussion of factorization of RSA129.
• Summary of the Cunningham project (to factor many numbers of the forms b^m +- 1).
• Submitting new progress for the Cunningham project
• Description of the NFSNET network of number-factorers, and a progress report on one of the Cunningham numbers.
• Historical pointer to a factor by mail project.
• Cunningham tables as of May, 2001
• Press release describing factorization of RSA-140

A few other files on factoring/primality testing:

• Proth's primality theorem and candidate primes generalizing the Fermat primes
• Pratt's theorem: Certificates which verify primality in polynomial time
• Long arithmetic progressions consisting only of (consecutive) primes
• Aurifeuillian factorizations of sums of powers
• What are the expected run-times of the principal factoring routines?
• Best known time estimates for integer factorization
• Citation for textbook (Bressoud) on factorization and primality testing.
• Pointer to lecture notes on factoring and primality testing
• Logical complexity of prime factorization (NP)
• An example using Pari to factor.
• Sample factorization output using MIRACL program
• Some pointers to factorization code
• Factor n, n-1, n+1 where n is the order of the Monster finite simple group.
• Some primes dividing 1 + googolplex (10^(10^100))
• Pointer: status of (double-)Mersenne numbers
• Factoring as a lifesaving activity!

A related question is that of primality testing. Note that this is in principle (and -- so far -- in practice) easier than determining the factors of a number shown to be composite.

• review of primality testing routines in commercial systems
• detailed summary of primality testing routines
• There are also deterministic (non-probabilistic) primality tests.
• A short discussion of the state of the art of primality testing.
• Pointer to Richard Pinch survey of primality proving techniques.
• Rapid tests for primality (e.g. Miller-Rabin)
• Polynomial tests for primality.
• Fast verification of primality from a certificate
• Pointer: primality proving program.
• Elliptic curve primality testing.
• What is the Elliptic Curve Primality Prover and how does one get it?
• The APR-CL primality test
• How does Mathematica determine primality?
• Current (Oct. 1997) record in primality proving (2196 digits)
• Fastest methods of primality proving?
• Some references on primality proving
• How about fast primality checks for smallish numbers?
• Fast primality testing through 16 000 000.
• Using (extensions of) Fermat's Little Theorem to generate large prime numbers (and prove they're prime)
• (Pointless) primality tests using Chebyshev polynomials

Some odds and ends in this section:

• How efficiently can we test an integer to be square-free?
• Factoring N efficiently given a factorization of (Euler) phi(N)
• How hard is it to compute the values of the Euler phi function