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

Product and product tree

One can easily use Python's built-in reduce operation to compute the product of all the integers in a sequence. This becomes very slow for long sequences: 
     sage: # AMD A10-5800K
     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 A10-5800K
     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 works

This 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*897
Example 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 built-in 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 trees

The 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 non-leaf 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.