Cryptography Reference
In-Depth Information
Algorithm 21
Random squares factoring algorithm
INPUT:
N
∈ N
OUTPUT: Factor of
N
1:
Select a suitable
B
∈ N
and construct the
factor base
B
={
p
1
,...,p
s
}
consisting of
all primes
≤
B
2:
repeat
3:
x
2
Choose an integer 1
≤
x<N
uniformly at random and compute
a
=
(mod
N
)
reduced to the range 1
≤
a<N
Try to factor
a
as a product in
B
(e.g., using trial division)
4:
if
a
is
B
-smooth
then
5:
=
store the value
x
and the exponent row vector
e
(
e
1
,...,e
s
) as in equa-
6:
tion (
15.2
)inamatrix
7:
end if
8:
until
there are
s
1 rows in the matrix
9:
Perform linear algebra over
+
F
2
to find a non-trivial linear dependence among the vectors
e
j
modulo 2
10:
Define
X
and
Y
as in equation (
15.4
)
11:
return
gcd(
X
−
Y,N
)
The sum of the three rows is the vector
(4
,
6
,
4)
.
Let
2
2
3
3
5
2
X
=
264
≡
34
·
52
·
55 (mod 551) and
Y
=
496
≡
·
·
(mod 551)
.
It follows that
X
2
Y
2
≡
(mod
N
)
and gcd(
X
−
Y,N
)
=
29 splits
N
.
Exercise 15.2.3
Factor
N
=
3869 using the above method and factor base
{
2
,
3
,
5
,
7
}
.
15.2.1 Complexity of the random squares algorithm
There are a number of issues to deal with when analysing this algorithm. The main problem
is to decide how many primes to include in the factor base. The prime number theorem
implies that
s
B/
log(
B
). If we make
B
larger then the chances of finding a
B
-smooth number increase but, on the other hand, we need more relations and the linear
algebra takes longer. We will determine an optimal value for
B
later. First, we must write
down an estimate for the running time of the algorithm as a function of
s
. Already this
leads to various issues:
=
#
B
≈
