Cryptography Reference
In-Depth Information
E
XAMPLES
.
We will use Fermat factorization to factor the following integers:
a) 3811. We begin with
m
= 62 > 61.73
3811 and look for perfect squares in the sequence
√
62
2
3811 = 3844
3811 = 33
63
2
3811 = 3969
3811 = 158
64
2
3811 = 4096
3811 = 285
65
2
3811 = 4225
3811 = 414
66
2
3811 = 4356
3811 = 545
67
2
3811 = 4489
3811 = 678
68
2
3811 = 4624
3811 = 813
69
2
3811 = 4761
3811 = 950
70
2
3811 = 1089 = 33
2
Thus we obtain a factorization of 3811 by noting that
3811 = 4900
3811 = 70
2
33
2
= (70 + 33)(70
33) = 103
37.
b) 6077
Begin with
m
= 78 > 77.95
√
6077 and examine the sequence
78
2
6077 = 6084
6077 = 7
79
2
6077 = 6241
6077 = 164
80
2
6077 = 6400
6077 = 323
81
2
6077 = 6561
6077 = 484 = 22
2
And we see that 6077 = 81
2
22
2
= (81 + 22)(81
22) = 103
59.
c) 11
Begin with
m
= 4 > 3.32
√
11 and examine the sequence
4
2
11 = 16
11 = 5
5
2
11 = 25
11 = 14
11 = 25 = 5
2
And here we obtain the trivial factorization 11 = 6
2
6
2
11 = 36
5
2
= (6 + 5)(6
5) = 11
1.
Hopefully you can see how inefficient this method of factoring can be. It can be even
worse than the trial division method, for trial division never has to test more than
√
n
inte-
gers, but with the Fermat method it may be necessary to search as many as (
n
+ 1)/2
√
n
integers before the procedure is guaranteed to terminate. As the integer
n
gets larger, the quan-
tity (
. (See Table 12.1.)
The Fermat factorization method is most efficient when the two factors of
n
+ 1)/2
√
n
becomes much larger than
√
n
n
, say
2
2
= (
n
=
ab
=
x
y
x
+
y
)(
x y
)
Search WWH ::
Custom Search