Nios II hardware acceleration of the epsilon quadratic sieve algorithm
Uwe H. Meyer-Baese, Guillermo Botella, Encarnación Castillo, Antonio García · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2010
The quadratic sieve (QS) algorithm is one of the most powerful algorithms to factor large composite primes used to break RSA cryptographic systems. The hardware structure of the QS algorithm seems to be a good fit for FPGA acceleration. Our new ε-QS algorithm further simplifies the hardware architecture making it an even better candidate for C2H acceleration. This paper shows our design results in FPGA resource and performance when implementing very long arithmetic on the Nios microprocessor platform with C2H acceleration for different libraries (GMP, LIP, FLINT, NRMP) and QS architecture choices for factoring 32-2048 bit RSA numbers.