You are looking at a specific version 20160907:112842 of this paper. See the latest version.

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