Transcript ppt

Implementation of Pollard’s Rho Heuristic
Mid-term Exam
CSE670
Manoj Patil
March 03, 2004
Pseudo code explains the Pollard’s Rho procedure
 This method picks two modulo N congruent
numbers x and y.
i 1
x1  RANDOM (0, N  1)
y  x1
k 2
 Modulo N numbers:
We are considering a finite set of numbers that
is [0, n).
While TRUE
do
 if y = x mod n, that means that (y-x) is a
multiple of n
i  i 1
xi  ( xi21  1) mod N
d  GCD( y  xi , N )
if [( d  1)and (d  N )]
print d
if (i  k )
k  2k
y  xi
 If GCD [ (x-y), N ] is not equal to 1 or N,
then we just proved the
compositeness of the number N.
else
we will pick another random x
number to repeat the procedure.
 Next random number is chosen by a
polynomial ( x  a)
2
Top Level design for Pollard’s Rho procedure
Datapath for the Pollard’s Rho procedure
State Machine for the Pollard’s Rho procedure control unit
Simulation for the Pollard’s Rho procedure control unit