in the real world
Batch gcdGiven a sequence X of positive integers, the batch-gcd algorithm computes the sequence
The batch-gcd 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 batch-gcd 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.