Original title:
Integer Factorization on the GPU
Translated title:
Integer Factorization on the GPU
Authors:
Podhorský, Jiří ; Zbořil, František (referee) ; Homoliak, Ivan (advisor) Document type: Master’s theses
Year:
2014
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato práce pojednává o faktorizaci, tedy rozkladu složených čísel na prvočísla a možnostech její paralelizace. Dále shrnuje nejznámější algoritmy pro faktorizaci a nejznámější platformy pro implementaci těchto algoritmů na grafické kartě. Hlavní část práce se zaobírá návrhem a implementací hardwarové akcelerace současného nejrychlejšího algoritmu na grafické kartě s využitím frameworku OpenCL. Následně je v práci uvedeno srovnání rychlostí akcelerovaného algoritmu implementovaného v rámci této práce s ostatními nejznámějšími verzemi algoritmů pro faktorizaci, zpracovávané sériově. Na závěr je v práci diskutována délka klíče algoritmu RSA potřebná pro bezpečný provoz bez možnosti jejího prolomení v reálném časovém intervalu.
This work deals with factorization, a decomposition of composite numbers on prime numbers and possibilities of its parallelization. It summarizes also the best known algorithms for factoring and most popular platforms for the implementation of these algorithms on the graphics card. The main part of the thesis deals with the design and implementation of hardware acceleration current fastest algorithm on the graphics card by using the OpenCL framework. Subsequently, the work provides a comparison of speeds accelerated algorithm implemented in this work with other versions of the best known algorithms for factoring, processed serially. In conclusion, the work discussed length of RSA key needed for safe operation without the possibility of breaking in real time interval.
Keywords:
CUDA; Fermat factorization.; General number field sieve; integer factorization; Lenstra's elliptic curve factorization; OpenCL; Pollard p-1 factorization; Pollard's rho factorization; Quadratic sieve; celočíselná faktorizace; CUDA; Fermatova factorizace.; Kvadratické prosívání; Lenstrova faktorizace eliptické křivky; Obecné prosívání číselného pole; OpenCL; Pollardova p-1 faktorizace; Pollardova rho faktorizace
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/187678