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 107
- Downloads 0
Solution of a Fuzzy Assignment Problem by using Branch-and-Bound Technique with application of linguistic variable
In this paper Branch and bound technique is applied to assignment problem with fuzzy cost with objective to minimise cost, fuzzy cost is assumed as triangular fuzzy number, Yager’s ranking method has been used for rank...
Analysis and Comparison of Color Features for Content Based Image Retrieval
Creation of a content-based image retrieval system implies solving a number of difficult problems, including analysis of low-level image features and construction of feature vectors, multidimensional indexing, design of...
EVOLVING INFORMATION TECHNOLOGY: OPPORTUNITIES AND CHALLENGES
The rapid Information technology evolution is fast becoming a change agent in the ways we conduct business and social interaction. Due to the increasing number of regulations and policies regarding information technology...
Security Defects in Biometric- based IdentificationSystemsand Mechanisms torectify them
Biometrics is one of the evolving technologies widely used in different aspects of life today. Theuse of biometrics for identification is a system mainly established to recognize a certain person through authentication b...
Enhancement of Sales promotion using Clustering Techniques in Data Mart
Clustering is an important research topic in wide range of unsupervised classification application. Clustering is a technique, which divides a data into meaningful groups. K-means algorithm is one of the popular clusteri...