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 90
- Downloads 0
MARKETING INFORMATION SYSTEMS IN THE HEALTH SECTOR: A PRACTICE IN HOSPITALS IN TURKEY AND JORDAN
Health tourism, showing development in the last twenty years in the world, has emerged as an alternative tourism. Health tourism, very quickly developing among alternative tourism options, is an important profit tool s...
ALGORITHM FOR THE ANALYSIS OF EXACTICTY OF BANERJEE TEST
In compiler theory, the Banerjee test is a dependence test. The Banerjee test assumes that all loop indices are independent, however in reality, this is often not true. The Bannerjee test is a conservative test. That is,...
Representation of cloud ecosystem using engineering methodologies
Cloud Computing has fascinated massive consideration for business in spite of lot of technologies and business models in the market. The operational particulars within the cloud are not coherent enough to customers. Henc...
A Preview on Subspace Clustering of High Dimensional Data
When clustering high dimensional data, traditional clustering methods are found to be lacking since they consider all of the dimensions of the dataset in discovering clusters whereas only some of the dimensions are relev...
Prediction Of Long Term Living Donor Kidney Graft Outcome: Comparison Between Different Machine Learning Methods
Predicting the outcome of a graft transplant with high level of accuracy is a challenging task In medical fields and Data Mining has a great role to answer the challenge. The goal of this study is to compare the performa...