Efficient Multiplication of Polynomials on Graphics Hardware

Emeliyanenko, Pavel

doi:10.1007/978-3-642-03644-6_11

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Efficient Multiplication of Polynomials on Graphics Hardware

MPS-Authors

/persons/resource/persons44381

Emeliyanenko, Pavel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Emeliyanenko, P. (2009). Efficient Multiplication of Polynomials on Graphics Hardware. In Y. Dou, R. Gruber, & J. Joller (Eds.), Advanced Parallel Processing Technologies (pp. 134-149). Berlin: Springer. doi:10.1007/978-3-642-03644-6_11.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-183A-B

Abstract

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.