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
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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search