CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

| Download

18.783 Lecture 10: Simple implementation of Pollard's p-1 algorithm for factoring integers

Views: 122
License: AGPL3
Image: ubuntu2004
Kernel: SageMath 9.2
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 if b == 1: return 0 d = gcd(b.lift()-1,N) 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^208 * 3^48 * 5^4 * 7^78
p1=random_unsafe_prime(512) p2=random_prime(2^512,2^511) print(p1,p2) %time print(pollard_pm1(p1*p2))
15233457733737344526540743467037883976191131688801290976111437578683757334559566682309858873270788500743177592868343644160000000000000000000000000000000001 10805811561697681649612317523735012268289842506849046934843189811833967445914708434992672188003562368615706302208602535704643748161444047008827305924614487 15233457733737344526540743467037883976191131688801290976111437578683757334559566682309858873270788500743177592868343644160000000000000000000000000000000001 CPU times: user 3.29 ms, sys: 0 ns, total: 3.29 ms Wall time: 3.27 ms