Continued fraction factorization

The continued fraction method (abbr.: CFRAC ) calculates two divisors of a natural number that is not prime. By repeated application of the prime factorization of this number can be so determined.

The continued fraction method was published in 1931 by Derrick Henry Lehmer and math lovers Ralph Ernest Powers, who is also known by number theoretical calculation results. For decades, it was hardly used, as they are often still found no factorization on the available computing machines after several hours. In 1970, Michael programmed Morrison and John Brillhart, the continued fraction method on a mainframe, and thus computed the factorization of the seventh Fermat number. In the eighties of the twentieth century, the continued fraction method was the standard method for factoring large numbers. Those were numbers with up to fifty decimal places. 1990 was presented with the quadratic sieve, a new algorithm, who succeeded the continued fraction method. The term of the continued fraction method in O- notation, where N is the number to be factored.

Operation

The algorithm searches a congruence of the form x2 ≡ y2 (mod N). To find them, he multiplied suitable congruences of the form x2 ≡ y (mod N). Such congruences lead to a factorization of N ( described in more detail in the article Dixon's factorization method. )

With the continued fraction method one uses to find the continued fraction expansion of around such congruences. The continued fraction expansion provides the best approximations to the root of N as fractions of the form. Each approximation yields a congruence x2 ≡ y (mod N) for x = p and y = x2 - q2 · N. Since the break is a best approximation for, is smooth and small y with high probability and it takes only a few such congruences.

Algorithm by Morrison and Brillhart

The variant of the continued fraction method described here corresponds to that which was published by Morrison and Brillhart in her essay "A Method of Factoring and the Factorization of". The algorithm consists of three main steps. The number to be factored further identified with.

Step A

Choose a natural number and compute the continued fraction expansion of. The continued fraction expansion can be aborted at any point, so you have a continued fraction of the form

Receives. Now Calculate the pairs, where the numerator and denominator of the -th convergent and are according to the formula

Calculated.

Step B

From the in step A generated pairs are selected those in which all prime factors of a predetermined factor base stem. The base typically contains the factor -1 and all prime numbers, the divider Q may be, to a certain limit. One needs only the primes p with or include in the factor base, because Q can only be divisible by this p.

By repeated trial division can be determined whether the respective product of numbers from the factor base, and by the way we obtain the prime factorization of.

With the selected pairs filling a table. This table contains a column for each number of the factor base. In the factor -based columns, a one is added when the respective factor in the prime factorization of odd often. Otherwise, one enters a zero. The table entry for the couple and the factor base looks for example like this.

Then determined a choice of table rows for which the sum of the entries in each column of the table is straight, so that the product of the selected rows contains each factor with an even power and thus is a square number. This is certainly possible, if the number of table rows at least one larger than the number of factors in the factor -based and therefore the columns of the table.

Step C

You multiply the As all couples and Qs of all pairs of the selected table rows. Thus we obtain the Legendre congruence

It then calculates and.

If and, then and are proper divisors of N. Otherwise, it may be a different selection of table rows successfully. If necessary. one must still calculate more rows.

History

The first step on the road to continued fraction method was the factorization of Fermat described in 1643 by Pierre de Fermat. This calculation method takes two square numbers and so true. is again the number to be factored. Due to the third binomial formula applies

And and therefore are divisors of.