Fast convolutions meet Montgomery

DOI10.1090/S0025-5718-07-01956-4zbMath1183.11081OpenAlexW2144686178MaRDI QIDQ5444325

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

FFTconvolutionsfast arithmetic

Mathematics Subject Classification ID

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

Related Items

Subquadratic Polynomial Multiplication over GF(2 m ) Using Trinomial Bases and Chinese Remaindering ⋮ Implementing the asymptotically fast version of the elliptic curve primality proving algorithm

Uses Software

• LiDIA
• NTL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast modular transforms
• On short multiplications and divisions
• A new polynomial factorization algorithm and its implementation
• On computing reciprocals of power series
• Polynomial evaluation and interpolation on special sets of points
• Fast multiplication of large numbers
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• An algorithm for division of powerseries
• A long note on Mulders' short product
• Modular Multiplication Without Trial Division
• On Computing the Discrete Fourier Transform
• Discrete Weighted Transforms and Large-Integer Arithmetic
• New frameworks for Montgomery’s modular multiplication method
• The truncated fourier transform and applications
• An Algorithm for the Machine Calculation of Complex Fourier Series