FactHacks 
RSA factorization in the real world 

Remainder treeGiven an integer n and a sequence X of positive integers, the remaindertree algorithm computes n mod X[0], n mod X[1], n mod X[2], etc. For long sequences the remaindertree algorithm is much faster than computing each remainder separately.The remaindertree algorithm is an important subroutine in the batchgcd algorithm. How it worksThe remaindertree algorithm uses the product tree of X as input:def remaindersusingproducttree(n,T): result = [n] for t in reversed(T): result = [result[floor(i/2)] % t[i] for i in range(len(t))] return result def remainders(n,X): return remaindersusingproducttree(n,producttree(X)) # example: print remainders(8675309,[11,13,17,19,23]) # output: [5, 6, 5, 4, 8] # double check: print [8675309 % p for p in [11,13,17,19,23]] # output: [5, 6, 5, 4, 8]This algorithm computes n mod X[0] and n mod X[1] by first computing n mod X[0]X[1] and then using the identities
sage: X = [41,43,47,53] sage: T = producttree(X); print T [[41, 43, 47, 53], [1763, 2491], [4391633]] sage: n = 31415926535 sage: r = [n] sage: r = [r[floor(i/2)] % T[2][i] for i in range(len(T[2]))]; print r [2575686] sage: r = [r[floor(i/2)] % T[1][i] for i in range(len(T[1]))]; print r [1706, 2483] sage: r = [r[floor(i/2)] % T[0][i] for i in range(len(T[0]))]; print r [25, 29, 39, 45] sage: # double check: sage: [n%x for x in X] [25, 29, 39, 45]Here 31415926535 is first reduced mod 4391633, producing 2575686; then 2575686 is reduced mod 1763 and 2491, producing 1706 and 2483; then 1706 is reduced mod 41 and 43, producing 25 and 29; then 2483 is reduced mod 47 and 53, producing 39 and 45. Version: This is version 2013.09.16 of the remainder.html web page. 