Efficient high-precision integer multiplication on the GPU

doi:10.1177/10943420221077964

Efficient high-precision integer multiplication on the GPU

2022-03-20

1

OA

AI

A

Adrián Perez Diéguez *

DOI：10.1177/10943420221077964

Original

Original request for help

Save

Abstract

En 中文

The multiplication of large integers, which has many applications in computer science, is an operation that can be expressed as a polynomial multiplication followed by a carry normalization. This work develops two approaches for efficient polynomial multiplication: one approach is based on tiling the classical convolution algorithm, but taking advantage of new CUDA architectures, a novelty approach to compute the multiplication using integers without accuracy lossless; the other one is based on the Strassen algorithm, an algorithm that multiplies large polynomials using the FFT operation, but adapting the fastest FFT libraries for current GPUs and working on the complex field. Previous studies reported that the Strassen algorithm is an effective implementation for large enough integers on GPUs. Additionally, most previous studies do not examine the implementation of the carry normalization, but this work describes a parallel implementation for this operation. Our results show the efficiency of our approaches for short, medium, and large sizes.

Keywords:

large integers

multiplication

FFT

GPU

CUDA

Efficient high-precision integer multiplication on the GPU

Abstract

Journal

Organization