The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Factorization Algorithms

Date: 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 

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   
Associated Topics:
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.