Continued fraction method

The continued fraction method (abbr .: CFRAC ) calculates two divider a natural number that no prime number is. Repeated application can be used to determine the prime factorization of this number.

The continued fraction method was published in 1931 by Derrick Henry Lehmer and the mathematics lover Ralph Ernest Powers , who is also known for his number-theoretical calculation results. It was hardly used for decades because it often failed to factorize on the calculating machines available after several hours. In 1970 Michael Morrison and John Brillhart programmed the continued fraction method on a mainframe computer and used it to calculate the factorization of the seventh Fermat number . In the 1980s, the continued fraction method was the standard method for factoring large numbers. Back then, those were numbers with up to fifty decimal places. In 1990 a new algorithm was presented with the square sieve , which succeeded the continued fraction method. The term the continued fraction method in O notation is , where N is the number to be factored. ${\displaystyle O\left(e^{\sqrt {2\log N\log \log N}}\right)}$

functionality

The algorithm looks for a congruence of the form x ²  ≡  y ²  (mod  N ). To find these, he multiplies suitable congruences of the form x ² ≡ y (mod  N ). Such congruences lead to a factorization of N (described in more detail in the article Dixon's factorization method .)

The continued fraction method uses the continued fraction expansion of to find such congruences. The continued fraction expansion provides the best approximations of the root of N as fractions of the form . Every approximation yields a congruence x ² ≡ y (mod  N ) for x = p and y = x ² - q ² · N. Since the fraction is a best approximation for , y is small and with a high probability smooth and you only need a few such congruences. ${\displaystyle {\sqrt {N}}}$ ${\displaystyle {\frac {p}{q}}}$ ${\displaystyle {\sqrt {N}}}$

Morrison and Brillhart algorithm

The variant of the continued fraction method described here corresponds to that published by Morrison and Brillhart in their article "A Method of Factoring and the Factorization of ". The algorithm consists of three main steps. The number to be factored is referred to below with . ${\displaystyle F_{7}}$ ${\displaystyle N}$

Step A.

Choose a natural number and calculate the continued fraction expansion of . The continued fraction development can be terminated at any point , so that one has a continued fraction of the form ${\displaystyle k\geq 1}$ ${\displaystyle {\sqrt {kN}}}$ ${\displaystyle n-1}$

${\displaystyle [q_{0};q_{1},q_{2},\ldots ,q_{n-1},{\frac {{\sqrt {kN}}+P_{n}}{Q_{n}}}]}$

receives. The pairs are now calculated , where the numerator and denominator of the -th convergent are and are based on the formula ${\displaystyle (A_{i-1},Q_{i})}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{i}}$ ${\displaystyle i}$ ${\displaystyle Q_{i}}$

${\displaystyle Q_{i}=(-1)^{i}\cdot (A_{i-1}^{2}-kNB_{i-1}^{2})}$

calculated.

Step B.

From the pairs generated in step A , those are selected in which all prime factors originate from a predetermined factor base. The factor base usually contains the number −1 and all prime numbers that can divide Q up to a certain bound. One only needs to include the prime numbers p with or in the factor base, because Q can only be divisible by this p . ${\displaystyle (A,Q)}$ ${\displaystyle Q}$ ${\displaystyle p=2}$ ${\displaystyle (kN)^{(p-1)/2}\,{\bmod {\;}}p\leq 1}$

Multiple trial divisions can be used to determine whether each is a product of numbers from the factor base, and in addition one obtains the prime factorization of . ${\displaystyle Q}$ ${\displaystyle Q}$

A table is filled with the selected pairs. This table contains a column for each factor base number. The number 1 is entered in the factor base columns if the respective factor occurs often in the prime number decomposition of odd. Otherwise enter 0. For example, the table entry for the pair and the factor base looks like this: ${\displaystyle (A,Q)}$ ${\displaystyle Q}$ ${\displaystyle (375,-220=-1\cdot 2^{2}\cdot 5\cdot 11)}$ ${\displaystyle \{-1,2,3,5,7,11,13\}}$

	−1	2	3	5	7th	11	13
(375, −220)	1	0	0	1	0	1	0

A selection of table rows is then determined for which the sum of the entries in each table column is even, so that the product of the selected rows contains every factor with an even power and is therefore a square number. This is certainly possible if the number of table rows is at least one greater than the number of factors in the factor base and thus the table columns. ${\displaystyle Q}$

Step c

The A of all pairs and the Q of all pairs of the selected table rows are multiplied. This is how you get the Legendre congruence

${\displaystyle x^{2}=\prod A^{2}\equiv \prod Q=y^{2}\;({\bmod {\,}}N)}$.

One then calculates and . ${\displaystyle d_{1}=\operatorname {ggT} (x-y,N)}$ ${\displaystyle d_{2}=\operatorname {ggT} (x+y,N)}$

If and , then and are real factors of N. Otherwise, a different selection of table rows may be successful. If necessary you have to calculate more lines. ${\displaystyle x\not \equiv y\;({\bmod {\,}}N)}$ ${\displaystyle x\not \equiv -y\;({\bmod {\,}}N)}$ ${\displaystyle d_{1}}$ ${\displaystyle d_{2}}$

history

The first step on the way to the continued fraction method was the Fermat factorization method described by Pierre de Fermat in 1643 . This calculation method finds two square numbers and , so that holds. is again the number to be factored here. Based on the 3rd binomial formula, the following applies ${\displaystyle x^{2}}$ ${\displaystyle y^{2}}$ ${\displaystyle x^{2}-y^{2}=N}$ ${\displaystyle N}$

${\displaystyle N=x^{2}-y^{2}=(x+y)(x-y)}$

and and are therefore dividers of . ${\displaystyle x+y}$ ${\displaystyle x-y}$ ${\displaystyle N}$

In 1798 Adrien-Marie Legendre published his book "Essai sur la théorie des nombres". The Legendre congruences are a further development of Fermat's method. The difference between the square numbers and no longer has to be the same , but can be any multiple of . The roots and the squares must also meet three conditions: , and . In those circumstances, divides and both the greatest common divisor and are factors . ${\displaystyle x^{2}}$ ${\displaystyle y^{2}}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle 0<x,y<N}$ ${\displaystyle x\neq y}$ ${\displaystyle x+y\neq N}$ ${\displaystyle N}$ ${\displaystyle x^{2}-y^{2}=(x+y)(x-y)}$ ${\displaystyle \operatorname {ggT} (N,x+y)}$ ${\displaystyle \operatorname {ggT} (N,x-y)}$ ${\displaystyle N}$

literature

• Carl Pomerance : A Tale of Two Sieves. (PDF; 275 kB) In: Notices of the AMS. Vol. 43, No. 12, 1996, pp. 1473-1485.
• DH Lehmer , RE Powers: On Factoring Large Numbers. In: Bulletin of the American Mathematical Society. Vol. 37, 1931, pp. 770-776 ( doi : 10.1090 / S0002-9904-1931-05271-X ).
• Michael A. Morrison, John Brillhart : A Method of Factoring and the Factorization of . ${\displaystyle F_{7}}$In: Mathematics of Computation. Vol. 29, No. 129, 1975, pp. 183-205 ( doi : 10.2307 / 2005475 ).