Comparison Analysis of the Quadratic Sieve Factoring Method in C and CUDA
by
Brad Baker
Boise State University

I will be implementing the Quadratic Sieve factoring method in both serial and parallel programming models for performance analysis. The serial implementation will be computed on a CPU in the C programming language. The parallel implementation will be computed on an NVIDIA GPU utilizing the CUDA parallel architecture. Device specifications will be reported along with the results.

There are some limitations to be aware of. Sieving requires a lot of memory, and is typically used on very large integers. Currently, CUDA does not provide a bignum library to represent abnormally large integers, which may be a reason why a sieving method has not yet been developed for CUDA. For these reasons, I will begin with standard integer data types currently supported by C and CUDA. Upon successful completion of the algorithms, I may integrate a bignum library to be used by both applications.

Since the introduction of CUDA by NVIDIA in 2007, many applications have been developed to take advantage of NVIDIA's GPU parallel architecture, with some applications reporting speed up times in the hundreds over CPU implementations. Very few of the published CUDA articles and applications have had a focus on general factoring methods, and not one Quadratic Sieve has been implemented with CUDA to my knowledge. Developing the Quadratic Sieve in CUDA will be a progressive step for factoring methods implemented in parallel for accessible GPUs.

A CUDA implemented Quadratic Sieving method will provide an easily affordable, high performance, parallel sieving method to Desktop PCs. This is desirable since parallel computing clusters and super computers can be expensive, and not easily accessible. Later, one could integrate other factoring methods such as Elliptical Curve, and Number Field Sieve into this application to develop a whole selective library for factoring.

Date received: October 30, 2009