Conference paperBREITENBACHER Dominik, HOMOLIAK Ivan and HANÁČEK Petr. Parallelized SelfInitializing Quadratic Sieve using OpenMP. In: Santa's Crypto GetTogether 2015. Praha: Trusted Network Solutions, a.s., 2015, pp. 3940. ISBN 9788090425774.  Publication language:  english 

Original title:  Parallelized SelfInitializing Quadratic Sieve using OpenMP 

Title (cs):  Paralelizované SelfInitializing Quadratic Sieve užitím OpenMP 

Pages:  3940 

Proceedings:  Santa's Crypto GetTogether 2015 

Conference:  Santa's Crypto GetTogether 2016 

Place:  Praha, CZ 

Year:  2015 

ISBN:  9788090425774 

Publisher:  Trusted Network Solutions, a.s. 

Keywords 

Factorization, SIQS, Parallelization, OpenMP, RSA Cryptanalysis, Profilation 
Annotation 

The paper deals with
integer factorization. Factorization is popular and used method for RSA
cryptanalysis. SIQS (SelfInitialization Quadratic Sieve) is chosen as a
factorization method which is used in this paper. This method is chosen because
of its balance between difficulty to learn and implement and its factorization
capabilities. QS (Quadratic Sieve) is considered as the second fastest
factorization method and the fastest method to factorize numbers with less than
100 decimal digits (332 bits). SIQS is the most optimized version of QS. The
method was implemented and well documented in this work. Whereby, this paper
tries to fill the gap between theoretic description of the method and already
existing implementations. Although, SIQS is the fastest method up to 100
decimal 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 as
possible. Two of the possible ways of achieving a speedup are parallelization
and optimization which were used in this paper. OpenMP was chosen to
parallelize critical code segments. Also, the goal of this paper is to show how
easily is possible to use parallelization and thanks to detailed source code
analysis with optimization it is possible to reach large speedup. Method of
iterative optimization showed itself as a very effective tool. Using this
method the implementation of SIQS achieved almost 100x speedup and at some
parts of the code even more. 
BibTeX: 

@INPROCEEDINGS{
author = {Dominik Breitenbacher and Ivan Homoliak and Petr
Han{\'{a}}{\v{c}}ek},
title = {Parallelized SelfInitializing Quadratic Sieve
using OpenMP},
pages = {3940},
booktitle = {Santa's Crypto GetTogether 2015},
year = {2015},
location = {Praha, CZ},
publisher = {Trusted Network Solutions, a.s.},
ISBN = {9788090425774},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=11049}
} 
