Cryptography Reference
In-Depth Information
(
√
p
+
/
=
≡
(
)
≤
=
)
i
j
l
l
2
i
and hence
s
i
s
2
i
mod
p
, with
i
k
O
. Thus Pollard's
(
s
2
i
−
s
i
,
)
=
,
,...
rho method proceeds by computing the sequence gcd
n
for
i
1
2
,
(
√
p
n
1
/
4
and it should output a nontrivial factor of
n
in
O
)
=
O
(
)
steps which, if
c
n
1
/
4
polylog
.Thisisa
heuristic estimate and a rigorous analysis of the algorithm remains to be done. This
estimate means that the rho method will find a
t
-bit prime factor of
n
with roughly
the same work needed to find a
t
O
(
polylog
(
n
))
=
O
(
len
(
n
)
)
gives a complexity of
O
(
(
n
))
2-bit prime factor by trial division. The smallest
prime factor
p
will usually be found first, although this may not be always the case
since the algorithm is probabilistic. The running time is more
de
pendent on the size
of
p
than on the size of the integer
n
itself and in some cases
√
p
can be substantially
smaller than
n
1
/
4
.
The preceding discussion leads to the following function that implements the rho
method in Maple. The input is the (positive) integer to be factored and the output (if
successful) a nontrivial factor of
n
in case
n
is composite or
n
itself if
n
is prime.
It may happen that, even if
n
is composite, the first factor greater than 1 that the
algorithm finds is
n
itself and, in that case—which is unlikely if
n
is large—the
procedure will ask the user whether to continue the algorithm restarting with a new
s
and a new
F
, or to stop the computation.
/
> RhoFactor := proc(n::posint)
uses RandomTools;
local b, s, u, v, f, g, finished, a;
if isprime(n) orn=1then
return n
end if;
randomize();
finished := false;
while not finished do
b := Generate(integer(range = 1 .. n-3));
s := Generate(integer(range = 0 .. n-1));
f := x -> 'mod'(xˆ2+b, n);
u:=s;v:=s;g:=1;
while g=1do
u := f(u);
v := f(f(v));
g := igcd(u-v, n)
end do;
ifg=nthen
a := readstat("No factor found, continue?, y/n");
ifa=ythen
print("Computation proceeds with new seeds")
else
finished := true;
print("Computation interrupted")
end if
else
return g
end if
end do
end proc:
Example 6.10
As a first historical example, let us try
M
67
:
> RhoFactor(2ˆ67-1);
193707721
The factorization is obtained instantaneously in this case.
