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. In: Proceedings of The 20th World Multi-Conference on Systemics, Cybernetics and Informatics. Orlando: The International Institute of Informatics and Systemics, 2016, s. 55-62. ISBN 978-1-941763-41-4.
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:55-62
Sborník:Proceedings of The 20th World Multi-Conference on Systemics, Cybernetics and Informatics
Konference:The 20th World Multi-Conference on Systemics, Cybernetics and Informatics
Řada knih:Volume I
Místo vydání:Orlando, US
Rok:2016
ISBN:978-1-941763-41-4
Vydavatel:The International Institute of Informatics and Systemics
Soubory: 
+Typ Jméno Název Vel. Poslední změna
iconwmsci2016.pdf236 KB2016-07-19 11:15:31
^ Vybrat vše
S vybranými:
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:
@INPROCEEDINGS{
   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 = {55--62},
   booktitle = {Proceedings of The 20th World Multi-Conference on Systemics,
	Cybernetics and Informatics},
   series = {Volume I},
   year = {2016},
   location = {Orlando, US},
   publisher = {The International Institute of Informatics and Systemics},
   ISBN = {978-1-941763-41-4},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=10933}
}

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

DNSSEC [dnssec]