Paper 2015/044

Use of SIMD-Based Data Parallelism to Speed up Sieving in Integer-Factoring Algorithms

Binanda Sengupta and Abhijit Das

Abstract

Many cryptographic protocols derive their security from the apparent computational intractability of the integer factorization problem. Currently, the best known integer-factoring algorithms run in subexponential time. Efficient parallel implementations of these algorithms constitute an important area of practical research. Most reported implementations use multi-core and/or distributed parallelization. In this paper, we use SIMD-based parallelization to speed up the sieving stage of integer-factoring algorithms. We experiment on the two fastest variants of factoring algorithms: the number-field sieve method and the multiple-polynomial quadratic sieve method. Using Intel’s SSE2 and AVX intrinsics, we have been able to speed up index calculations in each core during sieving. This performance enhancement is attributed to a reduction in the packing and unpacking overheads associated with SIMD registers. We handle both line sieving and lattice sieving. We also propose improvements to make our implementations cache-friendly. We obtain speedup figures in the range 5--40%. To the best of our knowledge, no public discussions on SIMD parallelization in the context of integer-factoring algorithms are available in the literature.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. MINOR revision.Applied Mathematics and Computation
DOI
10.1016/j.amc.2016.08.019
Keywords
Integer FactorizationSievingMultiple-Polynomial Quadratic Sieve MethodNumber-Field Sieve MethodSingle Instruction Multiple DataStreaming SIMD ExtensionsAdvanced Vector Extensions
Contact author(s)
binujucse3 @ gmail com
History
2016-09-07: last of 5 revisions
2015-01-20: received
See all versions
Short URL
https://ia.cr/2015/044
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/044,
      author = {Binanda Sengupta and Abhijit Das},
      title = {Use of SIMD-Based Data Parallelism to Speed up Sieving in Integer-Factoring Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2015/044},
      year = {2015},
      doi = {10.1016/j.amc.2016.08.019},
      note = {\url{https://eprint.iacr.org/2015/044}},
      url = {https://eprint.iacr.org/2015/044}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.