Cryptography Reference
In-Depth Information
The problem that arises now is how to generate these congruences. Here a new
important idea—due to Kraitchik who introduced it in the 1920s—comes into play:
just generate congruences of the form
u
2
such that
v
is small, and factor
these residues
v
as products of (small) primes. Then search among them for a set of
congruences
x
t
≡
v
(
mod
n
)
such that the product of the
z
t
is a square (which can
easily be detected because the factorizations of the
z
t
are known) and multiply them
to obta
in a co
ngruence of the required form
x
2
≡
z
t
(
mod
n
)
=
t
y
2
≡
(
mod
n
)
, where
x
x
t
and
=
t
z
t
. The form inwhichwewill generate the required congruenc
e
s is inspired
by Fermat's method. We will co
ns
ider the polynomial
Q
y
+
√
n
2
(
t
)
=
(
t
)
−
n
and
+
√
n
x
t
compute the values
x
t
; these
z
t
are just the integers that are submitted to the squareness test in Fermat's method.
We illustrate this with a simple example.
=
t
and
z
t
=
Q
(
t
)
=
−
n
for
t
=
0
,
1
,...
√
1261
=
=
Example 6.13
Let us factor
n
1261. We compute
36 and the values
=
,...
of
x
t
and
z
t
for
t
0
5. Then we have:
x
t
=
x
t
=
t
+
−
n
t
x
t
36
z
t
Factorization of
z
t
0
36
1296
35
5
·
7
2
2
3
3
1
37
1369
108
·
2
38
1444
183
3
·
61
2
2
3
39
1521
260
·
5
·
13
4
40
1600
339
3
·
113
2
2
5
41
1681
420
·
3
·
5
·
7
We see that none of the
z
t
is a square since all of them have some odd exponent
in their prime factorization. We look for a product of the
z
t
which is a square, i.e.,
we look for a product in which all prime factors have even exponents. We see that if
we multiply the prime factors in rows 1, 2 and 6 (corresponding to
t
=
0
,
1
,
5), we
2
4
3
4
5
2
7
2
which is obviously a square with square root equal
obtain
z
0
z
1
z
5
=
·
·
·
to 2
2
3
2
·
·
5
·
7
=
1260. Thus if we set
x
=
x
0
x
1
x
5
=
36
·
37
·
41
=
54612 and
y
=
√
z
1
z
2
z
6
=
1260, then
x
2
y
2
≡
(
mod 1261
)
and
x
≡±
y
(
mod 1261
)
. Nowwe find
a proper factor of 1261 by computing gcd
(
x
−
y
,
1261
)
=
gcd
(
53352
,
1261
)
=
13
and we have that 1261
97. Using
FermatFactor
we can find the number
of steps required by Fermat's method on this integer:
=
13
·
> FermatFactor(1261, numsteps = true);
13, 97, 20
We see that Fermat'smethod required 20 iterations to factor 1261whileKraitchik's
method required only the computation of the first 6 iterations.
Although Kraitchik's method is still far from satisfactory, we are going to see that
it is a big improvement on Fermat's method and an important step towards the more
powerful modern factoring algorithms. The strategy applied in the preceding example
was to chose the
z
t
as small as possible in order to maximize the probability that
they factor as a product of small primes. Then we discarded the
z
t
with 'large' prime
factors, namely,
z
2
,
z
3
and
z
4
, which were not used to obtain the final congruence.
Thesystematicwaytodothisistousea
factor base
consisting of primes less than a