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
Breitenbacher Dominik, Ing. (UITS FIT VUT)
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)
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
2-s2.0-85016806556
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