Cryptography Reference
In-Depth Information
primes
p
in the factor base for which
n
is a quadratic residue modulo
p
. The
following gives a small illustration of the continued fraction algorithm, called
CFRAC by some users.
F
{
}
Exampl
e
C.1
Let
n
= 6109. Our factor base will be
=
3
,
5
,
11
,
13
,
31
,
37
.
√
n
Since
= 78, then we compute the following table (where
J
= 3).
1)
j
Q
j
j P
j
q
j
A
j
−
1
(
−
v
j
0
0
78
1
1
(0
,
0
,
0
,
0
,
0
,
0
,
0)
1
78
6
78
−
25
(1
,
0
,
0
,
0
,
0
,
0
,
0)
2
72
4
469
37
(0
,
0
,
0
,
0
,
0
,
0
,
1)
3
76
17
1954
−
9
(1
,
0
,
0
,
0
,
0
,
0
,
0)
We have a set
such that
S
v
i,j
≡
0 (mod 2) for each
i
=0
,
1
,...,
6
.
j
∈
S
This set is
S
=
{
1
,
3
}
for which we have
Q
1
=
−
5
2
,
Q
3
=
−
3
2
,
A
0
= 78 and
A
2
= 1954. We compute
j
∈
S
A
j
−
1
≡
5796 (mod 6109) and since
y
2
=
j
x
2
=
j
A
j
−
1
≡
Q
j
=15
2
(mod
n
)
,
∈
S
∈
S
then we check gcd(
x
−
5796
,
6109) = 41, and gcd(
x
+
y,n
) = gcd(15 + 5796
,
6109) = 149. Thus, we
have factored
n
=41
±
y,n
). We compute that both gcd(
x
−
y,n
) = gcd(15
·
149.
The CFRAC algorithm was developed by Brillhart and Morrison in the early
1970s (see [173]). It is widely acclaimed to be the very first eGcient
general
factorization algorithm put into use. It is subexponential time (see page 501),
which essentially means that if the running time to factor
n
is
n
a
, then
a
slowly
decreases as
n
→∞
.
In 1974, Pollard published a factorization scheme (see [189]), that utilizes
Euler's generalization of Fermat's little theorem (see Theorem A.14 on page
479). He reasoned that if (
p
1)
n
where
p
is prime, then
p
(
t
n
−
−
1) provided
that
p
t
, which follows from Euler's theorem, so
p
may be found by employing
Eulcild's algorithm (see Theorem A.3 on page 470). The following is taken from
[169].
Search WWH ::
Custom Search