Implementation of the "rho", "p-1" and the Elliptic Curve Methods of Factoring in Reconfigurable Hardware

Kris Gaj
George Mason University

Three special purpose factoring methods,
"rho", "p-1", and ECM, have been implemented in
reconfigurable hardware, and optimized for the
minimum product of the execution time and area.
These methods can be applied in series
to the outputs of the sieving phase of
the Number Field Sieve in order to fully factor
large integers that are already likely to contain
only relatively small prime factors.
All three circuits have been ported to SRC 6,
a high-performance reconfigurable computer
based on FPGAs, and the obtained results compared
to the results of highly optimized software implementations.
All three designs have been also implemented as
ASICs, and the performance to cost ratio
compared among the FPGA, ASIC and the microprocessor
Using ECM as an example, a high level language, MAP C,
has been applied to programming FPGA-based reconfigurable
computers and compared with traditional implementation approaches,
based on hardware description languages,
in terms of computational efficiency and development time.

Audio (MP3 File, Podcast Ready) Presentation (PDF File)

Back to Workshop IV: Special purpose hardware for cryptography: Attacks and Applications