Fermat's Algorithm
12:58 AM
Muhammad Yusuf
, Posted in
We know that (a - b)(a + b) = a2 - b2.
Thus, given any number n if we can find a number a such that a2 - n is a perfect square, then we can write a2 - n = b2 so n = a2 - b2 = (a + b)(a - b). We
use the following algorithm.
Algorithm To
fact a large positive integer n, pick the smallest integer k such
that k2 > n. Find the first number in the sequence
k2 - n, (k + 1)2 - n, (k + 2)2 - n, . .
. ,
that is a perfect
square, say (k + m)2 - n = b2. Then, n = (k + m)2 - b2 =
(k + m + b)(k + m - b).
EXAMPLE Use
Fermat's Algorithm to factor 1073 and 931.
Solution: We can
find that 332 = 1089. We find that
332 - 1073 =
1089 - 1073 = 16 = 42
so 1073 = 332 - 42 = (33
+ 4)(33 - 4) = 37 X 29.
For 931, we find
that 312 = 961, and
312 - 931 = 30
322 - 931 = 93
332 - 931 = 158
342 - 931 = 225 = 152
Thus, 931 = 342 - 152 = (34
+ 15)(34 - 15) = 49 X 19.
EXERCISE Use
Fermat's Algorithm to factor the following numbers: 713, 1763, 851, 533.
Solution: We
have 272 = 729. We _nd that 272 - 713 =
16 = 42, so 713 =
(27 + 4)(27 - 4) =
31 X 23
We have 422 =
1764, so 422 - 1764 = 12. Thus, 1764 = 43 X 41.
We have 302 = 900
and 900 - 851 = 49, so 851 = (30 + 7)(30 - 7) = 37 X 23.
We have 242 = 576.
We _nd
242 - 533 = 43
252 - 533 = 92
262 - 533 = 143
272 - 533 = 196 = 142
Thus, 533 = (27 +
14)(27 - 14) = 41 X 13.
Observe that the
worst case for Fermat's Algorithm is when the factors of n are
far apart. As a side note, if Fermat used this method to factor 100895598169,
it would have taken 75419 iterations before he got to
3930602 - 100895598169
= 5053632
So, he
probably did it another way... but how?!?
0 Response to "Fermat's Algorithm"
Post a Comment