Factorization method
The factorization problem for whole numbers is a task from the mathematical branch of number theory . The aim is to composite number one nontrivial divisor be determined. For example, given the number 91, look for a number like 7 that divides 91. Corresponding algorithms that accomplish this are called factorization methods . The prime factorization of an integer can be calculated through the recursive application of factoring methods in combination with primality tests .
To date, there is no known factorization method that efficiently calculates nontrivial divisors and thus the prime factorization of a number . This means that an enormous amount of computational effort is required to factor a number with several hundred digits. This difficulty is exploited in cryptography . The security of encryption methods like the RSA cryptosystem is based on the fact that it is difficult to factorise the RSA module to decrypt the messages; thus an efficient factorization method would break the RSA method. However, it is conceivable that the RSA problem can be solved more efficiently than the factorization problem. However, no such method is known so far.
In theoretical computer science , problems are divided into complexity classes that provide information about the effort required to solve a problem. In the factoring problem for integers, it is not known which complexity class it belongs to: it is known that the problem (in its decision variant ) lies in the class NP , but it is not known whether it can be solved in polynomial time . This means that, according to the current state of knowledge, it cannot be ruled out that at some point an algorithm will be discovered that can factor whole numbers with manageable effort.
The best known algorithms are the square sieve , invented by Carl Pomerance in 1981 , the number field sieve and the method of the number field sieve jointly developed around 1990 by several mathematicians (including John M. Pollard , Arjen Lenstra , Hendrik Lenstra Jr., Mark S. Manasse , Carl Pomerance) elliptic curves presented by Hendrik W. Lenstra, Jr. in 1987.
The RSA Factoring Challenge followed the current state of research in the field of factoring procedures until it was suspended in 2007. From this evidence showed the necessary size of the RSA cryptosystem related Semi primes .
In practice, to factor a number, one will proceed as follows:
 Find / remove small factors by trial division.
 Use a prime number test to find out whether the number is a prime number or a prime power .
 Search for comparatively small prime factors (<10 ^{30} ) using the elliptic curve method .
 Factor with the square sieve (for numbers with fewer than 120 decimal places) or the number field sieve.
The first two steps are sometimes reversed.
Overview of the factoring methods
In the following always denotes a composite number for which a divisor is to be determined.
Trial division
The easiest way to find a divisor of is to try division . It is divided by all prime numbers beginning with two until a prime number proves to be its divisor or until the trial divisor has become greater than . The procedure is very suitable for determining small prime factors, but it is very timeconsuming to use it to completely decompose a number with two or more large prime factors.
Calculating the greatest common divisor
The trial division can be extended by the Euclidean algorithm or other methods for determining the greatest common divisor in such a way that one finds all the prime factors of from a certain interval. To do this, one uses the product of all prime numbers in the interval and calculates the greatest common divisor of the two numbers and . This is the product of prime factors that come from the selected interval, and the individual prime factors can be recovered from it. The advantage of this procedure is that you then only have to apply the trial division to the quotient , which is much smaller than .
Fermat's factorization method
One method that is particularly useful for finding divisors near to is Fermat's factoring method . This algorithm only works for odd numbers and takes advantage of the fact that these can be represented as differences between two square numbers. It first calculates the smallest integer that is greater than or equal to . The algorithm then calculates the differences , , ..., until one of these differences is a square. From this, factors of are calculated.
Further procedures
 Lehman's factoring method
 Continued fraction method
 Pollard p − 1 method
 Pollard p + 1 method
 PollardRho method
 Dixon's factorization method ( random squares method )
 Method of class groups by Daniel Shanks , with variants by Martin Seysen ( class group relations method ) and Lenstra / Schnorr ( random class groups method )
 SQUFOF , square form factorization from Shanks
 Square sieve
 Number body sieve
 Method of elliptic curves
 Schnorr's grid based factorization method
