Cryptography Reference
In-Depth Information
x
2
an integer 1
≤
x<N
, compute
a
=
(mod
N
) reduced to the range 1
≤
a<N
and try
(e.g., using trial division).
2
If
a
is
B
-smooth then this succeeds,
inwhichcasewehavea
relation
to factor
a
as a product in
B
s
p
e
i
i
x
2
≡
(mod
N
)
.
(15.2)
i
=
1
The values
x
for which a relation is found are stored as
x
1
,x
2
,...,x
t
. The corresponding
exponent vectors
e
j
=
t
are also stored. When enough relations
have been found we can use linear algebra modulo 2 to obtain congruent squares. More
precisely, compute
λ
j
∈{
(
e
j,
1
,...,e
j,s
)for1
≤
j
≤
0
,
1
}
such that not all
λ
j
=
0 and
t
λ
j
e
j
≡
(0
,
0
,...,
0) (mod 2)
.
j
=
1
Equivalently, this is an integer linear combination
t
λ
j
e
j
=
(2
f
1
,...,
2
f
s
)
(15.3)
j
=
1
with not all the
f
i
equal to zero. Let
t
s
x
λ
j
j
p
f
i
i
≡
≡
X
(mod
N
)
,
Y
(mod
N
)
.
(15.4)
j
=
1
i
=
1
One then has
X
2
Y
2
Y,N
)
(note that this gcd could be 1 or
N
, in which case the algorithm has failed). We present the
above method as Algorithm
21
.
We emphasise that the random squares algorithm has two distinct stages. The first stage
is to generate enough relations. The second stage is to perform linear algebra. The first
stage can easily be distributed or parallelised, while the second stage is hard to parallelise.
≡
(mod
N
) and one can hope to split
N
by computing gcd(
X
−
=
·
=
B
={
}
Example 15.2.2
Let
N
. One finds the following
congruences (in general 4 relations would be required, but we are lucky in this case)
34
2
19
29
551 and let
2
,
3
,
5
3
3
≡
·
2
(mod
N
)
52
2
2
2
5
3
≡
·
(mod
N
)
55
2
3
3
≡
2
·
·
5(mod
N
)
.
These relations are stored as the matrix
130
203
131
.
To obtain non-trivial relations one should restrict to integers in the range
√
N<x<N
−
√
N
. But it turns out to be simpler
to analyse t
he
algorithm for the case 1
≤
x<N
. Note that the probability that a randomly chosen integer 1
≤
x<N
satisfies
1
≤
x<
√
N
is negligible.
2
