Big Integer Factorization on Parallel Computers
Date Issued
2009
Date
2009
Author(s)
Lin, Zong-Cing
Abstract
The Elliptic Curve Method (ECM) is the method of choice for nding medium-size prime factors. A good ECM implementation is useful for evaluating the strength of the RSA (Rivest, Shamir, Adleman) public-key cryptographic algorithm because it is a critical step in the Number Field Sieve algorithm that is employed as the stateof-the-art cryptanalysis technique against the RSA. In this thesis, we describe ourork to accelerate the ECM with the Cell multi-core processor. We discuss how the performance of cryptanalysis-related applications can bene t from the architecturaleatures of the Cell processor. Finally, we show that our implementation outperforms the previous records.mong previously published results, the ECM implementation with the best performance is achieved using an NVIDIA GTX 295 graphics card on an Intel X86-based platform, which can compute 401 curves per second for 280-bit integers in ECM Stage 1 with B1 = 8192. That implementation also achieves the best cost-performance ratio to date. In our results, the PowerXCell 8i processor, which is a recently revised variant in the Cell family, can handle 776 curves per second, which outperforms the previous record by 93% with much less power consumption, despite the fact that GPU''s (Graphics Processing Units) have greater raw capabilities measured in GFLOPS (Giga Floating-Point Operation per Second).e attribute the high performance and high power e ciency to several architectural features of the Cell processor, namely, the wider main arithmetic pipeline, an auxiliary pipeline for handling managerial tasks, fast direct memory access capability, and the larger fast on-die memory.
Subjects
ellitpic curve method
Cell processor
integer factorization
number field sieve
cryptanalysis
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96922004-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):efc38da491473962646757ab1f84f480