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
 
 
Search WWH ::




Custom Search