Multiplying very large integer in GPU with pascal architecture

摘要

Multiplication plays an important role in scientific computing and cryptography. When the size of multiplicands grow large (e.g. more than 100K-bit), the multiplication process become time consuming. In this paper, we present implementation techniques to multiply very large integer in state of the art GPU architecture. The implementation relies on Number Theoretic Transform with 64-bit prime. The implementation results show that multiplication of 768K-bit integer takes 1.37 milliseconds on GTX1070 (GPU with Pascal architecture). The work presented in this paper can be used to implement various advanced cryptosystem, including Homomorphic Encryption and Lattice based cryptography.