OPTIMIZATION OF PRIMALITY TESTING METHODS BY GPU EVOLUTIONARY SEARCH

by Manju Hegde

Just read Steve Worley’s recent paper on primality testing using CUDA, “Optimization of Primality Testing Methods by GPU Evolutionary Search,”and it was personally very gratifying.

Many years ago my love for mathematics was awakened by Hardy and Wright’s, “An Introduction to the Theory of Numbers” which was also my introduction to the amazing centuries old lore and theatre around Fermat’s Last Theorem.  This book’s easily accessible treatment of prime numbers is a pleasure to read but I remember wondering that, while this was fun and challenging, would anything worthwhile ever come of this?

Fast forward many years and the difficulty of factoring numbers makes the products of large prime numbers very useful in authentication systems online! It is not easy to find the factors of such a product when you know just the product but, on the other hand, if you know one factor, finding the other is trivial. So it is asymmetric information which can be used to verify the authenticity of the communication. For this to work well, however, you need really large prime numbers, the larger the more secure. And now, per Steve Worley’s paper, CUDA helps just that! Basically, by using Fermat’s Little Theorem (Fermat again, how satisfyingly ironic?) you can, with high probability, identify the primality of a number. The probability of the number being prime increases with the number of computations you do and speeding up the computations using CUDA allows for the identification of much larger primes.

This is a fascinating illustration of what can happen when you juxtapose ideas from different fields. Here you mix and match number theory, probability, computer architecture and semiconductors, and BAM, more secure authentication! This seems to be illustrative of some of the inroads CUDA is making. The speeds it is delivering make some part of a problem much more tractable, and that removes a prior bottleneck and often, opens up just a new way of doing things. Speed does not just help to do things faster, but also to be done in unexpected ways.