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 non-trivial 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 non-trivial 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:

1. Find / remove small factors by trial division.
2. Use a prime number test to find out whether the number is a prime number or a prime power .
3. Search for comparatively small prime factors (<10 ³⁰ ) using the elliptic curve method .
4. 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. ${\displaystyle n}$

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 time-consuming to use it to completely decompose a number with two or more large prime factors. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$

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 . ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n/\operatorname {ggT} (n,m)}$ ${\displaystyle n}$

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. ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle x^{2}-n}$ ${\displaystyle (x+1)^{2}-n}$ ${\displaystyle (x+2)^{2}-n}$ ${\displaystyle n}$

Further procedures

• Lehman's factoring method
• Continued fraction method
• Pollard p − 1 method
• Pollard p + 1 method
• Pollard-Rho 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 set-ups 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 multi-path interferometry. ${\displaystyle n}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

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 ²  ≡  y ²  (mod  n ). To find this, he multiplies suitable congruences of the form x ² ≡ 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 so-called continued fraction method in 1931 to find congruences of the form x ²  ≡  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 ₂ in the 1960s in order to be able to select suitable ones from a list of congruences of the form x ² ≡ y (mod n ). In 1975, together with Michael Morrison, he succeeded in factoring the 39-digit 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 sub-exponential 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 129-digit number RSA-129 . 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 155-digit 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 so-called fast prime number ) without a special structure was completed in 2005 after two years of work on a computer pool. This is the number RSA-200, a 200-digit decimal number that was generated along with many other semi-prime 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 semi-prime 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 0-387-97040-1 .
• Otto Forster : Algorithmic Number Theory. Vieweg, 1996, ISBN 3-528-06580-X .
• Richard Crandall , Carl Pomerance : Prime Numbers - A Computational Perspective. Springer, New York 2005, ISBN 0-387-25282-7 .
• Hans Riesel : Prime Numbers and Computer Methods for Factorization . (Progress in Mathematics) Birkhäuser, Boston 2012, ISBN 1-4612-6681-5 . Softcover reprint of the 2nd ext. Edition 1994.
• Samuel Wagstaff : The joy of factoring (Student Mathematical Library), American Mathematical Society 2013, ISBN 1-4704-1048-6 .

Individual evidence

1. ^ Hans Riesel : Prime Numbers and Computer Methods for Factorization. 2nd Edition. Birkhäuser, Boston 1994, ISBN 0-8176-3743-5
2. ^ 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
3. ^ 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. 171-182
   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)
4. ↑ L. Vandersypen et al. a .: Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. (PDF file; 372 kB)
5. ↑ M. Gilowski et al. a: Gauss sum factorization with cold atoms. Phys. Rev. Lett. 100 (2008), 030201.
6. ↑ 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.
7. ↑ 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. 124-129.
8. ↑ 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) 
9. ^ Homepage of Knuth
10. ↑ http://homes.cerias.purdue.edu/~ssw/cun/champ
11. ↑ 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

	This article is available as an audio file:
	Save | Information  | 12:54 min (13 MB) Text of the spoken version (December 29, 2013)
	More information on spoken Wikipedia