Residue Number System - Integer Factorization

Integer Factorization

The RNS can improve efficiency of trial division. Let a semiprime. Let represent first N primes. Assume that, . Then, where . The method of trial division is the method of exhaustion, and the RNS automatically eliminates all Y and Z such that or, that is we only need to check

numbers below M. For example, N = 3, the RNS can automatically eliminate all numbers but

1,7,11,13,17,19,23,29 mod 30

or 73% of numbers. For N = 25 when are all prime numbers below 100, the RNS eliminates about 88% of numbers. One can see from the above formula the diminishing returns from the larger sets of moduli.