A parallel variant of LDSieve for the SVP on lattices

Artur Mariano, Thijs Laarhoven, Christian Bischof

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Citaten (Scopus)

Samenvatting

In this paper, we propose a parallel implementation of LDSieve, a recently published sieving algorithm for the SVP, which achieves the best theoretical complexity to this day, on parallel shared-memory systems. In particular, we propose a scalable parallel variant of LDSieve that is probabilistically lock-free and relaxes the properties of the algorithm to favour parallelism. We use our parallel variant of LDSieve to answer a number of important questions pertaining to the algorithm. In particular, we show that LDSieve scales fairly well on shared-memory systems and uses much less memory than HashSieve on random lattices, for the same or even less execution time.

Originele taal-2Engels
Titel2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings
Plaats van productiePiscataway
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's23-30
Aantal pagina's8
ISBN van elektronische versie978-1-5090-6058-0
ISBN van geprinte versie978-1-5090-6059-7
DOI's
StatusGepubliceerd - 26 apr 2017
Extern gepubliceerdJa
Evenement25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017) - St. Petersburg, Rusland
Duur: 6 mrt 20178 mrt 2017
Congresnummer: 25
https://www.pdp2017.org

Congres

Congres25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017)
Verkorte titelPDP 2017
LandRusland
StadSt. Petersburg
Periode6/03/178/03/17
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'A parallel variant of LDSieve for the SVP on lattices'. Samen vormen ze een unieke vingerafdruk.

Citeer dit