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

Finding smooth numbers

Algorithms such as QS and NFS factor N in four steps:
  • generating a huge pile of random-looking auxiliary numbers related to N;
  • relation search: searching through the pile of auxiliary numbers for numbers that are easy to factor;
  • linear algebra: using those factorizations to find a bunch of auxiliary numbers whose product is a square;
  • using this square to figure out the factorization of N.
Relation search is the most important step. The easiest numbers to factor are smooth numbers, i.e., numbers that factor into small primes. There are several ways to quickly find these smooth numbers (and their factorizations): The following Sage code uses batch trial division to find smooth numbers, and does a little extra work to make a list of the primes dividing each smooth number. The code also finds smooth numbers times squares, and suppresses squares of primes in the output, so each prime appears only once for each number.
     def oddpowers(P,x):
       if len(P) == 0: return [[],x,x]
       P = primesin(P,x)
       e,r,x = oddpowers([p*p for p in P],x)
       Q = primesin(P,r)
       return [Q,r / product(Q),x]
     
     def oddpowersineach(P,X):
       return [oddpowers(Q,x) for Q,x in zip(primesineach(P,X),X)]
     
     def easilyfactorable(x,pmodx):
       smoothpart = Mod(pmodx,x)^x.nbits()
       return (x / gcd(x,Integer(smoothpart))).is_square()
     
     def easyfactorizations(P,X):
       result = zip(X,remainders(product(P),X))
       result = [x for x,pmodx in result if easilyfactorable(x,pmodx)]
       return oddpowersineach(P,result)

     # example:
     print easyfactorizations([2,3,5,7],[50,157,266,377,490,605])
     # output: [[[2], 1, 50], [[2, 5], 1, 490], [[5], 121, 605]]

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