Efficient Multiplication of Polynomials on Graphics Hardware

Pavel Emeliyanenko
Max-Planck-Institut fur Informatik, Saarbrucken, Germany
Advanced Parallel Processing Technologies, Lecture Notes in Computer Science, 2009, Volume 5737/2009, 134-149


   title={Efficient Multiplication of Polynomials on Graphics Hardware},

   author={Emeliyanenko, P.},

   journal={Advanced Parallel Processing Technologies},





Download Download (PDF)   View View   Source Source   



We present the algorithm to multiply univariate polynomials with integer coefficients efficiently using the Number Theoretic transform (NTT) on Graphics Processing Units (GPU). The same approach can be used to multiply large integers encoded as polynomials. Our algorithm exploits fused multiply-add capabilities of the graphics hardware. NTT multiplications are executed in parallel for a set of distinct primes followed by reconstruction using the Chinese Remainder theorem (CRT) on the GPU. Our benchmarking experiences show the NTT multiplication performance up to 77 GMul/s. We compared our approach with CPU-based implementations of polynomial and large integer multiplication provided by NTL and GMP libraries.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: