Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / Integer Factorization, Sieving, Multiple-Polynomial Quadratic Sieve Method, Number-Field Sieve Method, Single Instruction Multiple Data, Streaming SIMD Extensions, Advanced Vector Extensions

Original Publication (with minor differences): Applied Mathematics and Computation
DOI:
10.1016/j.amc.2016.08.019

Date: received 19 Jan 2015, last revised 7 Sep 2016

Contact author: binujucse3 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160907:112842 (All versions of this report)

Short URL: ia.cr/2015/044

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]