Detail publikace

Parallelized Self-Initializing Quadratic Sieve using OpenMP

Originální název

Parallelized Self-Initializing Quadratic Sieve using OpenMP

Anglický název

Parallelized Self-Initializing Quadratic Sieve using OpenMP

Jazyk

en

Originální abstrakt

The paper deals with integer factorization. Factorization is popular and used method for RSA cryptanalysis. SIQS (Self-Initialization 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.

Anglický abstrakt

The paper deals with integer factorization. Factorization is popular and used method for RSA cryptanalysis. SIQS (Self-Initialization 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{BUT119931,
  author="Dominik {Breitenbacher} and Ivan {Homoliak} and Petr {Hanáček}",
  title="Parallelized Self-Initializing Quadratic Sieve using OpenMP",
  annote="The paper deals with integer factorization. Factorization is popular and used
method for RSA cryptanalysis. SIQS (Self-Initialization 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.",
  address="Trusted Network Solutions, a.s.",
  booktitle="Santa's Crypto Get-Together 2015",
  chapter="119931",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Trusted Network Solutions, a.s.",
  year="2015",
  month="december",
  pages="39--40",
  publisher="Trusted Network Solutions, a.s.",
  type="conference paper"
}