Cryptography Reference
In-Depth Information
What is the probability that a random value
x
2
(mod
N
) factors over the factor base
B
?
How many relations do we require until we can be sure there is a non-trivial vector
e
?
What are the chances that computing gcd(
X
−
Y,N
) splits
N
?
1 relations are sufficient
for line 9 of Algorithm
21
to succeed. The question is whether 1
<
gcd(
X
We deal with the latter two points first. It is immediate that
s
+
Y,N
)
<N
for
the corresponding integers
X
and
Y
. There are several ways the algorithm can fail to split
N
. For example, it is possible that a relation in equation (
15.2
) is such that all
e
i
are even a
nd
x
−
x<
√
N
≡±
i
p
e
i
/
2
(mod
N
). One way that such relations could arise is from 1
≤
−
√
N<x<N
; this situation occurs with ne
gli
gible probability. If
√
N<x<
i
or
N
−
√
N
and
a
Y<
√
N
and so
x
Y
2
is a square in
N
Y
(mod
N
) and the
relation is useful. The following result shows that all these (and other) bad cases occur with
probability at most 1
/
2.
=
N
then 1
≤
≡±
1
2
.
Lemma 15.2.4
The probability to split N using X and Y is at least
Proof
Let
X
and
Y
be the integers computed in line 10 of Algorithm
21
. We treat
Y
as fixed,
and consider the probability distribution for
X
.ByExercise
15.2.1
, the number of solutions
Z
to
Z
2
Y
2
(mod
N
)is2
m
where
m
≡
≥
2 is the number of distinct primes dividing
N
.
Y
are useless but the other 2
m
The two solutions
Z
2 solutions will all split
N
.
Since the values for
x
are chosen uniformly at random it follows that
X
is a randomly
chosen solution to the equation
X
2
=±
−
Y
2
≡
(mod
N
). It follows that the probability to split
N
is (2
m
2)
/
2
m
−
≥
1
/
2.
Exercise 15.2.5
Show that if one takes
s
+
l
relations where
l
≥
2 then the probability of
1
/
2
l
.
splitting
N
is at least 1
−
We now consider the probability of smoothness. We first assume the probability that
x
2
(mod
N
) is smooth is the same as the probability that a random integer modulo
N
is
smooth.
3
Lemma 15.2.6
Let the notation be as above. Let T
B
be the expected number of trials
until a randomly chosen integer modulo N is B-smooth. Assuming the above smoothness
heuristic, Algorithm
21
has expected running time at most
2
T
B
M
(log(
N
))
)
3
c
1
#
B
+
c
2
(#
B
bit operations for some constants c
1
,c
2
(where M
(
n
)
is the cost of multiplying two n-bit
integers).
3
Section 16.3 of Shoup [
497
] gives a modification of the random squares algorithm for which one can avoid this assumption.
The trick is to note that at least one of the cosets of (
Z
/N
Z
)
∗
/
((
Z
/N
Z
)
∗
)
2
has at least as great a proportion of smooth numbers
as random integers up to
N
(Shoup credits Rackoff for this trick). The idea is to fix some 1
<δ<N
and consider relations
coming from smooth values of
δx
2
(mod
N
).