Shor algorithm
The Shor algorithm occupies a special position among the factorization methods . It cannot be run on classic computers, but requires a quantum computer . However, on this he can calculate a factor of in polynomial time. However, it is not yet possible to build quantum computers with a register size sufficient for factoring large numbers. The function of the Shor algorithm is based on determining the order of an element of the prime residual class group with the help of the quantum Fourier transform .
After the Shor algorithm became known, physicists developed technical systems and experimental setups that enable natural numbers to be factored in the classic way, without the superposition of quantum states. These include B. nuclear magnetic resonance, cold atoms, ultrashort light pulses and multipath interferometry.
history
Factoring methods of antiquity
Since Euclid of Alexandria had formulated and proved the fundamental theorem of arithmetic in his main work, The Elements , about 300 years before Christ , it was known that every natural number has a unique prime factorization . With the method of the trial division , which was also essentially known to Euclid, a method of determining this had been found very early on; although it is unsuitable for larger numbers as it takes too much time.
17th to 19th century
In 1643, Pierre de Fermat described in a letter (the addressee is unknown, probably Marin Mersenne or Bernard Frénicle de Bessy ) the factoring method of Fermat , which is now named after him and which is based on representing the number to be factored as the difference between two squares . This method, which is rather worse than the trial division in terms of time, forms the basis for almost all modern factorization methods.
20th century, before the advent of computers
In 1926 Maurice Kraitchik published a paper in which he suggested some improvements to Fermat's method of factoring. In particular, in addition to the number n to be factored , he also considers its multiple, in other words, he is looking for a congruence of the form x ^{2} ≡ y ^{2} (mod n ). To find this, he multiplies suitable congruences of the form x ^{2} ≡ y (mod n ), which can be found easily and effectively (described in the article Square Sieve ).
Derrick Henry Lehmer and Ralph Ernest Powers proposed the socalled continued fraction method in 1931 to find congruences of the form x ^{2} ≡ y (mod n ).
20th century, after the introduction of computers
With the introduction of computers, intensive research into factoring methods began. Building on the idea of Lehmer and Powers, John Brillhart developed a method based on linear algebra over the finite field F _{2} in the 1960s in order to be able to select suitable ones from a list of congruences of the form x ^{2} ≡ y (mod n ). In 1975, together with Michael Morrison, he succeeded in factoring the 39digit Fermat number F _{7, which was} extremely large for the time . In particular, it was thus possible for the first time to find a factorization method with a subexponential running time (the number of digits).
Inspired by the linear sieve of Richard Schroeppel Carl Pomerance 1981 could achieve an acceleration of the process by a sieving method in place of the hitherto used trial division introduced. Since the screening process is not for the continued fraction method was suitable, Pomerance went back over to the originally proposed by Kraitchik process. This made it possible to factor numbers with up to 100 digits; In particular, in 1994 it was possible to break down the 129digit number RSA129 . This method, known as the square sieve , is still the fastest known method for factoring numbers with fewer than 100 digits.
In the 1980s, it was suggested that methods based on Kraitchik's idea could not be substantially faster than the square sieve. This assumption was supported by the fact that there were meanwhile a number of methods with similar running times, and by a result from analytical number theory on even numbers .
In the early 1990s, this assumption was impressively refuted by the number body sieve . The number field sieve was proposed in 1988 by John Pollard for special numbers and then changed by a number of mathematicians (including John Pollard, Arjen Lenstra, Hendrik Lenstra, Jr., Mark Manasse, Carl Pomerance, Joe Buhler, Len Adlemann) so that it became applicable to any number. The transition to algebraic number fields made it possible to keep the numbers used during the calculation significantly smaller and thus to achieve the aforementioned acceleration. In particular, in 1990 the full factorization of the 155digit Fermat number F _{9 was achieved} .
21st century
With the grid sieve (a variant of the number field sieve proposed by Pollard) and other methods, the factorization of the largest number made up of two large prime factors (a socalled fast prime number ) without a special structure was completed in 2005 after two years of work on a computer pool. This is the number RSA200, a 200digit decimal number that was generated along with many other semiprime numbers as part of the RSA Factoring Challenge.
In 2012, a group of 500 participants in the BOINC project NFS @ Home factored a number with 211 decimal digits and thus deciphered a secret message that was presented by Donald Knuth in 1997 in the book The Art of Computer Programming as an unsolvable task at the time. Knuth then replaced the problem using a semiprime number with 318 decimal digits.
The list of champions in the Cunningham Project, named after Allan Joseph Champneys Cunningham , lists current factoring records for various decomposition methods.
Implementations
The program ARIBAS of Otto Forster implemented the methods discussed here different  whether as part of the runtime library or in addition to the author's book on computational number theory .
literature
 David M. Bressoud: Factorization and primality testing. (Undergraduate Texts in Mathematics) Springer, New York 1989, ISBN 0387970401 .
 Otto Forster : Algorithmic Number Theory. Vieweg, 1996, ISBN 352806580X .
 Richard Crandall , Carl Pomerance : Prime Numbers  A Computational Perspective. Springer, New York 2005, ISBN 0387252827 .
 Hans Riesel : Prime Numbers and Computer Methods for Factorization . (Progress in Mathematics) Birkhäuser, Boston 2012, ISBN 1461266815 . Softcover reprint of the 2nd ext. Edition 1994.
 Samuel Wagstaff : The joy of factoring (Student Mathematical Library), American Mathematical Society 2013, ISBN 1470410486 .
