Cryptography Reference
In-Depth Information
C.2 The Continued Fraction Algorithm
∈
N
and a smoothness bound
B
has been
selected. Then execute the following steps:
(1) Choose a factor base of primes
Suppose that we wish to factor
n
F
{
}
∈
N
=
p
1
,p
2
,...,p
k
for some
k
deter-
mined by
B
and a large upper index value
J
.
C.2
√
n
(2)
Set
Q
0
=1,
P
0
=0,
A
−
1
=1,
A
0
=
=
q
0
=
P
1
. For each natural
number
j
≤
J
, recursively compute
Q
j
using the following formulas:
P
j
Q
j
−
1
,
q
j
=
P
j
+
Q
j
=
n
−
√
n
,
Q
j
A
j
=
q
j
A
j
−
1
+
A
j
−
2
,
P
j
+1
=
q
j
Q
j
−
P
j
,
F
and trial divide
Q
j
by the primes in
to determine if
Q
j
is
p
k
-smooth. If
it is, use its factorization
Q
j
=
i
=1
p
a
i,j
to form the binary
k
+ 1-tuple,
i
v
j
=(
v
0
,j
,v
1
,j
,v
2
,j
,...,v
k,j
)
,
where
v
0
,j
is, respectively, 0 or 1 according as
j
is even or odd, and for
1
k
,
v
i,j
is, respectively, 0 or 1 according to whether
a
i,j
is even or
odd. If
Q
j
is not
p
k
-smooth, discard it and return to calculate
Q
j
+1
.
≤
i
≤
(3) For each set
S
of the vectors v
j
constructed in (2), for which it is discovered
that
v
i,j
≡
0 (mod 2)
,
0
≤
i
≤
k,
j
∈
S
we have
x
2
≡
y
2
(mod
n
), where
j
∈
S
!
1
/
2
"
1)
j
Q
j
x
=
(
−
and
y
≡
A
j
−
1
(mod
n
)
.
j
∈
S
If
x
≡±
y
(mod
n
), then gcd(
x
±
y,n
) gives a nontrivial factor of
n
.
By Corollary A.3 on page 498,
A
j
−
1
−
nB
j
−
1
=(
1)
j
Q
j
,
−
which is the heart of the algorithm. Thus, we have that
nB
j
−
1
≡
A
j
−
1
(mod
p
),
for any prime
p
Q
j
,so
n
is a quadratic residue modulo
p
. Hence, we only put
C.2
From knowledge about the distribution of smooth
integers close to
√
n
, the optimal
k
is
known to be one that is chosen to be approximately
exp(
√
log(
n
) log log(
n
))
.
Search WWH ::
Custom Search