Faster arithmetic for number-theoretic transforms

DOI10.1016/J.JSC.2013.09.002zbMATH Open1284.65195arXiv1205.2926OpenAlexW2067507719MaRDI QIDQ2437296FDOQ2437296

David I. Harvey

Publication date: 3 March 2014

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

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.

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

zbMATH Keywords

fast Fourier transformefficient algorithmmodular arithmeticnumber-theoretic transforms

Mathematics Subject Classification ID

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

Cites Work

• Sampling Methods for Wallenius' and Fisher's Noncentral Hypergeometric Distributions
• Modular Multiplication Without Trial Division
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved Division by Invariant Integers

Cited In (22)

• Title not available (Why is that?)
• Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency
• Accelerated tower arithmetic
• An implementation of parallel number-theoretic transform using Intel AVX-512 instructions
• Fast Multipliers for Number Theoretic Transforms
• Fast arithmetic with general Gauß periods
• Polynomial Multiplication over Finite Fields in Time \( O(n \log n \)
• Rapid multiplication modulo the sum and difference of highly composite numbers
• Speeding up the number theoretic transform for faster ideal lattice-based cryptography
• A search for Wilson primes
• Title not available (Why is that?)
• Arithmetically improved algorithmic performance
• Faster integer multiplication using plain vanilla FFT primes
• The shifted number system for fast linear algebra on integer matrices
• Bootstrapping bits with CKKS
• Fast Library for Number Theory: An Introduction
• Speedable Left-c.e. Numbers
• Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
• A full RNS variant of approximate homomorphic encryption
• Title not available (Why is that?)
• Irregular primes to two billion
• Arithmetic for ternary number-theoretic transforms

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)