Research Article Open Access

Big Integer Multiplication with CUDA FFT (cuFFT) Library

Abstract

It is well recognized in the computer algebra theory and systems communities that the Fast Fourier Transform (FFT) can be used for multiplying polynomials. Theory predicts that it is fast for “large enough” polynomials. The basic idea is to use fast polynomial multiplication to perform fast integer multiplication. We can achieve really fast FFT multiplication on GPU with parallel FFT implementation, in this case with cuFFT. Here we provide cuFFT multiplication and its comparison with well known fast big integer arithmetic libraries (.net BigInteger, GMP, IntX). We also compare our results with results of other papers in this area. Experiments showed, that cuFFT multiplication is becoming faster than all other tested methods, when we deal with about 2^15 digit integers.

Hovhannes Bantikyan

To read the full article Download Full Article | Visit Full Article