Faster arithmetic for number-theoretic transforms
arXiv:1205.2926 · doi:10.1016/j.jsc.2013.09.002
Abstract
We show how to improve the efficiency of the computation of fast Fourier transforms over F_p where p is a word-sized prime. Our main technique is optimisation of the basic arithmetic, in effect decreasing the total number of reductions modulo p, by making use of a redundant representation for integers modulo p. We give performance results showing a significant improvement over Shoup's NTL library.
9 pages, a few minor changes and reorganisation, to appear in JSC
Cited by in corpus (12)
- Faster CryptoNets: Leveraging Sparsity for Real-World Encrypted Inference
- HEAAN Demystified: Accelerating Fully Homomorphic Encryption Through Architecture-centric Analysis and Optimization
- Accelerating Number Theoretic Transformations for Bootstrappable Homomorphic Encryption on GPUs
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
- A Systematic Study of Lattice-based NIST PQC Algorithms: from Reference Implementations to Hardware Accelerators
- A Fully Private Pipeline for Deep Learning on Electronic Health Records
- Cheddar: A Swift Fully Homomorphic Encryption Library Designed for GPU Architectures
- Intel HEXL: Accelerating Homomorphic Encryption with Intel AVX512-IFMA52
- Ring Learning With Errors: A crossroads between postquantum cryptography, machine learning and number theory
- Speeding up decimal multiplication
- Faster integer multiplication using plain vanilla FFT primes
- Elements of Design for Containers and Solutions in the LinBox Library