Detail publikace

Parallelized Self-Initializing Quadratic Sieve using OpenMP

BREITENBACHER Dominik, HOMOLIAK Ivan a HANÁČEK Petr. Parallelized Self-Initializing Quadratic Sieve using OpenMP. In: Santa's Crypto Get-Together 2015. Praha: Trusted Network Solutions, a.s., 2015, s. 39-40. ISBN 978-80-904257-7-4.
Název česky
Paralelizované Self-Initializing Quadratic Sieve užitím OpenMP
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Abstrakt

Tato práce se zabývá faktorizací celých čísel. Faktorizace je velmi známou a používanou metodou pro RSA kryptoanalýzu. V rámci tohoto článku byla jako faktorizační metoda vybrána metoda SIQS (Self-Initializing Quadratic Sieve). Tato metoda byla vybrána na základě náročnosti k naučení a naprogramování a na základě její rychlosti faktorizace. Metoda QS (Quadratic sieve) je obecně považována za druhou nejrychlejší faktorizační metodu a nejrychlejší metodou pro faktorizaci čísel o 100 dekadických číslicích (332 bitů) a méně. Metoda SIQS je nejvíce optimalizovanou verzí QS. Metoda byla v rámci této práce implementována a podrobně zdokumentována, čímž se práce snaží vyplnit mezeru mezi teoretickým popisem metody a jejími stávajícími implementacemi. Přestože SIQS je 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. Nabízí se dvě možnosti, jak toho dosáhnout. Jednou z nich je paralelizace, druhou pak optimalizace. Obě možnosti byly využity v rámci této práce. Pro paralelizaci metody je použito OpenMP. Cílem této práce je ukázat, jak lze využitím paralelizace a detailní analýzou kódu s optimalizací dosáhnout značného urychlení. Metoda iterativní optimalizace se ukázala jako velice efektivní nástroj. Použitím této metody byla až 100x urychlena implementace SIQS oproti referenční verzi a v některých částech kódu dokonce ještě více.

Rok
2015
Strany
39-40
Sborník
Santa's Crypto Get-Together 2015
Konference
Santa's Crypto Get-Together 2016, Praha, CZ
ISBN
978-80-904257-7-4
Vydavatel
Trusted Network Solutions, a.s.
Místo
Praha, CZ
BibTeX
@INPROCEEDINGS{FITPUB11049,
   author = "Dominik Breitenbacher and Ivan Homoliak and Petr Han\'{a}\v{c}ek",
   title = "Parallelized Self-Initializing Quadratic Sieve using OpenMP",
   pages = "39--40",
   booktitle = "Santa's Crypto Get-Together 2015",
   year = 2015,
   location = "Praha, CZ",
   publisher = "Trusted Network Solutions, a.s.",
   ISBN = "978-80-904257-7-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11049"
}
Nahoru