Irrational base discrete weighted transform

In mathematics, the irrational base discrete weighted transform (IBDWT) is a variant of the fast Fourier transform using an irrational base; it was developed by Richard Crandall (Reed College), Barry Fagin (Dartmouth College) and Joshua Doenias (NeXT Software) in the early 1990s using Mathematica. It implies a fast, practical implementation of large-number modular multiplication on modern computers, at asymptotically 2× faster than non-modular FFT multiplication.

IBDWT can also be done using integer arithmetic modulo 2⁶⁴-2³²+1, a number theoretic transform. This approach was first demonstrated by Nick Craig-Wood in ARMPrime. This too has been ported to GPUs, providing an alternative for consumer GPUs with weak double-precision computing power but acceptable 32-bit integer power, especially Nvidia models from the 2020s boasting "1:1" or "1:2" 32-bit integer multiplication speed but "1:64" double-precision speed relative to 32-bit floating-point.

Derived methods

Granger and Scott demonstrated using IBDWT-inspired "GRP (generalized repunit prime) multiplication" to accelerate eliptic curve cryptography over F(2⁵²¹-1), the P-521. This is a Karatsuba-like technique featuring a cyclic convolution similar to IBDWT.

Notes

References

Further reading

• Richard Crandall, Barry Fagin: Discrete weighted transforms and large-integer arithmetic, Mathematics of Computation 62, 205, 305-324, January 1994 (PDF file)
• Richard Crandall: Topics in Advanced Scientific Computation, TELOS/Springer-Verlag