Cryptography Reference
In-Depth Information
Suppose we generate a sequence of random integers as mentioned, and we come across
a pair
m
q
,
m
r
such that
m
q
m
r
(mod
p
)
but
m
q
m
r
(mod
n
).
It follows then that the gcd of
m
q
m
r
and
n
; that is, (
m
q
m
r
,
n
), is a nontrivial divi-
sor of
n
, since
p
|(
m
q
m
r
)
but
(
m
q
m
r
).
The question is, how quickly can we find such a pair of numbers? As mentioned earlier,
this pair will surface relatively quickly if we generate the sequence randomly. We do this
in the following way:
n
• Start with an initial, randomly generated integer,
m
0
.
• Generate successive terms in the sequence by computing
m
i
m
i
1
2
+ 1 (mod
n
),
≤
m
i
<
n
This, of course, is not a random sequence, but it “appears to be,” and for our purposes it
will suffice. (See the chapter on cryptographic applications.) Once we have generated
m
2
i
in the sequence, we check the greatest common divisor of
m
2
i
m
i
and
n
; if we have
(
m
2
i
m
i
,
n
) =
d
,
0
1 <
d
<
n
,
then, as we mentioned before, we have found a nontrivial divisor of
n
.
E
XAMPLE
.
We will attempt to factor
n
= 356659679. Start with an initial value for
m
0
, say
1260345256, and proceed to generate numbers in the sequence.
m
1
= 1260345256
2
+ 1
72342499 (mod 356659679)
m
2
= 72342499
2
+ 1
278250477 (mod 356659679)
Now we can compute
(
m
2
m
1
, 356659679) = 1.
This fails to help us, so we continue to compute numbers in our sequence.
m
3
= 278250477
2
+ 1
66447814 (mod 356659679)
m
4
= 66447814
2
+ 1
333376938 (mod 356659679)
Now we compute (
m
4
m
2
,
n
), which again is 1. This gives us nothing, so we continue
to compute the next two values,
m
5
and
m
6
, then
m
7
and
m
8
, and so on. We obtain a nontrivial
Search WWH ::
Custom Search