Shared18.783 Lecture 11 Pollard p-1.sagewsOpen in CoCalc
Author: Andrew Sutherland
Views : 5
Description: 18.783 Lecture 11 Pollard p-1
def pollard_pm1(N,B=0):
if not B: B=ceil(sqrt(N))
a = Integers(N).random_element()
b = a
for ell in primes(B):
q = 1
while q < N:
q *= ell
b = b^q
d = gcd(b.lift()-1,N)
if d == N: return 0
if d > 1: return d
return 0

def random_unsafe_prime(bits):
while true:
a=randint(0,bits)
b=randint(0,floor((bits-a)/log(3,2)))
c=randint(0,floor((bits-a-floor(b*log(3,2)))/log(5,2)))
d=floor((bits-a-floor(b*log(3,2))-floor(c*log(5,2)))/log(7,2))
p = 2^a*3^b*5^c*7^d+1
if is_prime(p): return p

factor(random_unsafe_prime(512)-1)

2^158 * 3^203 * 5^8 * 7^5
%time
p1=random_unsafe_prime(512)
p2=random_prime(2^512,2^511)
print p1,p2
print pollard_pm1(p1*p2)


5910093991871786246372853122054421164774790801528303596695923699714734369981041050978862340505600000000000000000000000000000000000000000000000000000000001 353240364992979750025389516399295551850493719196360166473354268047957883137419788008084692157612780327183572912588493205709522367539322707411575427483757 5910093991871786246372853122054421164774790801528303596695923699714734369981041050978862340505600000000000000000000000000000000000000000000000000000000001 CPU time: 0.51 s, Wall time: 0.51 s