Cryptography Reference
In-Depth Information
The storage requirements for this are simply storing the factors as we calculate them, and keeping track of
where we are. This won't take up too much space; thus, we need not be worried at this point.
As terrible as this may seem when compared to other algorithms in terms of time complexity, it has the ad-
vantage that it
always
works. There is no randomness in its operation, and it has a fixed, known upper-bound.
Few other algorithms discussed here have these properties. Also, other algorithms are not guaranteed to find
complete prime factorizations (whereas this one does) and often rely on trial division to completely factor num-
bers less than some certain bound.
3.3.2 Fermat's Difference of Squares
A method attributed to Fermat in 1643 [6] uses little more than normal integer arithmetic to siphon large factors
from numbers. In fact, it doesn't even use division.
3
The algorithm works from a fact often learned in basic algebra:
(
x
+
y
)(
x
-
y
) =
x
2
-
y
2
for any integers
x
and y. Fermat theorized using this to factor a number: If we can discover two squares such
that our target number
(a)
is equal to the difference of the two squares
(x
2
-
y
2
),
we then have two factors of the
n,
namely, (
x + y
) and (
x - y
).
Fermat's method just tries, essentially, to brute-force the answer by going through the possible squares and
testing them. The algorithm is written out concisely in Reference [15], although I have changed some of the
variable names for the following:
Fermat's Difference of Squares.
Take an integer, a, to factor. The goal is to calculate x
2
and y
2
so that (x +
y)(x - y) =
x
2
-
y
2
=
a
. In the following,
d
=
x
2
-
a
(which should, eventually, be equal to
y
2
).
1. Set
x
to be
rounding up (the ceiling function).
2. Set
t
= 2
x
+ 1.
3. Set
d
=
x
2
-
a
.
In the algorithm,
d
will represent
x
2
-
a,
the difference between our current estimate of
x
2
and
a,
and
thus will represent
y
2
when we have found the correct difference of the squares. This means that
d
is
positive (if
a
is not a perfect square in the first step) or zero (if
a
is a perfect square).
Make
t
the difference between
x
2
and the next square: (
x
+ 1)
2
=
x
2
+ 2
x
+ 1, and hence the difference
is 2
x
+ 1 to start with. The next square will be (
x
+ 2)
2
=
x
2
+ 4
x
+ 4, which is 2
x
+ 3 more than the
last. Following this trend (which can be verified using calculus), the difference between the squares
increases by 2 each time.
4. (a) If
d
is a square ( is an integer), then stop and go to Step 5, because the difference is a square.
(b) Set
d
to
d
+
t
. We are adding in the distance to the next
x
2
attempt to the difference of
x
2
-
a
.
This works because we already have (
x
+
c
)
2
-
a
(for some
c
, the current step), and we wish to calcu-
late [(
x
+
c
) + 1]
2
-
a
= (
x
+
c
)
2
+ 2(
x
+
c
) + 1 -
a
= (
x
+
c
)
2
-
a
+ 2
x
+ (2
c
+ 1) =
d
+ 2
x
+ 2
c
+ 1, the
next value of
d
. We use the value of
t
to stand in for 2
x
+ 2
c
+ 1, which increases by 2 every time,
since
c
increases by 1 with each step.
(c) Set
t
to
t
+ 2. The distance between the next pair of squares is increased by 2 each time.
(d) Go to Step 4a.
Search WWH ::
Custom Search