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. Journal on Systemics, Cybernetics and Informatics, 2016, vol. 14, no. 3, p. 51-58. ISSN: 1690-4524.
Název česky
Vliv optimalizace a paralelizace na faktorizační rychlost SIQS
Typ
článek v časopise
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
51–58
Časopis
Journal on Systemics, Cybernetics and Informatics, roč. 14, č. 3, ISSN 1690-4524
BibTeX 
@article{BUT131017,
  author="Dominik {Breitenbacher} and Ivan {Homoliak} and Jiří {Jaroš} and Petr {Hanáček}",
  title="Impact of Optimization and Parallelism on Factorization Speed of SIQS",
  journal="Journal on Systemics, Cybernetics and Informatics",
  year="2016",
  volume="14",
  number="3",
  pages="51--58",
  issn="1690-4524",
  url="http://www.iiisci.org/Journal/CV$/sci/pdfs/SA559BN16.pdf"
}
Nahoru