FactHacks 
RSA factorization in the real world 

Product and product treeOne can easily use Python's builtin reduce operation to compute the product of all the integers in a sequence. This becomes very slow for long sequences:sage: # AMD A105800K sage: time x = reduce(lambda x,y:x*y,range(1,10000)) Time: CPU 0.04 s, Wall: 0.04 s sage: time x = reduce(lambda x,y:x*y,range(1,100000)) Time: CPU 4.11 s, Wall: 4.11 s sage: time x = reduce(lambda x,y:x*y,range(1,1000000)) Time: CPU 911.28 s, Wall: 911.29 s sage:But there's a much faster way to compute products of long sequences: sage: # same AMD A105800K sage: time x = product(list(range(1,10000))) Time: CPU 0.02 s, Wall: 0.02 s sage: time x = product(list(range(1,100000))) Time: CPU 0.46 s, Wall: 0.46 s sage: time x = product(list(range(1,1000000))) Time: CPU 17.41 s, Wall: 17.40 s How it worksThis fast product function simply multiplies pairs, then pairs of pairs, etc.:def product(X): if len(X) == 0: return 1 while len(X) > 1: X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)] return X[0] # example: print product([314,159,265,359,897]) # output: 4260489878970 # double check: print 314*159*265*359*897Example done by hand: sage: X = list(range(1,20)); print X [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] sage: X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)]; print X [2, 12, 30, 56, 90, 132, 182, 240, 306, 19] sage: X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)]; print X [24, 1680, 11880, 43680, 5814] sage: X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)]; print X [40320, 518918400, 5814] sage: X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)]; print X [20922789888000, 5814] sage: X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)]; print X [121645100408832000]This is much faster than multiplying sequentially first times second times third etc., for essentially the same reason that merge sort is much faster than insertion sort. This product function uses Sage's builtin prod function to multiply pairs. Actually, prod can multiply sequences of any length, and works the same way as product, so you can simply write prod and skip product. Product treesThe list of intermediate results in the product function is called a product tree:def producttree(X): result = [X] while len(X) > 1: X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)] result.append(X) return result # example: print producttree([10,20,30,40,50,60]) # output: [[10, 20, 30, 40, 50, 60], [200, 1200, 3000], [240000, 3000], [720000000]]Traditionally this tree is visualized with the inputs at the leaves, the product at the root, and intermediate products at intermediate nodes. For example, the product tree of 3,1,4,1,5,9,2,6 has 3,1,4,1,5,9,2,6 as leaves at the bottom; 3,4,45,12 as the next layer; 12,540 as the next layer; and 6480 as the root. Each nonleaf node is the product of its two children: for example, the 540 node is the parent of the 45 node and the 12 node. Version: This is version 2012.12.27 of the product.html web page. 