Individual evidence
 ^ Hans Riesel : Prime Numbers and Computer Methods for Factorization. 2nd Edition. Birkhäuser, Boston 1994, ISBN 0817637435

^ Daniel Shanks: Analysis and Improvement of the Continued Fraction Method of Factorization , (unpublished, edited by S. McMath 2004)
Daniel Shanks: SQUFOF Notes , (unpublished, edited by S. McMath 2004)
Stephen McMath: Daniel Shanks' Square Forms Factorization (Nov. 2004)
Stephen S. McMath: Parallel integer factorization using quadratic forms , 2005
S. McMath, F. Crabbe, D. Joyner: Continued fractions and parallel SQUFOF , 2005 
^ CP Schnorr: Factoring integers and computing discrete logarithms via diophantine approximation. ( Memento of the original from June 13, 2011 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. in J.Y. Cai (Ed.): Advances in computational complexity theory , AMS 1993, pp. 171182
H. Ritter, C. Rössner: Factoring via strong lattice reduction algorithm. ( Memento of the original from June 13, 2011 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. (Postscript, Technical Report 1997)
Antonio Vera: A note on integer factorization using lattices. (pdf, Preprint March 2010; 216 kB)
CP Schnorr: Average Time Fast SVP and CVP Algorithms for Low Density Lattices and the Factorization of Integers. ( Page no longer available , search in web archives ) Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. (PDF file; 185 kB) (Conference contribution June 2010)  ↑ L. Vandersypen et al. a .: Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. (PDF file; 372 kB)
 ↑ M. Gilowski et al. a: Gauss sum factorization with cold atoms. Phys. Rev. Lett. 100 (2008), 030201.
 ↑ D. Bigourd et al. a: Factorization of numbers with the temporal Talbot effect : Optical implementation by a sequence of shaped ultrashort pulses. Phys. Rev. Lett. 100 (2008), 030202.
 ↑ K. Nitta et al. a .: Improvement of a system for prime factorization based on optical interferometer. In: Optical Supercomputing , Lecture Notes Computer Science 5882 (2009), pp. 124129.
 ↑ V. Tamma u. a .: Factoring numbers with periodic optical interferograms. ( Memento of the original from June 9, 2015 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF; 200 kB)
 ^ Homepage of Knuth
 ↑ http://homes.cerias.purdue.edu/~ssw/cun/champ
 ↑ See in particular the Aribas example file factor.ari on the math website. Institute of the Ludwig Maximilians University in Munich
Web links
 Factor World  page on factorization methods
 Current factoring records