Doc. Ing. Jiří Jaroš, Ph.D.
BREITENBACHER Dominik, HOMOLIAK Ivan, JAROŠ Jiří and HANÁČEK Petr. Impact of Optimization and Parallelism on Factorization Speed of SIQS. In: Proceedings of The 20th World MultiConference on Systemics, Cybernetics and Informatics. Orlando: The International Institute of Informatics and Systemics, 2016, pp. 5562. ISBN 9781941763414.  Publication language:  english 

Original title:  Impact of Optimization and Parallelism on Factorization Speed of SIQS 

Title (cs):  Vliv optimalizace a paralelizace na faktorizační rychlost SIQS 

Pages:  5562 

Proceedings:  Proceedings of The 20th World MultiConference on Systemics, Cybernetics and Informatics 

Conference:  The 20th World MultiConference on Systemics, Cybernetics and Informatics 

Series:  Volume I 

Place:  Orlando, US 

Year:  2016 

ISBN:  9781941763414 

Publisher:  The International Institute of Informatics and Systemics 

Files:  

 Keywords 

Factorization, SIQS, Parallelism, OpenMP, Profiling, RSA cryptanalysis

Annotation 

This paper examines optimization possibilities of SelfInitialization Quadratic Sieve (SIQS), which is enhanced version of Quadratic Sieve factorization method.SIQS is considered the second fastest factorization method at all and the fastest one for numbers shorter than 100 decimal digits, respectively.Although, SIQS is the fastest method up to 100 decimal digits, it cannot be effectively utilized to work in polynomial time.Therefore, it is desirable to look for options how to speed up the method as much as possible.Two feasible ways of achieving it are code optimization and parallelism.Both of them are utilized in this paper.The goal of this paper is to show how it is possible to take advantage of parallelism in SIQS as well as reach a large speedup thanks to detailed source code analysis with optimization.Our implementation process consists of two phases.In the first phase, the complete algorithm is implemented in the simplest way which does not consider any requirements for execution speed.The solution from the first phase serves as the reference implementation for further experiments.An improvement of factorization speed is performed in the second phase of the SIQS implementation, where we use the method of iterative modifications in order to examine contribution of each proposed step.The final optimized version of the SIQS implementation has achieved over 200x speedup.

BibTeX: 

@INPROCEEDINGS{
author = {Dominik Breitenbacher and Ivan Homoliak and Ji{\v{r}}{\'{i}}
Jaro{\v{s}} and Petr Han{\'{a}}{\v{c}}ek},
title = {Impact of Optimization and Parallelism on Factorization
Speed of SIQS},
pages = {5562},
booktitle = {Proceedings of The 20th World MultiConference on Systemics,
Cybernetics and Informatics},
series = {Volume I},
year = {2016},
location = {Orlando, US},
publisher = {The International Institute of Informatics and Systemics},
ISBN = {9781941763414},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en.iso88592?id=10933}
} 
