Cryptography Reference
In-Depth Information
Example
C.
4
Refer
ring
to Exa
mple
C.3, a
nd co
ntinui
ng the
calcul
ation
s, we
get
x
1
0
= 4
85
,
x
11
= 1312
,
x
12
= 1761
,
x
13
= 181
,
x
14
= 1152
,
x
15
= 2646
, and
x
16
= 2863
. We find that
gcd(
x
16
−
x
8
,n
) = gcd(493
,
3161) = 29
.
In Example C.4, we made only eight comparisons for
x
2
j
−
x
j
for
j
=
1
,
2
,
3
,...,
8. However, in Example C.3, we made nearly forty of them, since
we had to look at
x
j
9.
Now we illustrate the reason behind the name
Pollard rho method
. We take
n
= 29 as the modulus and
x
0
= 2 as the seed, then we proceed through the
Pollard rho method to achieve the following diagram.
−
x
i
for all
i
=
j
with 1
≤
i,j
≤
Diagram C.1
(
Pollard's Rho Method Illustrated
)
We take
n
=29
as the modulus and
x
0
=2
as the seed, then we proceed
through the Pollard rho method to achieve the following diagram.
.
x
7
≡
x
9
≡
7 (mod 29)
←
x
8
≡
21 (mod 29)
↑
x
6
≡
8 (mod 29)
↑
x
5
= 226
≡
23 (mod 29)
↑
x
4
= 3146
≡
14 (mod 29)
↑
x
3
= 677
≡
10 (mod 29)
↑
x
2
=26
↑
x
1
=5
↑
x
0
=2
Diagram C.1 shows us that when we reach
x
9
, then we are in the period
that takes us back and forth between the residue system of 7 and that of 21
modulo 29. This is the significance of the left pointing arrow from the position
of
x
8
back to the position of
x
7
, which is the same as the reside system of
x
9
.
This completes the circuit. The shape of the symbol is reminiscent of the Greek
symbol
ρ
,
rho
, pronounced
row
. The rho method was made twenty-five percent
faster by Brent [43]in 1980. His idea was to stop the algorithm when
x
j
for
j
=2
i
occurs, then consider
x
j
−
2
i
+1
. This has the
advantage of revealing the period length after far fewer arithmetic operations
2
i
−
1
<j
x
2
i
(mod
p
) for 3
·
≤
Search WWH ::
Custom Search