[The Mathematical Atlas] [Search][Subject Index][MathMap][Tour][Help!]
[MathMap Icon]
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

Selected topics at this site

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/primality testing:

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:


You can reach this page through http://www.math-atlas.org/welcome.html
Last modified 2000/01/14 by Dave Rusin. Mail: