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 quadratic sieve

     def qs_basic(N,differences,y):
       X = [Integer(a^2-N) for a in range(sqrt(N)+1,sqrt(N)+differences)]
       P = list(primes(2,y))
       F = easyfactorizations(P,X)
       M = matrix(GF(2),len(F),len(P),lambda i,j:P[j] in F[i][0])
       for K in M.left_kernel().basis():
         x = product([sqrt(f[2]+N) for f,k in zip(F,K) if k==1])
         y = sqrt(product([f[2] for f,k in zip(F,K) if k==1]))
         return [gcd(N,x - y),gcd(N,x + y)]
       return [1,N]

     # example:
     print qs_basic(275801,1000,20)
     # output: [389, 709]
Larger example:
     time print qs_basic(314159265358979323,500000,1000)

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