Cryptography Reference
In-Depth Information
Proof
Suppose we compute the factorisation of
x
2
(mod
N
) over
B
by trial division. This
requires
O
(#
1) relations
to have a soluble linear algebra problem. As said above, the expected number of trials of
x
to get a
B
-smooth value of
x
2
B
M
(log(
N
))) bit operations for each value of
x
. We need (#
B
+
(mod
N
)is
T
B
. Hence, the cost of finding the relations is
O
((#
)
M
(log(
N
))), which gives the first term.
The linear algebra problem can be solved using Gaussian elimination (we are ignoring
that the matrix is sparse) over
B
+
1)
T
B
(#
B
)
3
) bit operations. This gives the
F
2
, which takes
O
((#
B
second term.
It remains to choose
B
as a function of
N
to minimise the running time. By the discussion
in Section
15.1
, it is natural to approximate
T
B
by
u
u
where
u
log(
N
)
/
log(
B
). We now
explain how subexponential functions naturally arise in such algorithms. Since increasing
B
makes the linear algebra slower, but makes relations more likely (i.e., lowers
T
B
), a natural
approach to selecting
B
is to try to equate both terms of the running time in Lemma
15.2.6
.
This leads to
u
u
=
=
#
B
. Putting
u
=
log(
N
)
/
log(
B
), #
B
=
B/
log(
B
), taking logs and
ignoring log(log(
B
)) terms gives
log(
N
) log(log(
N
))
/
log(
B
)
≈
log(
B
)
.
This implies log(
B
)
2
≈
log(
N
) log(log(
N
)) and so
B
≈
L
N
(1
/
2
,
1). The overall complexity
for this choice of
B
would be
L
N
(1
/
2
,
3
+
o
(1)) bit operations.
A more careful argument is to set
B
=
L
N
(1
/
2
,c
) and use Corollarry 15.1.8. It fol-
lows that
T
B
=
L
N
(1
/
2
,
1
/
(2
c
)
+
o
(1)) as
N
→∞
. Putting this into the equation of
Lemma
15.2.6
gives complexity
L
N
(1
/
2
,
2
c
+
1
/
(2
c
)
+
o
(1))
+
L
N
(1
/
2
,
3
c
) bit opera-
tions. The function
x
+
1
/x
is minimised at
x
=
1; hence, we should take
c
=
1
/
2.
Theorem 15.2.7
Let the notation be as above. Under the same assumptions as
Lemma
15.2.6
then Algorithm
21
has complexity
L
N
(1
/
2
,
2
+
o
(1))
bit operations as N
→∞
.
Proof
Put
B
=
L
N
(1
/
2
,
1
/
2) into Lemma
15.2.6
.
1 methods, this factoring algorithm
has essentially no dependence on the factors of
N
. In other words, its running time is
essentially the same for all integers of a given size. This makes it particularly suitable for
factoring
N
We remark that, unlike the Pollard rho or Pollard
p
−
=
pq
where
p
and
q
are primes of the same size.
15.2.2 The quadratic sieve
To improve the result of the previous section it is necessary to reduce the cost of the linear
algebra and to reduce the cost of decomposing smooth elements as products of primes. We
