Impact of Optimization and Parallelism on Factorization Speed of SIQS

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F16%3APU121568" target="_blank" >RIV/00216305:26230/16:PU121568 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.iiisci.org/Journal/CV$/sci/pdfs/SA559BN16.pdf" target="_blank" >http://www.iiisci.org/Journal/CV$/sci/pdfs/SA559BN16.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Impact of Optimization and Parallelism on Factorization Speed of SIQS

Popis výsledku v původním jazyce

This paper examines optimization possibilities of Self-Initialization 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 speed-up 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 speed-up.

Název v anglickém jazyce

Impact of Optimization and Parallelism on Factorization Speed of SIQS

Popis výsledku anglicky

This paper examines optimization possibilities of Self-Initialization 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 speed-up 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 speed-up.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/LQ1602" target="_blank" >LQ1602: IT4Innovations excellence in science</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of The 20th World Multi-Conference on Systemics, Cybernetics and Informatics

ISBN

978-1-941763-41-4

ISSN

1690-4524

e-ISSN

—

Počet stran výsledku

8

Strana od-do

51-58

Název nakladatele

The International Institute of Informatics and Systemics

Místo vydání

Orlando

Místo konání akce

USA, Orlando

Datum konání akce

5. 7. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—