Faster arithmetic for number-theoretic transforms

2012/05/31 by David Harvey · 2 citations
Computer Science · #acm:68W30 #cs.DS #cs.SC #msc:68W30

paper · pdf · doi:10.1016/j.jsc.2013.09.002

9 pages, a few minor changes and reorganisation, to appear in JSC

crossref created 2013/09/24 · arxiv created 2013/09/25 · arxiv updated 2013/09/26 · crossref issued 2014/01/01 · crossref published 2014/01/01 · crossref published-print 2014/01/01 · crossref deposited 2018/10/12 · crossref indexed 2026/08/06

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.

Cited by

• High-performance NTT accelerators for PQC leveraging Unified Redundant Arithmetic and Fine-Tuned Microarchitecture
• Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Related

• Faster Integer Multiplication Using Preprocessing
• Speeding up decimal multiplication
• The Arithmetic Fourier Transform
• Faster integer multiplication using plain vanilla FFT primes
• Introduction to Number Theoretic Transform