Cryptography Reference
In-Depth Information
Appendix C: Factoring Large Integers
Given the importance of factoring, or rather the diGculty thereof, in the
security of RSA and other cryptosystems, it is worth our having a closer look
at the issue to which we devote this appendix.
On page 165, we mentioned the integer factoring problem (IFP), but did not
delve into its meaning. Now we make this explicit.
The Integer Factoring Problem — (IFP)
Given
n
∈
N
, find primes
p
j
for
j
=1
,
2
,...,r
∈
N
with
p
1
<p
2
<
···
<p
n
such that
r
p
e
j
.
n
=
j
=1
A simpler problem than the IFP is the notion of
splitting
of
n
∈
N
, which
means the finding of factors
r, s
s
such that
n
=
rs
.Of
course, with an RSA modulus, splitting and the IFP are the same thing. Yet, in
order to solve the IFP for any integer, one merely splits
n
, then splits
n/r
and
s
if they are both composite, and so on until we have a complete factorization.
First, we look at some older methods that still inspire the methods of today.
∈
N
such that 1
<r
≤
C.1 Classical Factorization Methods
Trial Division
The oldest method of spl
it
ting
n
is
trial division
by which
we mean dividing
n
by all primes up to
√
n
.For
n<
10
8
, or within that
neighborhood, this is not an unreasonable method in our computer-savvy world.
However, for larger integers, we need more elaborate methods.
Fermat Factoring
In 1643, Fermat discovered a factoring scheme bas
ed
upon the following insight. If
n
=
rs
is an odd natural number with
r<
√
n
,
then
n
=
s
+
r
2
2
s
2
−
r
=
a
2
b
2
.
−
−
(C.1)
2
Therefore, in order to split
n
, we need only investigate the values,
√
n
√
n
x
=
a
2
−
n
for
a
=
+1
,
+2
,...,
(
n
−
1)
/
2
,
until a perfect square is found. This is now called Fermat's
difference-of-squares
factoring method
. It has been rediscovered many times and used as a basis for
many modern factoring techniques since essentially we are looking at solutions
of
x
2
y
2
(mod
n
) with
x
≡
≡±
y
(mod
n
)
,
(C.2)
and
gcd(
x
±
y,n
)
Search WWH ::
Custom Search