Factorization AlgorithmsDate: 02/22/99 at 00:10:04 From: c.vijay Subject: Factorization Algorithms Can you send me the most efficient classical algorithm available for factoring a given number (very large, say at least 100 digits) into primes? Since factorization is assumed to be hard it is widely used in RSA cryptosystems. It can be assumed that the number to be factorized is a product of only two large prime numbers. Date: 02/22/99 at 09:58:12 From: Doctor Rob Subject: Re: Factorization Algorithms The best algorithm known at present for factoring such large, difficult numbers, is called the Number Field Sieve Factoring Algorithm. I will outline it below. The record it has achieved is the factorization of a number of 140 decimal digits, which took several months on a rather large network of workstations, followed by several days of labor on a super-computer. Let N be the number to be factored. Find a polynomial f(x) with small integer coefficients and a small integer m such that f(m) = 0 (mod N). The degree d of f(x) should be about 4 or 5 for numbers of this size. Then look at the number field Q(a) found by adjoining a complex root alpha of f(x) to the rational numbers Q, that is f(alpha) = 0 in the complex numbers. Then there is a homomorphism phi from Z[alpha] to Z/NZ defined by mapping alpha to the congruence class of m and elements of Z to their congruence class mod N. Now look for pairs (a, b) such that a-b*m factors into prime numbers, all smaller than some bound B1, and such that the ideal (a - b*alpha) in the ring Z [alpha] factors into prime ideals whose norms are all smaller than some bound B2. B1 and B2 are parameters whose size controls the speed of the algorithm. When you have found enough pairs (a, b) so that they outnumber the prime numbers smaller than B1 together with the prime ideals of norm smaller than B2, then you can find subsets of these pairs such that the product of (a[i] - b[i]*m) is a square, and also the product of the ideals (a[i] - b[i]*alpha) is a square ideal. Finding these subsets involves the use of linear algebra over Z/2Z on a very large matrix, several hundred thousand on a side, to find a vector in the left nullspace. There is a problem with units in Z[alpha], and taking a square root in Z[alpha] (this is suprisingly hard!), which are to be overcome. Once you have found a few such subsets, you can apply the map phi to the ideal parts to reduce the calculation to one in Z/NZ. The result is a pair of integers X and Y such that X^2 = Y^2 (mod N), and the factors of N are found from GCD (X + Y, N) and GCD (X - Y, N). I have glossed over most of the details, and omitted some of the difficulties that can arise but which can also be overcome. Perhaps this will give you the general idea of how the algorithm works. The expected amount of work required has the form e^([1.9+c]*[ln N]^[1/3]*[ln ln N]^[2/3]), where c is a quantity which tends to 0 as N -> infinity, but whose size is not known for N in the range you mention. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Ask Dr. MathTM
© 1994-2002 The Math Forum
http://mathforum.org/dr.math/