FactHacks 
RSA factorization in the real world 

Batch gcdGiven a sequence X of positive integers, the batchgcd algorithm computes the sequence
The batchgcd algorithm is much faster than separately computing each gcd shown above, and is much faster than computing gcds of all pairs. This algorithm was used to test millions of deployed RSA keys in 2012, factoring tens of thousands of the keys. How it worksThe batchgcd algorithm has three steps:
def batchgcd_simple(X): R = remainders(product(X),[n^2 for n in X]) return [gcd(r/n,n) for r,n in zip(R,X)]A faster version observes that the nodes of the product tree used inside the remainder tree in the second step are simply the squares of the nodes in the product tree used in the first step: def batchgcd_faster(X): prods = producttree(X) R = prods.pop() while prods: X = prods.pop() R = [R[floor(i/2)] % X[i]**2 for i in range(len(X))] return [gcd(r/n,n) for r,n in zip(R,X)] # example: print batchgcd_simple([1909,2923,291,205,989,62,451,1943,1079,2419]) # output: [1909, 1, 1, 41, 23, 1, 41, 1, 83, 41] print batchgcd_faster([1909,2923,291,205,989,62,451,1943,1079,2419]) # output: [1909, 1, 1, 41, 23, 1, 41, 1, 83, 41] Version: This is version 2012.12.27 of the batchgcd.html web page. 