Another Attempt To Sieve With Small Chips---Part II: Norm Factorization

Rainer Steinwandt
Florida Atlantic University

When implementing the sieving step of the Number Field Sieve (NFS) in hardware, the question of how to recover prime factors found during sieving arises. The logic for logging and recovering large prime factors can significantly add to the layout complexity. The talk discusses a hardware design that for NFS parameters of interest tries to recover all prime factors with an optimized implementation of the Elliptic Curve Method (ECM). It is assumed that the actual sieving does not log any prime factors, and that occurring norms are to be split in a postprocessing phase without significantly affecting the total sieving time.

For the relation collection step expected for a 1024 bit factorization, the performance of the proposed device is expected to suffice, e.g., to replace the complete logging part in TWIRL by an off-wafer postprocessing. According to a preliminary analysis, for such a parameter choice an implementation seems doable with current fab technology at very moderate cost.

(Based on joint work with Willi Geiselmann, Fabian Januszewski, Hubert Köpfer and Jan Pelzl.)

Presentation (PDF File)

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