Cryptography Reference
In-Depth Information
2
14
11
2
is a square and hence we obtain the required
Nowwe see that
z
−
4
z
−
2
z
0
=
·
=
√
z
−
4
z
−
2
z
0
=
=
x
−
4
x
−
2
x
0
=
·
·
=
congruence by taking
x
41
43
45
79335 and
y
2
7
·
11
=
1408. Now, gcd
(
x
−
y
,
n
)
=
gcd
(
77927
,
1937
)
=
149 is a nontrivial
factor.
In this example we used an extremely small factor base consisting of only two
primes. We leave as an exercise for the reader to show that if we use the factor base
{
2
,
11
,
13
,
17
}
, then it is enough to let
t
run through the interval
[
0
,
10
]
to find a
congruence that serves to factor
n
.
The preceding examples use very small numbers and so are not very representative
of what might happen when trying to factor large integers. We will later handle larger
examples with Maple but now it is worthwhile to consider what we did in these
examples in order to find the required congruences. One of the things we had to do
was to generate a factor base containing the primes
p
B
such that
n
is a quadratic
residue modulo
p
. This poses the problem of how to choose
B
and we will give some
guidelines later on.
Once the factor base was ready, we had to generate the auxiliary integers
z
t
and
obtain a number of them that factor as a product of members of the factor base, so
that these
z
t
are, in particular,
B-smooth
in the sense that all their prime factors are
≤
≤
B
. In one case, several of the integers
z
t
were even greater than the number
n
being factored but this was an artifact of the small size of
n
and of the relatively
small factor base used in our example. In real life this will not be a problem because
the values of
t
will be small enough to guarantee that the
x
t
are much smaller than 2
n
and hence that the
z
t
are much smaller than
n
. Then the
B
-smooth
z
t
can be factored
by trial division over the factor base, although we will later see that there is a much
better alternative.
The next step was to look for a subset of the
B
-smooth
z
t
whose product was a
square and this produced a congruence of the required type. This part of the algorithm
also poses some problems. One of them is how to recognize how many
B
-smooth
values should be generated in order to have assurance (or, at least, a high probability)
that a square may be obtained by multiplying some of these smooth values (actually,
several of these squares will be required in order to factor the number with high
probability). Another related problem is how to find which of these smooth values
we have to multiply in order to get the squares we are looking for. In the previous
examples this was done by direct inspection of the factorizations of the smooth values
until several of them were found such that the sums of their exponents were all even
but it is clear that a much more efficient way is required for the method to work with
large numbers.
In order to deal with this problem, suppose that our factor base is
FB
=
{
p
1
,...,
p
K
}
, where
p
1
=−
1,
p
2
=
2, and
p
3
,...,
p
K
are odd primes
≤
B
.
Each of the factorizations of a
B
-smooth value
z
t
is called a
relation
:
K
p
e
tj
j
z
t
=
,
j
=
1
