Doc. Ing. Jiří Jaroš, Ph.D.

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. 2016, roč. 14, č. 3, s. 51-58. ISSN 1690-4524.
Jazyk publikace:angličtina
Název publikace:Impact of Optimization and Parallelism on Factorization Speed of SIQS
Název (cs):Vliv optimalizace a paralelizace na faktorizační rychlost SIQS
Strany:51-58
Místo vydání:US
Rok:2016
Časopis:Journal on Systemics, Cybernetics and Informatics, roč. 14, č. 3, US
ISSN:1690-4524
Klíčová slova
Factorization, SIQS, Parallelism, OpenMP, Profiling, RSA cryptanalysis
Anotace
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.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=11267}
}

Vaše IPv4 adresa: 54.147.40.153
Přepnout na IPv6 spojení

DNSSEC [dnssec]