Cryptography Reference
In-Depth Information
L
N
(
ab,dc
b
a
1
−
b
4. Let
0
<b<
1
and
0
<d.IfM
=
L
N
(
a,c
)
then L
M
(
b,d
)
=
+
o
(1))
as N
→∞
.
5.
log(
N
)
m
=
O
(
L
N
(
a,c
))
for any m
∈ N
.
6. L
N
(
a,c
)log(
N
)
m
=
O
(
L
N
(
a,c
+
o
(1)))
as N
→∞
for any m
∈ N
. Hence, one can
always replace O
(
L
N
(
a,c
))
by O
(
L
N
(
a,c
+
o
(1)))
.
7.
log(
N
)
m
≤
L
N
(
a,o
(1))
as N
→∞
for any m
∈ N
.
8. If F
(
N
)
=
O
(
L
N
(
a,c
))
then F
(
N
)
=
L
N
(
a,c
+
o
(1))
as N
→∞
.
N
c
√
log(log(
N
))
/
log(
N
)
.
9. L
N
(1
/
2
,c
)
=
Exercise 15.1.7
Prove Lemma
15.1.6
.
→∞
Corollary 15.1.8
Let c>
0
.AsN
, the probability that a randomly chosen integer
1
≤
x
≤
N is L
N
(1
/
2
,c
)
-smooth is L
N
(1
/
2
,
−
1
/
(2
c
)
+
o
(1))
.
Exercise 15.1.9
Prove Corollary
15.1.8
(using Corollary
15.1.3
).
Exercise 15.1.10
Let 0
<b<a<
1. Let 1
L
N
(
a,c
) be a randomly chosen integer.
Show that the probability that
x
is
L
N
(
b,d
)-smooth is
L
N
(
a
≤
x
≤
−
b,
−
c
(
a
−
b
)
/d
+
o
(1)) as
N
→∞
.
15.2 Factoring using random squares
The goal of this section is to present a simple version of Dixon's random squares factoring
algorithm. This algorithm is easy to describe and analyse, and already displays many of
the important features of the algorithms in this chapter. Note that the algorithm is not
used in practice. We give a complexity analysis and sketch how subexponential running
times naturally arise. Further details about this algorithm can be found in Section 16.3 of
Shoup [
497
] and Section 19.5 of von zur Gathen and Gerhard [
220
].
Let
N
be an integer to be factored. We assume in this section that
N
is odd,
composite and not a perfect power. As in Chapter
12
, we focus on splitting
N
into a product
of two smaller numbers (neither of which is necessarily prime). The key idea is that if one
can find congruent squares
∈ N
x
2
y
2
≡
(mod
N
)
≡±
−
such that
x
y
(mod
N
) then one can split
N
by computing gcd(
x
y,N
).
Exercise 15.2.1
Let
N
be an odd composite integer and
m
be the number of distinct primes
dividing
N
. Show that the equation
x
2
1(mod
N
) has 2
m
solutions modulo
N
.
≡
A general way to find congruent squares is the following.
1
Select a
factor base
B
=
{
p
1
,...,p
s
}
consisting of the primes
≤
B
for some
B
∈ N
. Choose uniformly at random
1
This idea goes back to Kraitchik in the 1920s; see [
439
] for some history.
