Cryptography Reference
In-Depth Information
Now we look at one of the big guns in factoring. This requires some knowl-
edge of the theory of algebraic number fields (see [168]for instance).
The
following is taken from [170].
C.8
The General Number Field Sieve
The QS and MPQS studied above is
ba
sed upon the generation of many
smooth quadratic residues of
n
close to
√
n
, for a given composite
n
. Pollard
extrapolated this idea
in a
manuscript circulated in 1988, where he used cubic
integers (those in
[
√
−
2]) t
o
factor by attempting to generate many smooth
cubic residues of
n
close to
Z
√
n
. Later the idea was extended to the fifth degree
and used to factor the 9th Fermat number. Then he looked at the more general
idea of looking at composite
n
that are close to being powers in the sense that
3
n
=
r
t
−
s
for small
r,
|
s
|∈
N
and larger
t
∈
N
.
(C.8)
= 1 are called
Cunningham numbers
, which are
the subject of a project unto themselves in the history of factoring, called the
Cunningham project
(see [47]).
The
special number field sieve
dubbed as such by the authors of [50]
can factor integers of the form given in (C.8) in expected running time
L
n
(1
/
3
.
(32
/
9)
1
/
3
) (see Equation (A.16) on page 501 for a definition of the nota-
tion). The general number field sieve (GNFS) that we study below has expected
running time (for arbitrary integers
n
) given by
L
n
(1
/
3
,
1
.
9229), making it a
fast algorithm for arbitrary integers but the SNFS is faster for the integers of
the special type given above.
We now look at the GNFS and point out that despite its sophistication and
power, it is still based essentially on Fermat's difference-of-squares method.
|
|
The special case where
s
The setup and the goal
: Given a composite
n
to split, what we will
be setting out to achieve is the following.
We select an appropriate monic
polynomial
f
(
x
), irreducible over
Z
, where
m
∈
N
with
f
(
m
)
≡
0 (mod
n
), and
α
∈
C
arootof
f
. This setup allows us to define the natural homomorphism,
φ
:
Z
[
α
]
→
Z
/n
Z
, via
φ
(
α
)=
m,
which ensures that, for any
g
(
x
)
∈
Z
[
x
], we have
φ
(
g
(
α
))
≡
g
(
m
) (mod
n
).
such that both
g
∈
S
Thus, we will seek a set
S
of polynomials
g
over
Z
g
(
α
)=
[
α
], and
g
∈
S
β
2
∈
Z
g
(
m
)=
y
2
∈
Z
≡
. Then by setting
φ
(
β
)
x
(mod
n
) we get
g
≡
x
2
=
φ
(
β
)
2
φ
(
β
2
)
y
2
(mod
n
)
,
≡
≡
φ
g
(
α
)
g
(
m
)
≡
(C.9)
∈
S
g
∈
S
and we are back to Fermat's method in (C.2) on page 509, where we have a
nontrivial factor of
n
if
x
≡±
y
(mod
n
)! However, the devil is in the details so
here we go.
Search WWH ::
Custom Search