Algebra
Applied Mathematics
Calculus and Analysis
Discrete Mathematics
Foundations of Mathematics
Geometry
History and Terminology
Number Theory
Probability and Statistics
Recreational Mathematics
Topology
 |
|
factorization
method. The first is the idea of iterating a formula until it falls into a cycle.
Let 
, where 
is the number to
be factored and 
and 
are its unknown
prime factors. Iterating the formula
) for any
initial value 
will produce
a sequence of number that eventually fall into a cycle. The expected time until the
s become cyclic and the expected length
of the cycle are both proportional to 
.
with 
and 
(mod 
) corresponds uniquely
to the pair of values (
), 
). Furthermore, the sequence
of 
s follows exactly the same formula
modulo 
and 
, i.e.,
![[x_n (mod p)]^2+a (mod p)](/images/equations/PollardRhoFactorizationMethod/Inline22.gif)
![[x_n (mod q)]^2+a (mod q).](/images/equations/PollardRhoFactorizationMethod/Inline25.gif)
) will fall into
a much shorter cycle of length on the order of 
. It can
be directly verified that two values 
and 
have the same
value (mod 
), by computing
.
to 
for all 
. A different method is used in 
algorithm can
be very slow.
Contact the MathWorld Team
