Fast effective deterministic primality test using CUDA/GPGPU

No Thumbnail Available
Authors
Asaduzzaman, Abu
Maiti, Anindya
Yip, Chok Meng
Advisors
Issue Date
2015-01-04
Type
Article
Keywords
CUDA architecture , Deterministic algorithm , GPU computing , Parallel computing , Primality test , Research Subject Categories::MATHEMATICS , Research Subject Categories::TECHNOLOGY::Electrical engineering, electronics and photonics::Electrical engineering , High Performance Computing , Parallel programming , Low power system
Research Projects
Organizational Units
Journal Issue
Citation
Asaduzzaman, Abu, Maiti, Anindya and Chok M. Yip. 2015. Fast effective deterministic primality test using CUDA/GPGPU. International Journal of Computers & Technology;v.12 no.3, pp. 3738-3746,
Abstract

There are great interests in understanding the manner by which the prime numbers are distributed throughout the integers. Prime numbers are being used in secret codes for more than 60 years now. Computer security authorities use extremely large prime numbers when they devise cryptographs, like RSA (short for Rivest, Shamir, and Adleman) algorithm, for protecting vital information that is transmitted between computers. There are many primality testing algorithms including mathematical models and computer programs. However, they are very time consuming when the given number n is very big or n→∞. In this paper, we propose a novel parallel computing model based on a deterministic algorithm using central processing unit (CPU) / general-purpose graphics processing unit (GPGPU) systems, which determines whether an input number is prime or composite much faster. We develop and implement the proposed algorithm using a system with an 8-core CPU and a 448-core GPGPU. Experimental results indicate that up to 94.35x speedup can be achieved for 21-digit decimal numbers.

Table of Contents
Description
Click on the URL link to access the article.
Publisher
Council for Innovative Research
Journal
Book Title
Series
International Journal of Computers & Technology;v.12 no.3
PubMed ID
DOI
ISSN
2277-3061
EISSN