Cryptography Reference
In-Depth Information
7.3.2.1
Continued Fraction
The continued fraction algorithm was developed and proposed in the 1970s [5]. It
has a subexponential running time and was the the fastest integer factoring algorithm
in use for quite a long time (i.e., until the QS was developed).
7.3.2.2
QS
In the 1980s, Carl Pomerance developed and proposed the QS [6]. Like many other
general-purpose integer factorization algorithms, the QS is based on an idea that is
due to Fermat. If we have two integers
x
and
y
with
x
=
±
y
(mod
n
)
and
x
2
y
2
(mod
n
)
,
≡
(7.1)
then we can factorize
n
with a success probability of 1
/
2.Let
n
=
pq
, and we want
to use
x
and
y
to find
p
or
q
. First, we note that
x
2
y
2
(mod
n
) means that
≡
x
2
y
2
=(
x
−
−
y
)(
x
+
y
)=0(mod
n
)
.
Because
n
=
pq
, the four following cases are possible:
1.
p
|
x
−
y
and
q
|
x
+
y
;
2.
p
|
x
+
y
and
q
|
x
−
y
;
3.
p
|
x
−
y
and
q
|
x
−
y
(but neither
p
nor
q
divides
x
+
y
);
4.
p
|
x
+
y
and
q
|
x
+
y
(but neither
p
nor
q
divides
x
−
y
).
All of these cases are equally probable and occur with a probability of 1
/
4.If
we then compute
d
=
gcd
(
x
−
y, n
)
,
then
d
refers to
p
in case 1,
q
in case 2,
n
in case 3, and 1 in case 4. Hence, in cases
1 and 2 we have indeed found a prime factor of
n
. So the success probability is in
fact 1
/
2 (as mentioned earlier).
