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

Lattice techniques

An algorithm by Coppersmith finds p very quickly if p has about half as many bits as N and half of the leading bits of p are known. For Fermat's factorization method it was necessary for p and q to share leading bits; Coppersmith's method doesn't have this restriction.

How it works

This is actually a simpler, faster algorithm by Howgrave-Graham.
     def lattice(n,nearp,howclose,t,k):
       R.<x> = PolynomialRing(ZZ)
       f = howclose*x+nearp
       M = matrix(t)
       for i in range(t):
         M[i] = (f^i*n^max(k-i,0)).coeffs()+[0]*(t-1-i)
       M = M.LLL()
       Q = sum(z*(x/howclose)^i for i,z in enumerate(M[0]))
       for r,multiplicty in Q.roots():
         if nearp+r > 0:
           g = gcd(n,nearp+r)
           if g > 1: return [g,n/g]
       return [1,n]
     
     # examples:
     print lattice(314159265358979323,317213000,1000,5,2)
     # output: [317213509, 990371647]
     print lattice(314159265358979323,317210000,10000,40,20)
     # output: [317213509, 990371647]

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