Publication Details
Parallelized Self-Initializing Quadratic Sieve using OpenMP
Homoliak Ivan, doc. Ing., Ph.D. (DITS)
Hanáček Petr, doc. Dr. Ing. (DITS)
Factorization, SIQS, Parallelization, OpenMP, RSA Cryptanalysis, Profilation
The paper deals withinteger factorization. Factorization is popular and used method for RSAcryptanalysis. SIQS (Self-Initialization Quadratic Sieve) is chosen as afactorization method which is used in this paper. This method is chosen becauseof its balance between difficulty to learn and implement and its factorizationcapabilities. QS (Quadratic Sieve) is considered as the second fastestfactorization method and the fastest method to factorize numbers with less than100 decimal digits (332 bits). SIQS is the most optimized version of QS. Themethod was implemented and well documented in this work. Whereby, this papertries to fill the gap between theoretic description of the method and alreadyexisting implementations. Although, SIQS is the fastest method up to 100decimal digits, it can't be effectively used to work in polynomial time. Therefore,it is desirable to look up for options how to speedup the method as much aspossible. Two of the possible ways of achieving a speedup are parallelizationand optimization which were used in this paper. OpenMP was chosen toparallelize critical code segments. Also, the goal of this paper is to show howeasily is possible to use parallelization and thanks to detailed source codeanalysis with optimization it is possible to reach large speedup. Method ofiterative optimization showed itself as a very effective tool. Using thismethod the implementation of SIQS achieved almost 100x speedup and at someparts of the code even more.
@inproceedings{BUT119931,
author="Dominik {Breitenbacher} and Ivan {Homoliak} and Petr {Hanáček}",
title="Parallelized Self-Initializing Quadratic Sieve using OpenMP",
booktitle="Santa's Crypto Get-Together 2015",
year="2015",
pages="39--40",
publisher="Trusted Network Solutions, a.s.",
address="Praha",
isbn="978-80-904257-7-4"
}