# Discrete weighted transforms and large-integer arithmetic

@article{Crandall1994DiscreteWT, title={Discrete weighted transforms and large-integer arithmetic}, author={Richard E. Crandall and Barry S. Fagin}, journal={Mathematics of Computation}, year={1994}, volume={62}, pages={305-324} }

It is well known that Discrete Fourier Transform (DFT) techniques may be used to multiply large integers. We introduce the concept of Discrete Weighted Transforms (DWTs) which, in certain situations, substantially improve the speed of multiplication by obviating costly zero-padding of digits. In particular, when arithmetic is to be performed modulo Fermât Numbers 22"1 + 1 , or Mersenne Numbers 29 1 , weighted transforms effectively reduce FFT run lengths. We indicate how these ideas can be… Expand

#### 90 Citations

Rapid multiplication modulo the sum and difference of highly composite numbers

- Computer Science, Mathematics
- Math. Comput.
- 2003

Tight bounds on the rounding errors which naturally occur in floating-point implementations of FFT and DWT multiplications are proved, making it possible for FFT multiplications to be used in situations where correctness is essential, for example in computer algebra packages. Expand

Integer multiplication in time O(n log n)

- Mathematics
- 2021

We present an algorithm that computes the product of two n-bit integers in O(n log n) bit operations, thus confirming a conjecture of Schonhage and Strassen from 1971. Our complexity analysis takes… Expand

Parallel Algorithm for Multiplying Integer Polynomials and Integers

- Computer Science
- 2013

Under certain conditions the authors' integer polynomial multiplication method is asymptotically faster than the algorithm based on Fast Fourier Transform when applied to multiply both: polynomials and their coefficients. Expand

Some Parallel Algorithms for Integer Factorisation

- Computer Science
- Euro-Par
- 1999

This work describes several integer factorisation algorithms, considers their suitability for implementation on parallel machines, and gives examples of their current capabilities. Expand

Spectral arithmetic in Montgomery modular multiplication

- Mathematics, Computer Science
- Journal of Cryptographic Engineering
- 2017

This survey paper introduces the development of spectral-based MMM, as well as its two important properties: high parallelism and low complexity, and compares these algorithms in terms of digit-level complexity. Expand

Fast convolutions meet Montgomery

- Computer Science, Mathematics
- Math. Comput.
- 2008

This paper gives a method for understanding and bypassing the short multiplication problem, thus reducing the costs of ring arithmetic to roughly 2M(R) when also using fast convolutions. Expand

Recent Progress and Prospects for Integer Factorisation Algorithms

- Computer Science
- COCOON
- 2000

This paper considers the problem of parallel solution of the large, sparse linear systems which arise with the MPQS and NFS methods, and outlines several integer factorisation algorithms, consider their suitability for implementation on parallel machines, and give examples of their current capabilities. Expand

Integer convolution via split-radix fast Galois transform

- Mathematics
- 1999

Integer convolution can be eected, as is well known, via certain number-theoretical transforms. One particular transform, which we call a discrete Galois transform (DGT), can be used eciently for… Expand

Area-Time Efficient Architecture of FFT-Based Montgomery Multiplication

- Mathematics, Computer Science
- IEEE Transactions on Computers
- 2017

This paper integrates the fast Fourier transform (FFT) method into the McLaughlin’s framework, and presents an improved FFT-based Montgomery modular multiplication (MMM) algorithm achieving high area-time efficiency. Expand

Parallel Implementation of Multiple-Precision Arithmetic and 1 , 649 , 267 , 440 , 000 Decimal Digits of π Calculation

- 2009

We present efficient parallel algorithms for multiple-precision arithmetic operations of more than several million decimal digits on distributed-memory parallel computers. A parallel implementation… Expand

#### References

SHOWING 1-10 OF 18 REFERENCES

Computational Complexity of Fourier Transforms over Finite Fields

- Mathematics
- 1977

Abstract : This paper describes a method for computing the Discrete Fourier Transform (DFT) of a sequence of n elements over a finite field GF (p to the mth power) with a number of bit operations… Expand

Large Integer Multiplication on Hypercubes

- Computer Science
- J. Parallel Distributed Comput.
- 1992

A convolution algorithm on a massively parallel processor, based on the Fermat Number Transform, is presented and some examples of the trade-offs between modulus, interprocessor communication steps, and input size are presented. Expand

The use of finite fields to compute convolutions

- Mathematics, Computer Science
- IEEE Trans. Inf. Theory
- 1975

If q is a Mersenne prime, one can utilize the fast Fourier transform (FFT) algorithm to yield a fast convolution without the usual roundoff problem of complex numbers. Expand

Real-valued fast Fourier transform algorithms

- Computer Science
- IEEE Trans. Acoust. Speech Signal Process.
- 1987

A new implementation of the real-valued split-radix FFT is presented, an algorithm that uses fewer operations than any otherreal-valued power-of-2-length FFT. Expand

Parameter determination for complex number-theoretic transforms using cyclotomic polynomials

- Mathematics
- 1989

Some new results for finding all convenient moduli m for a complex numbertheoretic transform with given transform length n and given primitive nth root of unity modulo m are presented. The main… Expand

The fast Fourier transform in a finite field

- Mathematics
- 1971

A transform analogous to the discrete Fourier transform may be defined in a finite field, and may be calculated efficiently by the 'fast Fourier transform' algorithm. The transform may be applied to… Expand

IRREGULAR PRIMES TO ONE MILLION

- 1992

Using "fast" algorithms for power series inversion (based on the fast Fourier transform and multisectioning of power series), we have calculated all irregular primes up to one million, including… Expand

Speeding the Pollard and elliptic curve methods of factorization

- Mathematics
- 1987

Since 1974, several algorithms have been developed that attempt to factor a large number N by doing extensive computations module N and occasionally taking GCDs with N. These began with Pollard's p 1… Expand

A Stochastic Roundoff Error Analysis for the Fast Fourier Transform

- Mathematics
- 1991

We study the accuracy of the output of the Fast Fourier Transform by estimating the expected value and the variance of the accompanying linear forms in terms of the expected value and variance of the… Expand

FIR filtering by the modified Fermat number transform

- Mathematics, Computer Science
- IEEE Trans. Acoust. Speech Signal Process.
- 1990

Right-angle circular convolution (RCC) and the modified Fermat number transform (MFNT) are introduced. It is shown that a linear convolution of two N-point sequences can be obtained by a… Expand