Cryptography Reference
In-Depth Information
The factor base method is a clever combination of two of the factoring methods
that we have discussed, Fermat's method and trial division. While the factor base
method can factor integers that are beyond the reach of these two methods, its main
interest lies in the fact that the idea of using a factor base can be further refined and
underlies the more powerful factoring algorithms currently available.
Example 6.19
We may see that Mersenne's number
M
67
is easily factorable by this
method (but, as we have seen, this number is also within reach of trial division). In
fact, substantially larger numbers can also be factored with
FBFactor
. Consider,
for example, the 27-digit number 672333687808859742277210981, which is beyond
the reach of our previous implementations of trial division and Fermat's method
(although quickly factorable by the rho method). We can easily factor this number
with
FBFactor
, and in order to give an idea of the parameters involved we print
the output of
FBFactor
, which looks like this:
> FBFactor(672333687808859742277210981);
Using multiplier:
21
Using smoothness bound:
5582
Size of factor base:
361
Numbers tried to factor:
987418
Smooth values found:
366
Solving a matrix of size:
366, 361
Number of linear dependencies found:
25
Factors:
(36335009715479) (18503743168739)
Exercise 6.22
Make an experimental study of the time required by the function
FBFactor
to factor numbers of several sizes between 15 and 30 decimal digits.
Determine the value of the constant
c
in the input of
FBFactor
that gives the best
results in this range.
6.4.7 The Quadratic Sieve
The factor base algorithm outlined above is a nice extension of Fermat's method
but is still inefficient because trial division, which runs in exponential time, lies
at its heart. Thus the crucial idea to obtain a fast factorization method is to get
rid of trial division while preserving the basic procedure of generating many
B
-
smooth numbers. These numbers have to be factored to find the relations but, since
they are the values of a (quadratic) polynomial, there is an alternative. We have,
on one side, a bunch of numbers from which we want to extract smooth values
and factor them over the factor base. On the other, we have the factor base primes.
In the previous algorithm we considered the polynomial values individually and
