Fast Effective Deterministic Primality Test Using CUDA/GPGPU

Abu Asaduzzaman, Anindya Maiti, Chok M. Yip
EECS Department, Wichita State University, Wichita, Kansas 67260-0083, USA
International Journal of Computers & Technology, Vol 12, No.3, 2014


   title={Fast Effective Deterministic Primality Test Using CUDA/GPGPU},

   author={Asaduzzaman, Abu and Maiti, Anindya and Yip, Chok Meng},







Download Download (PDF)   View View   Source Source   



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->infinity. 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: