CUDA-assisted energy-efficient primality test

摘要

It has been known that the primes are infinite in number but the exact sequence of primes is not predictable. Prime numbers and computers have been linked since the 1950s. 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 and energy consuming when the given number n is very large. In this paper, we propose a Compute Unified Device Architecture (CUDA)-accelerated deterministic algorithm to determine whether an input number is prime or composite much faster to save energy. We develop and implement the proposed algorithm using a system with an 8-core CPU and a 448-core GPU. Experimental results indicate that up to 45x speedup and 88% energy saving can be achieved for 20-digit decimal numbers.