Faster arithmetic for number-theoretic transforms

By David Harvey. 2012

104 citations recorded by the source corpus.

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 [email protected]?s NTL library.

Subfields: Computational Theory and Mathematics, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

XPIR : Private Information Retrieval for Everyone (2016, methodology): “First we use Harvey’s NTT algorithm [47] which is very fast but only works for some polynomials degrees (powers of two).”
Implementation and Performance Evaluation of RNS Variants of the BFV Homomorphic Encryption Scheme (2019, methodology): “We remark that the current version of DSI_BFV includes the NTT optimizations from David Harvey [21] adapted for DGT computations.”
Faster CryptoNets: Leveraging Sparsity for Real-World Encrypted Inference (2018, methodology): “Assuming that the coefﬁcient modulus q is chosen such that ( q − 1) is divisible by 2 n , we can invoke the Number Theoretic Transform to achieve O ( n log n ) [36].”
Simple Encrypted Arithmetic Library-SEAL (2017, methodology): “SEAL uses David Harvey’s algorithm for NTT, as described in [27], which additionally requires that 4q ≤ β, where β denotes the word size of q:”
Simple Encrypted Arithmetic Library v2.3.0 (2017, methodology): “enable_ntt true if all NTT can be used for polynomial multiplication (see [26, 28]) with respect to all the factors qi of q, otherwise false.”
Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography (2016, methodology): “Relevant examples are the use of precomputed quotients, as exploited in Shoup’s butterﬂy algorithm [29], and the use of redundant representations that enable the elimination of several conditional modular corrections, as shown by Harvey [13].”
Simple Encrypted Arithmetic Library - SEAL v2.1 (2016, methodology): “We use David Harvey’s algorithm for NTT as described in [18], which additionally requires that 4q ≤ β, where”