Fast convolutions meet Montgomery

DOI10.1090/S0025-5718-07-01956-4MaRDI QIDQ5444325zbMATH OpenOpenAlexFDO

Authors Preda Mihaĭlescu

Publication date 25 February 2008

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

Full work available at URL https://doi.org/10.1090/s0025-5718-07-01956-4

zbMATH Keywords

convolutionsfast arithmeticFFT

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Recommendations

• Fast multiplication and its applications
• New frameworks for Montgomery’s modular multiplication method
• Fast Multiplication for Skew Polynomials
• Simultaneous modular reduction and Kronecker substitution for small finite fields
• Convolutions of long integer sequences by means of number theoretic transforms over residue class polynomial rings

Cites work

• A long note on Mulders' short product
• A new polynomial factorization algorithm and its implementation
• An algorithm for division of powerseries
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Discrete Weighted Transforms and Large-Integer Arithmetic
• Fast modular transforms
• Fast multiplication of large numbers
• scientific article; zbMATH DE number 6698765 (Why is no real title available?)
• scientific article; zbMATH DE number 3928865 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 2151179 (Why is no real title available?)
• scientific article; zbMATH DE number 2124950 (Why is no real title available?)
• scientific article; zbMATH DE number 3322464 (Why is no real title available?)
• Modern computer algebra
• Modular Multiplication Without Trial Division
• New frameworks for Montgomery’s modular multiplication method
• On computing reciprocals of power series
• On Computing the Discrete Fourier Transform
• On short multiplications and divisions
• Polynomial evaluation and interpolation on special sets of points
• The truncated fourier transform and applications

Cited in

(4)

• Implementing the asymptotically fast version of the elliptic curve primality proving algorithm
• Subquadratic Polynomial Multiplication over GF(2 m ) Using Trinomial Bases and Chinese Remaindering
• Q-adic transform revisited
• Towards a library for straight-line programs

Describes a project that uses

Uses Software

• NTL
• LiDIA

This page was built for publication: Fast convolutions meet Montgomery

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