Discrete Weighted Transforms and Large-Integer Arithmetic

DOI10.2307/2153411zbMath0839.11065OpenAlexW2045826589WikidataQ59445435 ScholiaQ59445435MaRDI QIDQ4286602

Barry S. Fagin, Richard E. Crandall

Publication date: 19 June 1996

Full work available at URL: https://doi.org/10.2307/2153411

zbMATH Keywords

discrete Fourier transforminteger multiplicationdiscrete weighted transform

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Congruences; primitive roots; residue systems (11A07) Factorization; primality (11A51) Factorization (11Y05) Primality (11Y11)

Related Items (24)

Rapid multiplication modulo the sum and difference of highly composite numbers ⋮ Even faster integer multiplication ⋮ The twenty-fourth Fermat number is composite ⋮ Generalised Mersenne numbers revisited ⋮ Integer multiplication in time \(O(n\log n)\) ⋮ High-Performance Ideal Lattice-Based Cryptography on 8-Bit ATxmega Microcontrollers ⋮ Balanced non-adjacent forms ⋮ Faster integer multiplication using short lattice vectors ⋮ A search for Wieferich and Wilson primes ⋮ Improved Stage 2 to P ± 1 Factoring Algorithms ⋮ Irregular Primes and Cyclotomic Invariants to Four Million ⋮ \(2^n\) in scientific computation and beyond ⋮ The Twenty-Second Fermat Number is Composite ⋮ Distribution of generalized Fermat prime numbers ⋮ Faster integer multiplication using plain vanilla FFT primes ⋮ Fast convolutions meet Montgomery ⋮ Parallel implementation of multiple-precision arithmetic and 2,576,980,370,000 decimal digits of \(\pi \) calculation ⋮ Three new factors of Fermat numbers ⋮ New frameworks for Montgomery’s modular multiplication method ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Recent developments in primality proving ⋮ A note on factors of generalized Fermat numbers ⋮ Factorization of the tenth Fermat number

Cites Work

• Unnamed Item
• Unnamed Item
• Fast Fourier transform and convolution algorithms
• Large integer multiplication on hypercubes
• Fast multiplication of large numbers
• A Stochastic Roundoff Error Analysis for the Fast Fourier Transform
• FIR filtering by the modified Fermat number transform
• Speeding the Pollard and Elliptic Curve Methods of Factorization
• The Twentieth Fermat Number is Composite
• Parameter Determination for Complex Number-Theoretic Transforms Using Cyclotomic Polynomials
• Irregular Primes to One Million
• The use of finite fields to compute convolutions
• Computational Complexity of Fourier Transforms Over Finite Fields
• The Fast Fourier Transform in a Finite Field
• Roundoff Error Analysis of the Fast Fourier Transform

This page was built for publication: Discrete Weighted Transforms and Large-Integer Arithmetic