Faster arithmetic for number-theoretic transforms

DOI10.1016/J.JSC.2013.09.002MaRDI QIDQ2437296zbMATH OpenOpenAlexFDO

Authors David I. Harvey

Publication date 3 March 2014

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.2926

zbMATH Keywords

efficient algorithmfast Fourier transformmodular arithmeticnumber-theoretic transforms

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50)

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.

Recommendations

• Fast Fourier transformation based on number theoretic transforms
• scientific article; zbMATH DE number 3932301
• Fast Multipliers for Number Theoretic Transforms
• Multiple radix fast Fourier transformation based on number theoretic transforms
• scientific article; zbMATH DE number 3843648

Cites work

• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 2151219 (Why is no real title available?)
• Improved Division by Invariant Integers
• Modular Multiplication Without Trial Division
• Sampling Methods for Wallenius' and Fisher's Noncentral Hypergeometric Distributions

Cited in

(25)

• A full RNS variant of approximate homomorphic encryption
• Speeding up the number theoretic transform for faster ideal lattice-based cryptography
• An implementation of parallel number-theoretic transform using Intel AVX-512 instructions
• Arithmetically improved algorithmic performance
• Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency
• Accelerated tower arithmetic
• The shifted number system for fast linear algebra on integer matrices
• Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
• A search for Wilson primes
• scientific article; zbMATH DE number 3932301 (Why is no real title available?)
• scientific article; zbMATH DE number 4104356 (Why is no real title available?)
• Fast Multipliers for Number Theoretic Transforms
• Arithmetic for ternary number-theoretic transforms
• Faster integer multiplication using plain vanilla FFT primes
• Rapid multiplication modulo the sum and difference of highly composite numbers
• scientific article; zbMATH DE number 2114153 (Why is no real title available?)
• Speedable Left-c.e. Numbers
• Polynomial multiplication over finite fields in time O(n n)
• Big prime field FFT on the GPU
• Irregular primes to two billion
• Fast Library for Number Theory: An Introduction
• Fast arithmetic with general Gauß periods
• Bootstrapping bits with CKKS
• Fast polynomial arithmetic in homomorphic encryption with cyclo-multiquadratic fields
• Towards a library for straight-line programs

Describes a project that uses

Uses Software

• NTL

This page was built for publication: Faster arithmetic for number-theoretic transforms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437296)