Pollard P-1 .sagews

Pollard's (P-1) Attack

def pminone(R,a,rounds): 
    b = a - 1
    for j in range(1,rounds+1):
        b= (ZZ(power_mod(b+1,j,R))-1) %R
        p = gcd(b,R)
        if p==R:
            print("Pollard p-1 attack fails")
            return None
        elif p>1:
            print("Discovered in round {0}".format(j))
            return p
    print ("Not found in {0}".format(rounds))
    return None

R = 15056208191
p=pminone(R,37462,3463)
print("One of the prime factors of R is", p)

Discovered in round 3463 One of the prime factors of R is 34631