High Throughput Multiple-Precision GCD on the CUDA Architecture

被引：4

作者：

Fujimoto, Noriyuki ^{[1
]}

机构：

[1] Osaka Prefecture Univ, Grad Sch Sci, Dept Math & Informat Sci, Naka Ku, Sakai, Osaka 5998531, Japan

来源：

2009 IEEE INTERNATIONAL SYMPOSIUM ON SIGNAL PROCESSING AND INFORMATION TECHNOLOGY (ISSPIT 2009) | 2009年

关键词：

GPGPU; CUDA; High throughput computing; Greatest common divisor;

D O I：

10.1109/ISSPIT.2009.5407488

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

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 CPU 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.

引用

页码：507 / 512

页数：6

共 11 条

[1]

Brent R. P., 1980, BIT (Nordisk Tidskrift for Informationsbehandling), V20, P176, DOI 10.1007/BF01933190

[2]

Gesari G., 1998, LNCS, V1423, P64

[3]

Jebelean T., 1993, Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation. ISSAC '93, P111, DOI 10.1145/164081.164102

[4]

Lame G, 1844, COMPTE RENDU PARIS, V19, P867

[5]

Lehman M., 1961, IRE T COMP, VEC-10, P691

[6] NVIDIA Tesla: A unified graphics and computing architecture [J].

Lindholm, Erik ;

Nickolls, John ;

Oberman, Stuart ;

Montrym, John .

IEEE MICRO, 2008, 28 (02) :39-55

[7]

*NVIDIA, 2009, CUDA PROGR GUID 2 3

[8]

nVidia&REG

[9]

, 2009, CUDA BEST PRACT GUID

[10]

Pollard J. M., 1975, BIT (Nordisk Tidskrift for Informationsbehandling), V15, P331, DOI 10.1007/BF01933667

← 1 2 →