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

Euclid's algorithm

Given two integers x and y, Euclid's algorithm computes the greatest common divisor of x and y, written gcd{x,y}. This is the largest integer that divides both x and y, or 0 if x and y are both 0.

For example, 20 divides both 120 and 220 (i.e., 120/20 and 220/20 are integers), and no larger integer divides both 120 and 220, so 20 = gcd{120,220}.

If two RSA public keys share a prime factor (but not both prime factors) then feeding the keys to Euclid's algorithm will produce exactly that prime factor: gcd{pq,pq'} = p if q and q' are different primes. Two research teams announced in 2012 that tens of thousands of RSA public keys on the Internet were factorable in this way (and even more efficiently factorable by batch gcd). Properly generated keys have negligible chance of sharing a prime factor, but these keys had been generated by bad random-number generators.

Euclid's algorithm is also the last step in many other factorization algorithms.

How it works

Euclid's algorithm replaces y by the remainder y mod x, then swaps x and y, then repeats. Eventually x reaches 0, and then the greatest common divisor is exactly y (or -y if y is negative): 
     def greatestcommondivisor(x,y):
       while x != 0: x,y = y%x,x
       return abs(y)

     # example:
     print greatestcommondivisor(4187,5989)
     # output: 53
     # double check:
     print gcd(4187,5989)
     # output: 53
An optimized version of this algorithm is built into Sage as gcd(x,y).

Example done by hand: 

     sage: x,y = 120,220
     sage: x,y = y%x,x; print x
     100
     sage: x,y = y%x,x; print x
     20
     sage: x,y = y%x,x; print x
     0
This computation finds gcd{120,220} = 20.

Larger example done by hand: 

     sage: x,y = 26167,37627
     sage: x,y = y%x,x; print x
     11460
     sage: x,y = y%x,x; print x
     3247
     sage: x,y = y%x,x; print x
     1719
     sage: x,y = y%x,x; print x
     1528
     sage: x,y = y%x,x; print x
     191
     sage: x,y = y%x,x; print x
     0
This computation finds gcd{26167,37627} = 191.
Version: This is version 2012.12.27 of the euclid.html web page.