Cofactorization on Graphics Processing Units

Andrea Miele; Joppe W.  Bos; Thorsten Kleinjung; Arjen K.  Lenstra

Paper 2014/397

Cofactorization on Graphics Processing Units

Andrea Miele, Joppe W. Bos, Thorsten Kleinjung, and Arjen K. Lenstra

Abstract

We show how the cofactorization step, a compute-intensive part of the relation collection phase of the number field sieve (NFS), can be farmed out to a graphics processing unit. Our implementation on a GTX 580 GPU, which is integrated with a state-of-the-art NFS implementation, can serve as a cryptanalytic co-processor for several Intel i7-3770K quad-core CPUs simultaneously. This allows those processors to focus on the memory-intensive sieving and results in more useful NFS-relations found in less time.

Note: We fixed a typo

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in CHES 2014
Keywords: Cofactorization GPUs Number Field Sieve
Contact author(s): andrea miele @ epfl ch
History: 2015-01-28: last of 3 revisions; 2014-05-30: received; See all versions
Short URL: https://ia.cr/2014/397
License: CC BY

BibTeX

@misc{cryptoeprint:2014/397,
      author = {Andrea Miele and Joppe W.  Bos and Thorsten Kleinjung and Arjen K.  Lenstra},
      title = {Cofactorization on Graphics Processing Units},
      howpublished = {Cryptology ePrint Archive, Paper 2014/397},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/397}},
      url = {https://eprint.iacr.org/2014/397}
}