Integer factorization

related topics
{math, number, function}
{game, team, player}
{work, book, publish}
{day, year, event}
{math, energy, light}

In number theory, integer factorization or prime factorization is the breaking down of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer.

When the numbers are very large, no efficient integer factorization algorithm is publicly known; an effort concluded in 2009 by several researchers factored a 232-digit number (RSA-768) utilizing hundreds of machines over a span of 2 years.[1] The presumed difficulty of this problem is at the heart of certain algorithms in cryptography such as RSA. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing.

Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers. When they are both large, randomly chosen, and about the same size (but not too close), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical.

Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem, the RSA problem. An algorithm which efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure.

Contents

Prime decomposition

By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. (A special case for 1 is not needed using an appropriate notion of the empty product.) However, the fundamental theorem of arithmetic gives no insight into how to obtain an integer's prime factorization; it only guarantees its existence.

Given an algorithm for integer factorization, one can factor any integer down to its constituent prime factors by repeated application of this algorithm.

Current state of the art

Full article ▸

related documents
Expander graph
LL parser
Algebraically closed field
Even and odd permutations
Stokes' theorem
Cauchy's integral formula
Topology
Associative array
Line integral
Document Type Definition
Morphism
Parameter
Yoneda lemma
Stone–Weierstrass theorem
Positive-definite matrix
Optimization (mathematics)
Boolean algebra (structure)
Henri Lebesgue
Finite difference
Solvable group
Hypercomplex number
Liouville number
Banach space
Universal quantification
Haskell (programming language)
A* search algorithm
Power set
B-spline
Topological vector space
Free group