Fast effective deterministic primality test using CUDA/GPGPU
Asaduzzaman, Abu Maiti, Anindya Yip, Chok Meng
Asaduzzaman, Abu
Maiti, Anindya
Yip, Chok Meng
Citations
Altmetric:
Other Names
Location
Time Period
Advisors
Original Date
Digitization Date
Issue Date
2015-01-04
Type
Article
Genre
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
Subjects (LCSH)
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
Digital Collection
Finding Aid URL
Use and Reproduction
Archival Collection
PubMed ID
DOI
ISSN
2277-3061