Detail publikace

Impact of Optimization and Parallelism on Factorization Speed of SIQS

BREITENBACHER, D.; HOMOLIAK, I.; JAROŠ, J.; HANÁČEK, P. Impact of Optimization and Parallelism on Factorization Speed of SIQS. In Proceedings of The 20th World Multi-Conference on Systemics, Cybernetics and Informatics. Journal on Systemics, Cybernetics and Informatics. WMSCI 2016 - 20th World Multi-Conference on Systemics, Cybernetics and Informatics, Proceedings. Orlando: The International Institute of Informatics and Systemics, 2016. p. 55-62. ISBN: 978-1-941763-47-6. ISSN: 1690-4524.
Název česky
Vliv optimalizace a paralelizace na faktorizační rychlost SIQS
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Breitenbacher Dominik, Ing.
Homoliak Ivan, Ing., Ph.D. (UITS)
Jaroš Jiří, doc. Ing., Ph.D. (UPSY)
Hanáček Petr, doc. Dr. Ing. (UITS)
URL
Klíčová slova

Factorization, SIQS, Parallelism, OpenMP, Profiling, RSA cryptanalysis

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
ISBN
978-1-941763-47-6
Vydavatel
The International Institute of Informatics and Systemics
Místo
Orlando
EID Scopus
2-s2.0-85016806556
BibTeX 
@inproceedings{BUT130912,
  author="Dominik {Breitenbacher} and Ivan {Homoliak} and Jiří {Jaroš} and Petr {Hanáček}",
  title="Impact of Optimization and Parallelism on Factorization Speed of SIQS",
  booktitle="Proceedings of The 20th World Multi-Conference on Systemics, Cybernetics and Informatics",
  year="2016",
  series="WMSCI 2016 - 20th World Multi-Conference on Systemics, Cybernetics and Informatics, Proceedings",
  journal="Journal on Systemics, Cybernetics and Informatics",
  volume="1",
  number="3",
  pages="55--62",
  publisher="The International Institute of Informatics and Systemics",
  address="Orlando",
  isbn="978-1-941763-47-6",
  issn="1690-4524",
  url="http://www.iiisci.org/Journal/CV$/sci/pdfs/SA559BN16.pdf"
}
Nahoru