# FactHacks

RSA factorization
in the real world

 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()+*(t-1-i)
M = M.LLL()
Q = sum(z*(x/howclose)^i for i,z in enumerate(M))
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.