Factoring large numbers with programmable hardware
Hea Joung Kim, William H. Mangione-Smith · 2000
Most advanced forms of security for electronic transactions rely on the public-key cryptosystems developed by Rivest, Shamir and Adleman. Unfortunately, these systems are only secure while it remains difficult to factor large integers. The fastest published algorithms for factoring large numbers have a common sieving step. These sieves collect numbers that are completely factored by a set of prime numbers that are known in advance. Furthermore, the time required to execute these sieves currently dominates the runtime of the factoring algorithms. We show how the sieving process can be mapped to the Mojave configurable computing architecture. The mapping exploits unique properties of the sieving algorithms to fully utilize the bandwidth of a multiple bank interleaved memory system. The sieve has been mapped to a single programmable hardware unit on the Mojave computer, and achieves a clock frequency of 16 MHz. The full system implementation sieves over 28 times faster than an UltraSPARC Workstation. A simple upgrade to 8ns SRAMs will result in a speedup factor of 160.