# FactHacks

RSA factorization
in the real world

 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

## Remainder tree

Given an integer n and a sequence X of positive integers, the remainder-tree algorithm computes n mod X[0], n mod X[1], n mod X[2], etc. For long sequences the remainder-tree algorithm is much faster than computing each remainder separately.

The remainder-tree algorithm is an important subroutine in the batch-gcd algorithm.

## How it works

The remainder-tree 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
• n mod X[0] = (n mod X[0]X[1]) mod X[0],
• n mod X[1] = (n mod X[0]X[1]) mod X[1].
Example:
```     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.