#First define the RhoAttack method / function
def RhoAttack(R,rounds):
    a=2
    b=2
    for i in range (1,rounds):
        a=(a^2+1)% R
        c=(b^2+1)% R
        b=(c^2+1)% R
        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)

#Create RSA Public Key, using a small prime as one of the factors.
p = next_prime(92059842)
q = next_prime(309483204982304982340)
R = p * q

RhoAttack(R,500000)

#This is effective on composite numbers having a small prime factor.
#Example, our R has the multiples, q and p where p is a small prime.
#Because we have a small prime p, this attack is able to discover it fairly quick.
#Watch as we make the prime bigger, this attack becomes less effective.
p = next_prime(2390482309753984754283745329230582350)
R = p * q
RhoAttack(R,500000)

#To defend against this attack, be sure to pick primes that are not small (to a computer, because a small prime to a computer, like our original p, appears large to a human).