Prime factor

The factoring integers is a task from the mathematical branch of number theory. Goal is to identify a composite number is a non-trivial divisor. For example, given the number 91, so look for it a number like 7, which shares 91. Corresponding algorithms accomplish this is referred to as factorization. By recursive application of factorization in combination with primality testing the prime factorization of a whole number can be calculated.

To date, no factorization is known, calculate the nontrivial divisor and thus the prime factorization of a number efficiently. This means that an enormous computational effort required to factorize a number of several hundred spots. This difficulty is exploited in cryptography. The security of encryption, such as the RSA cryptosystem based on the fact that the factorization of the RSA modulus to decrypt communication is difficult; thus an efficient factorization would result in breaking the RSA method. It is conceivable, however, that one can solve the RSA problem more efficiently than the factoring problem. However, no such method is known so far.

In theoretical computer science problems in complexity classes are divided, which provide information as how much effort requires the solution of a problem. When factoring integers is not known which complexity class it belongs: Although it is known that the problem (in its decision version) is in the class NP, but not known whether it is solvable in polynomial time already. That is, it can not be excluded on the current state of knowledge that at some point, an algorithm is discovered, the integers can be factored with a reasonable effort.

The best known algorithms are in 1981, invented by Carl Pomerance Quadratic sieve, the number field sieve around 1990 by several mathematicians (including John M. Pollard, Arjen Lenstra, Hendrik Lenstra Jr., Mark S. Manasse, Carl Pomerance ) jointly developed and the method of elliptic curves, which was founded in 1987, presented by Hendrik W. Lenstra Jr..

The RSA Factoring Challenge pursued until its suspension in 2007, the current state of research in the field of factorization. This resulted in evidence of the necessary size of the related RSA cryptosystem Semi primes.

In practice, one is to factor a number, proceed as follows:

The first two steps are reversed here occasionally.

• 2.1 factorisation of antiquity
• 2.2 17th to 19th century
• 2.3 20th century, before the introduction of computers
• 2.4 20th century, after the introduction of computers
• 2.5 21st century

Overview of the factorization

Below we always called a composite number for which a divider to be determined.

Trial division

The simplest method for determining a divisor of the sample division. This is divided by all prime numbers, starting with the two until a prime number as the divisor or proves to the Probedivisor greater than. The procedure is very time-consuming, but is well suited for the determination of small prime factors.

Computing the greatest common divisor

The trial division can be extended by the Euclidean algorithm or other method for finding the greatest common divisor so that you can find all the prime factors of a certain interval. For this use is the product of all primes of the interval and calculates the greatest common divisor of two numbers. This is the product of prime factors that originate from the selected interval, and you can recover the individual prime factors of it. The advantage of this method is that the sample is then Division only needs to apply to the ratio, as is much smaller.

Factorization of Fermat

One method that is particularly well suited to find divider near, the factorization method of Fermat. This algorithm works only for odd and utilizes the fact that they can be represented as a difference of two square numbers. It first calculates the smallest integer that is greater than or equal. The algorithm then calculates the differences ... until one of these differences is a square number. From this subgroup of can be calculated.

Other methods

• Factorization of Lehman
• Continued fraction method
• Pollard p- 1 method
• Pollard -p 1 method
• Pollard 's rho method
• Dixon's factorization method (random squares method)
• Method of the class groups of Daniel Shanks, with variants of Martin Seysen ( classgroup relations method) and Lenstra / Schnorr (random class groups method)
• SQUFOF, square form factorization of Shanks
• Quadratic sieve
• Number field sieve
• Method of elliptic curves
• Schnorr's grid -based factorization

Shor algorithm

A special position among the Shor factorization takes the algorithm. He can not run on classical computers, but requires a quantum computer. On this however, it can be calculated in polynomial time by a factor of. However, no quantum computers can be built, which have sufficient for the factorization of large numbers register size. The function of the Shor algorithm is based on determining the order of an element of prime residue class group using the quantum Fourier transform. After the announcement of the Shor algorithm developed physicist technical systems and experimental setups that allow the classical way, without superposition of quantum states, the factorization of natural numbers. These include, for example, nuclear magnetic resonance, cold atoms, ultrashort light pulses and multipath interferometry.

