Cryptography Reference
In-Depth Information
provides the nontrivial factors.
Although the order of magnitude (see page 500) of Fermat factoring can
be shown to be
O
(
n
1
/
2
), Lehman has shown how to reduce the complexity
to
O
(
n
1
/
3
) when combined with trial division. This is all contained in [144],
complete with a computer program. There is also a method, from D.H. Lehmer,
for speeding up the Fermat method when all factors are of the form 2
k
+ 1 (see
[48]).
Euler's Factoring Method
This method only applies to integers of the
form,
n
=
x
2
+
ay
2
=
z
2
+
aw
2
,
where
x
=
w
. In other words,
n
can be written in two distinct ways
in this special form for a given nonzero value of
a
=
z
and
y
∈
Z
. Then
(
xw
)
2
ay
2
)
w
2
ay
2
w
2
(
z
2
n
)
y
2
(
zy
)
2
(mod
n
)
,
≡
(
n
−
≡−
≡
−
≡
from which we may have a factor of
n
, namely, provided that
xw
≡±
zy
(mod
n
).
In this case, the (nontrivial) factors of
n
are given by gcd(
xw
yz,n
).
The Euler method essentially is predicated on the congruence (C.2), but
unlike the Fermat method, not all integers have even one representation in
the form
n
=
x
2
+
ay
2
. In fact, the reader who is versed in some algebraic
number t
heo
ry will recognize these forms for
n
as norms from the quad
rati
c
field
±
n/a
(
√
−
Q
a
). It can be shown that Euler's method requires at most
steps when
a>
0.
Legendre's Factoring Method
This method is a precursor to what we
know today as
continued fraction methods for factorization
(see pages 496-498).
Legendre reasoned in the following fashion. Instead of looking at congruences
of the form (C.2), he looked at those of the form,
x
2
py
2
(mod
n
) for primes
p,
≡±
(C.3)
since a solution to (C.3) implies that
±
p
is a quadratic residue of all prime
factors of
n
.
For instance, if the residue is 2, then all prime factors of
n
are
congruent to
1 (mod 8) (see part (5) of Theorem A.19 on page 482). Therefore,
he would have halved the search for factors of
n
. Legendre applied this method
for various values of
p
, thereby essentially constructing a quadratic sieve
C.1
by
getting many residues modulo
n
. This allowed him to eliminate potential prime
divisors that sit in various linear sequences, as with the residue 2 example above.
He reali
ze
d that if he could achieve enough of these, he could eliminate primes
±
up to
√
n
, thereby effectively developing a test for primality!
The linchpin of Legendre's method is the continued fraction expansion of
√
n
since he was simply finding
small
residues modulo
n
. Legendre was essentially
C.1
A
sieve
may be regarded as any process whereby we find numbers via searching up to a
prescribed bound and eliminate candidates as we proceed until only the desired solution set
remains. A (general)
quadratic
sieve is one in which about half of the possible numbers being
sieved are removed from consideration, a technique used for hundreds of years as a scheme for
eliminating impossible cases from consideration.
Search WWH ::
Custom Search