PollardRho.sagews

%html
<h1><center>Pollard's Rho Attack</center></h1>

Pollard's Rho Attack

Description. The RhoAttack procedure uses two inputs - the modulus R and the number of rounds that we choose to run the algorithm. The initial value used in the procedure is $x_0=2$ and the function f used to generate the sequence $x_i$ is $f(x)=x^2+2$. The Floyd's cycle finding algorithm is incorporated in the procedure.

def RhoAttack(R,rounds):
    a=2
    b=2
    for i in range (1,rounds):
        a=(a^2+1)% R ######## Floyd's Cycle Finding
        c=(b^2+1)% R ######## Floyd's Cycle Finding
        b=(c^2+1)% R ######## Floyd's Cycle Finding
        g=gcd(a-b,R)
        if (1<g and g<R):
                print ("Factor found in round {0}".format(i))
                return(g)
    print("The Pollard rho failed in {0}rounds".format(rounds))

R=129646944724184073871 ######## R is the modulus
p=RhoAttack(R,200000) ########## 200000 rounds
print('p=',p) ################## The prime p was found using Pollard's Rho Attack
print('q=',R/p) ################ The prime q is R/p since R is a product of two primes

Factor found in round 57290 p= 3458734771 q= 37483922101