FPGA Implementation of High Throughput Circuit for Trial Division by Small Primes

Trial division is the most straightforward way to determine the prime fac-tors of a number, but the execution time is exponentially dependent on the size of the number. We have developed a novel hardware architecture which performs trial division of large dividends by small prime divisors at a much higher throughput than previously reported architectures. Our de-sign is implemented in FPGA devices and provides a speed-up of between one and two orders of magnitude over an optimized software implemen-tation of the same algorithm. These results can be employed to speed up factoring algorithms like the quadratic sieve or number field sieve when implemented in reconfigurable computers.