|
|
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.
|