Detail publikace
Impact of Optimization and Parallelism on Factorization Speed of SIQS
Homoliak Ivan, Ing., Ph.D. (UITS FIT VUT)
Jaroš Jiří, doc. Ing., Ph.D. (UPSY FIT VUT)
Hanáček Petr, doc. Dr. Ing. (UITS FIT VUT)
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.
@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"
}