Cryptography Reference
In-Depth Information
p
+
q
p
−
q
t
2
s
2
. Obviously,
t
n
=
−
=
and
s
=
is one such solution, and we notice
2
2
t
2
s
2
,wehave
n
that
s
is small when
p
≈
q
. Conversely, if
n
=
−
=
(
t
+
s
)(
t
−
s
),
n
+
1
2
which factorizes
n
unless
t
=
s
+
1
=
. But in this case,
s
is not small at all
n
since
s
≈
2
. The algorithm works as follows: we try all possible
t
values starting
√
n
until
t
2
n
is a perfect square
s
2
. The complexity is
from
−
O
(
p
−
q
) arithmetic
operations.
The Fermat method is important because of the following observation: if we happen
to find
s
and
t
such that
s
2
t
2
(mod
n
) and
s
≡
≡±
t
(mod
n
), then gcd(
s
−
t
,
n
)isa
nontrivial factor of
n
: we notice that (
s
−
t
)(
s
+
t
) is a multiple of
n
. So if gcd(
s
−
t
,
n
)
=
1, it means that
s
+
t
is a multiple of
n
in which case we have
s
≡−
t
(mod
n
),
but this is not the case. If gcd(
s
−
t
,
n
)
=
n
,wehave
s
≡
t
(mod
n
), but this is not the
case either. Hence, gcd(
s
−
t
,
n
) is a proper factor of
n
. So we can try to factorize
n
by
looking for nontrivial
s
2
t
2
(mod
n
) relations.
≡
Modern methods use
factor bases
. A factor base is a set
B
of numbers
p
1
,...,
p
r
.
We say that a number
b
is a
B
-number if it can be factorized into a product of numbers
which are all in
B
. This factorization is assumed to be easy to perform. The goal of
factor base methods is to get several
B
-numbers
a
2
mod
n
. We obtain several relations
p
α
i
,
1
1
p
α
i
,
r
a
i
mod
n
=
···
. Once we get a little more than
r
equations, we consider the
r
vectors
A
i
=
α
i
,
1
,...,α
i
,
r
). Since we have a little more than
r
vectors of
r
coordinates,
they must be linearly dependent modulo 2. Hence we obtain a linear combination
i
∈
I
A
i
, the coefficients of which are all even. Therefore
i
∈
I
a
i
2
is congruent to a
perfect square
B
-number. This relationship is likely to be a nontrivial
s
2
(
t
2
(mod
n
)
relation which leads to a nontrivial factor of
n
. It is important to emphasize the three
phases of this method:
≡
p
α
i
,
r
(mod
n
) relations,
2. solve a linear system in GF(2) in order to get an even linear combination of
(
p
α
i
,
1
1
1. get several
a
i
≡
···
α
i
,
1
,...,α
i
,
r
) vectors,
3. from the corresponding
s
2
t
2
(mod
n
) relation, get a nontrivial factor of
n
.
≡
The way the first step is done highly depends on the factorization method.
7.2.5
The Quadratic Sieve
The Quadratic sieve is a factor base method. Let
m
be the integer part of
√
n
. We pick
at random
A
=
X
+
m
, where
X
is a small integer. We notice that
A
2
−
n
=
X
2
+
2
mX
m
, the most important term in this sum is 2
mX
which is
approximately 2
X
√
n
. So this is relatively small when compared to
n
. In particular we
may have
A
2
+
m
2
−
n
. Wh
e
n
X
<<
A
2
n
. Assuming that
A
2
mod
n
=
−
−
n
is
b
-smooth (namely all prime
factors
p
are lesser than
b
), we can factorize
A
2
−
n
with the factor base which consists
of
−
1 and all prime numbers lesser than
b
.(
−
1 is necessary in order to factorize negative
numbers.)
Search WWH ::
Custom Search