Fast Effective Deterministic Primality Test Using CUDA/GPGPU
Journal Title: INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY - Year 2013, Vol 12, Issue 3
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 a 8-core CPU and a 448-core GPGPU. Experimental results indicate that upto 94.35x speedup can be achieved for 21-digit decimal numbers.
Authors and Affiliations
Abu Asaduzzaman, Anindya Maiti, Chok Meng Yip
Keywords
Related Articles
- EP ID EP650405
- DOI 10.24297/ijct.v12i3.3247
- Views 93
- Downloads 0
DIGITAL IMAGE ANALYSIS BASED ON AUTOMATED COUNTING CLUSTERED SOYBEAN SEEDS
- Â This paper investigates the use of digital image analysis techniques for developing for counting clustered soya bean seeds. Images are extracted from source WWW.21food.com). As manual counting have several issues suc...
SAPMS; Student Assessment Process Management System Enriched with Quality Factors
Computer's hardware and software development aided education field progresses more rapidly. Not only the computer is used in learning and assessment processes to add more attractiveness, but also it's used for better per...
HYDROMAGNETIC STABILITY OF STREAMING COMPRESSIBLE CYLINDER PERVADED BY MAGNETIC FIELD
The Stability of MHD compressible streaming fluid cylinder of radius endowed with surface tension and pervaded by axial magnetic field has been developed. The stability criterion is established in general form. The model...
Enhanced Tree Based Real Time Intrusion Detection System in Big Data
Intrusion detection is one of the major necessities of the current networked environment, where every information is available in its corresponding digital form. This paper presents an enhanced tree based approach that c...
Design and implementation of a health document
Exchanging and integrating medical information in the healthcare domain is a challenge. Indeed, the diversity of databases and the different representations of information sources make this exchange a very difficult task...