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. In: Proceedings of The 20th World Multi-Conference on Systemics, Cybernetics and Informatics. WMSCI 2016 - 20th World Multi-Conference on Systemics, Cybernetics and Informatics, Proceedings, roč. 1. Orlando: The International Institute of Informatics and Systemics, 2016, s. 55-62. ISBN 978-1-941763-47-6. 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 ve sborníku konference
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
55-62
Časopis
Journal on Systemics, Cybernetics and Informatics, roč. 1, č. 3, ISSN 1690-4524
Sborník
Proceedings of The 20th World Multi-Conference on Systemics, Cybernetics and Informatics
Řada
WMSCI 2016 - 20th World Multi-Conference on Systemics, Cybernetics and Informatics, Proceedings
Konference
The 20th World Multi-Conference on Systemics, Cybernetics and Informatics, Orlando, Florida, US
ISBN
978-1-941763-47-6
Vydavatel
The International Institute of Informatics and Systemics
Místo
Orlando, US
EID Scopus
BibTeX
@INPROCEEDINGS{FITPUB10933,
   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 = "WMSCI 2016 - 20th World Multi-Conference on Systemics, Cybernetics and Informatics, Proceedings",
   journal = "Journal on Systemics, Cybernetics and Informatics",
   volume = 1,
   number = 3,
   year = 2016,
   location = "Orlando, US",
   publisher = "The International Institute of Informatics and Systemics",
   ISBN = "978-1-941763-47-6",
   ISSN = "1690-4524",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10933"
}
Soubory
Nahoru