History

Factorization of antiquity

Since Euclid of Alexandria about 300 years before Christ, in his major work, the elements, the fundamental theorem of arithmetic had stated and proved, it was known that every natural number has a unique prime factorization. Using the method of trial division, which was known also essentially already Euclid, had very early discovered a method to determine this; although it is not suitable for larger numbers because then takes too much time.

17th to 19th century

In 1643, Pierre de Fermat described in a letter ( the addressee is not known, probably Marin Mersenne or Frénicle Bernard de Bessy ) the named after him today factorization method of Fermat which is based on that one represents the number to be factored as a difference of two squares. This method, which is the amount of time rather worse than the trial division, forms the basis for almost all modern factorization.

20th century, before the introduction of computers

1926 Maurice Kraitchik published a paper in which he suggests some improvements to the factorization method of Fermat. In particular, he considered the next to be factored number n and its multiples, in other words, he is looking for a congruence of the form x2 ≡ y2 (mod n ). To find them, he multiplied suitable congruences of the form x2 ≡ y ( mod n), which can be easily and effectively (as described in Article quadratic sieve ).

Derrick Henry Lehmer and Ralph Ernest Powers proposed in 1931 the so-called continued fraction method to find congruences of the form x2 ≡ y ( mod n).

20th century, after the introduction of computers

With the introduction of computers, the intensive study of factorization began. Building on the idea of Lehmer and Powers developed John Brillhart in the sixties, a work based on linear algebra over the finite field F2 method in order to select from a list of congruences of the form x2 ≡ y ( mod n) can appropriate. Together with Michael Morrison him thus succeeded in 1975, the factorization of the for those times extremely large 39 - digit Fermat number F7. In particular it was thus for the first time succeeded in finding a factorization with sub-exponential running time.

Inspired by the linear sieve by Richard Schroeppel could reach in 1981 an acceleration of the process by introducing a screening process in place of the trial division used to date Carl Pomerance. Since the screening process was not suitable for the continued fraction method, Pomerance went back over to the method originally proposed by Kraitchik. In this way it was possible to factor numbers up to 100 points; in particular, succeeded in 1994 in order to dismantle the 129- digit number RSA -129. This technique, known as the quadratic sieve method is still the fastest known method for factoring numbers with less than 100 points.

In the eighties, it was assumed that the methods, which are based on the idea of Kraitchik can not be substantially faster than the quadratic sieve. This assumption was supported by the fact that there were now a number of methods with similar maturities, and. By a result from analytic number theory over smooth numbers

Beginning of the nineties, this assumption was impressively refuted by the number field sieve. The number field sieve was proposed in 1988 by John Pollard for specific numbers and then by a number of mathematicians ( among others John Pollard, Arjen Lenstra, Hendrik Lenstra, Jr., Mark Manasse, Carl Pomerance, Joe Buhler, Len Adlemann ) changed so that it was applicable for arbitrary numbers. Due to the transition to algebraic number fields, it was possible to keep the numbers used during the computation significantly smaller and thus to achieve the mentioned acceleration. In particular, it succeeded in 1990, the complete factorization of the 155- digit Fermat number F9.

21st Century

With the mesh screen (one proposed by Pollard variant of Zahlkörpersiebs ) and other methods 2005, the factorization of the biggest composite of two large prime number was ( a so-called almost-prime ) completed without special structure after two years of work on a computer pool. This is the number RSA - 200, a 200 - digit decimal number that was generated jointly with other semi primes in the RSA Factoring Challenge.

In 2012, a group factorized by 500 participants in the BOINC project NFS @ Home is a number with 211 decimal digits and thus deciphered a secret message which was provided by Donald Knuth in the book The Art of Computer Programming as the time impossible task in 1997. Knuth replaced then the problem using a semi prime number with 318 decimal digits.

Implementations

The ARIBAS program by Otto Forster implements several of the methods discussed here - either as part of the run -time library, or as a supplement to the author's book on Algorithmic number theory.