Detail publikace

Impact of Optimization and Parallelism on Factorization Speed of SIQS

BREITENBACHER Dominik, HOMOLIAK Ivan, JAROŠ Jiří a HANÁČEK Petr. Impact of Optimization and Parallelism on Factorization Speed of SIQS. Journal on Systemics, Cybernetics and Informatics, roč. 14, č. 3, 2016, s. 51-58. ISSN 1690-4524. Dostupné z: http://www.iiisci.org/Journal/CV$/sci/pdfs/SA559BN16.pdf
Název česky
Vliv optimalizace a paralelizace na faktorizační rychlost SIQS
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Abstrakt

Tato práce se zabývá možnostmi optimalizace faktorizační metody Self-Initialization Quadratic Sieve (SIQS), jenž je upravenou verzí metody Quadratic Sieve. SIQS je obecně považováno za druhou nejrychlejší faktorizační metodu a nejrychlejší metodou pro faktorizaci čísel o 100 dekadických číslicích a méně. Přestože je SIQS nejrychlejší metodou do 100 dekadických číslic, není schopna efektivně pracovat v polynomiálním čase. Proto je nutné hledat možnosti, jak tuto metodu co nejvíce urychlit. Toho je možné docílit dvěma možnými způsoby. Jednou z nich je optimalizace kódu, druhou pak paralelizace. Obě možnosti jsou v této práci využity. Cílem práce je ukázat, jak je možné využít paralelizace SIQS a zároveň dosáhnout velkého urychlení díky detailní analýze kódu a jeho následnou optimalizací. Implementace probíhá ve dvou fázích. V první fázi je implementován kompletní a funkční algoritmus, zatím bez přihlédnutí k rychlosti vykonávání. Řešení z první fáze slouží jako referenční implementace s ověřenou funkčností pro následující experimenty. Optimalizace rychlosti je pak druhou fází implementace SIQS. V této fázi je využito metody iterační optimalizace pro nasazení a ověření vlivu modifikace v každém kroku. Použitím této metody je dosaženo více jak 200x urychlení oproti referenční verzi.

Rok
2016
Strany
51-58
Časopis
Journal on Systemics, Cybernetics and Informatics, roč. 14, č. 3, ISSN 1690-4524
Vydavatel
International Institute of Informacs and Systemics
BibTeX
@ARTICLE{FITPUB11267,
   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 = "51--58",
   journal = "Journal on Systemics, Cybernetics and Informatics",
   volume = 14,
   number = 3,
   year = 2016,
   ISSN = "1690-4524",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11267"
}
Nahoru