FactHacks

RSA factorization
in the real world

Introduction
Sage
Basic subroutines:
Euclid
Product tree
Remainder tree
Weak primes:
Batch gcd
Fermat
Lattice
Small primes:
Batch trial division
rho
p-1
ECM
Small keys:
Smooth
QS
NFS

The p-1 method

     def p1exponent(cutoff):
       return lcm(range(1,cutoff))
     
     def p1(n,cutoff):
       # Pollard's p-1 method
       g = gcd(n,Integer(pow(2,p1exponent(cutoff),n))-1)
       return [g,n/g]
     
     # example:
     print p1(38568900844635025971879799293495379321,2^14)
     # output: [17495058332072672321, 2204559716953267001]

Version: This is version 2012.12.28 of the p1.html web page.