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 94
- Downloads 0
Pso Optimization algorithm for Task Scheduling on The Cloud Computing Environment
The Cloud computing is a most recent computing paradigm where IT services are provided and delivered over the Internet on demand. The Scheduling problem for cloud computing environment has a lot of awareness as the appli...
An Extended Recommendation System using Data Mining Implemented for Smart Phones
In this paper we introduce a recommendation system that attempts to solve some of the issues of classical recommendation systems: the need for huge amounts of data to be able to extract meaningful patterns, or for dire...
Enhanced Feature-Based Automatic Text Summarization SystemUsingSupervised Technique
In this work, we propose an efficient text summarization methodby ranking sentences according to their scores that use a combination of existing and improved sentence features. Many works in the literature proposed imp...
A NOVEL APPROACH OF TASK CLASSIFICATION AND VM SKEWNESS IN CLOUD ENVIRONMENT
Cloud Computing is a technology that provides a platform for sharing of resources such as software, infrastructure, application and other information. Cloud Computing is being used widely all over the world, as it provid...
Microprocessor Architecture Era for Development Cloud Computing of Ministry of Electricity and Energy of Egypt
A development and evaluation the Cloud Computing (ClComp) of Ministry of Electricity and Energy of Egypt (MEEE) is presented in this paper. In order to be able to judge whether the ClComp of MEEE is competence, there is...