# 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, n mod X, n mod X, 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 and n mod X by first computing n mod XX and then using the identities
• n mod X = (n mod XX) mod X,
• n mod X = (n mod XX) mod X.
Example:
```     sage: X = [41,43,47,53]
sage: T = producttree(X); print T
[[41, 43, 47, 53], [1763, 2491], ]
sage: n = 31415926535
sage: r = [n]
sage: r = [r[floor(i/2)] % T[i] for i in range(len(T))]; print r

sage: r = [r[floor(i/2)] % T[i] for i in range(len(T))]; print r
[1706, 2483]
sage: r = [r[floor(i/2)] % T[i] for i in range(len(T))]; 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.