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
-
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},
url = {https://eprint.iacr.org/2015/044}
}
