Paper 2015/044

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

Binanda Sengupta and Abhijit Das


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.

Available format(s)
Publication info
Published elsewhere. Minor revision. Applied Mathematics and Computation
Integer FactorizationSievingMultiple-Polynomial Quadratic Sieve MethodNumber-Field Sieve MethodSingle Instruction Multiple DataStreaming SIMD ExtensionsAdvanced Vector Extensions
Contact author(s)
binujucse3 @ gmail com
2016-09-07: last of 5 revisions
2015-01-20: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.