High throughput multiple-precision GCD on the CUDA architecture

Author

Fujimoto, Noriyuki

Author_Institution

Dept. of Math. & Inf. Sci., Osaka Prefecture Univ., Sakai, Japan

fYear

2009

fDate

14-17 Dec. 2009

Firstpage

507

Lastpage

512

Abstract

Investigation of the cryptanalytic strength of RSA cryptography requires computing many GCDs of two long integers (e.g., of length 1024 bits). This paper presents a high throughput parallel algorithm to perform many GCD computations concurrently on a GPU based on the CUDA architecture. The experiments with an NVIDIA GeForce GTX285 GPU and a single core of 3.0 GHz Intel Core2 Duo E6850 CPU show that the proposed GPU algorithm runs 11.3 times faster than the corresponding CPU algorithm.

Keywords

computer graphic equipment; cryptography; parallel architectures; CUDA architecture; GPU algorithm; RSA cryptography; cryptanalytic strength; greatest common divisor; high throughput multiple-precision GCD; high throughput parallel algorithm; Algebra; Central Processing Unit; Computer architecture; Concurrent computing; Cryptography; High performance computing; Mathematics; Parallel algorithms; Throughput; Yarn; CUDA; GPGPU; Greatest common divisor; High throughput computing;

fLanguage

English

Publisher

ieee

Conference_Titel

Signal Processing and Information Technology (ISSPIT), 2009 IEEE International Symposium on

Conference_Location

Ajman

Print_ISBN

978-1-4244-5949-0

Type

conf

DOI

10.1109/ISSPIT.2009.5407488

Filename

5407488

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3401223