11Y05: Factorization and primality testing
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.
See also 11-04
Parent field: 11Y: Computational number theory.
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.
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.
Several techniques are available for factoring large integers quickly.
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).
A few other files on factoring:
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.
Some odds and ends in this section: