Irrational base discrete weighted transform

Short description: Variant of fast Fourier 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)[1] 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.[2][3]

It is most notably used in the Great Internet Mersenne Prime Search.

## Contents

* 1 Algorithm
* 2 Applications
* 2.1 Derived methods
* 3 Notes
* 4 References
* 5 Further reading

## Algorithm

The IBDWT method, as applied to the Lucas-Lehmer test for Mersenne primes (which requires repeated squaring modulo a Mersenne number Mp=2p−1), is based on four key elements developed by Crandall and Fagin:[4]

* Balanced-radix representations: Allows digits to be signed (e.g., in the range −W/2≤xj<W/2), which reduces error bounds.[4]
* Variable-base digit representations: Allows each digit xj to have its own base Wj.[4]
* Weighted cyclic convolutions: The multiplication is performed using a Discrete Weighted Transform (DWT).[4]
* Irrational numeric bases: The base used for the transform is irrational.[4]

This approach avoids the need for zero-padding the arrays and performs the multiplication modulo Mp directly.[4] The algorithm to compute the product xy(modMp) is as follows:[4]

1. Choose a run length (signal-length) N<p.[4]
2. Establish a variable base representation for the numbers. For example, x=∑j=0N−1xj2⌈pj/N⌉.[4] Each term is usually between 16 and 20 bits if using double-precision terms. The maximum size of each term is determined empirically,[lower-alpha 1] at least before the contribution of Percival 2003.
3. Define a weight-signal a where each component aj=2⌈pj/N⌉−pj/N, approximated by floats in the interval [1, 2).[4]
4. Compute the forward DWT for both numbers: 𝒳<-DWT(N,a)x and 𝒴<-DWT(N,a)y. This is practically computed using a standard DFT (like an FFT) as DWT(N,a)x≜DFT(N)(ax).[4]
5. Perform a component-wise product of the transformed arrays: 𝒵<-𝒳𝒴.[4]
6. Compute the inverse DWT: z<-DWT(N,a)−1𝒵. This is computed as z=a−1DFT(N)−1(𝒵).[4]
7. Round the resulting components to the nearest integer: z<-round(z), optionally checking the roundoff error is no greater than 0.4 (greater indicates too many integer bits stuffed into each term).[4]
8. Adjust the resulting digits {zn} to restore the variable-base radix representation. This step handles carries and borrows. Single-step partial carrying is sufficient.[4]

## Applications

Double-precision IBDWT is used in the Great Internet Mersenne Prime Search's x86 client Prime95 to perform modular multiplication in the Lucas–Lehmer test and Fermat primarily tests. The prime95 IBDWT library gwnum is also used in programs such as PrimeGrid's LLR2 and PRST. It is chosen because x86 CPUs since Pentium 4 have so much double-precision floating-point computing power that it is much faster to multiply numbers using IBDWT than to do the so using a more straightforward integer FFT (NTT).

Double-precision IBDWT has also been ported to other CPU architectures in the form of Glucas. It has also been ported to GPUs in the form of CUDALucas, GPUowl, and PRPLL.[4]

IBDWT can also be done using integer arithmetic modulo 264-232+1, a number theoretic transform. This approach was first demonstrated by Nick Craig-Wood in ARMPrime.[5] 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.[6]

### Derived methods

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

## Notes

1. ↑ For examples of empirical formulae and tables, see gpuowl and Prime95 "gwnum.c".

## References

1. ↑ Crandall, Richard (1997). "The Challenge of Large Numbers". Scientific American 276 (2): 74–78. doi:10.1038/scientificamerican0297-74. Bibcode: 1997SciAm.276b..74C. https://jstor.org/stable/24993611. Retrieved 29 March 2023.
2. ↑ "Mathematica Use of Renowned Computational Scientist and Author Richard Crandall". Wolfram Research. https://wolfram.com/customer-stories/mathematica-use-of-renowned-computational-scientist-and-author-richard-crandall.html.
3. ↑ 3.0 3.1

* Granger, Robert; Scott, Michael (March 31, 2015). "Faster ECC over F(2^521−1)". PKC 2015. https://www.iacr.org/workshops/pkc2015/talks/VIII/RobGranger2.pdf.
* Granger, Robert; Scott, Michael (2014), Faster ECC over $\mathbb{F}_{2^{521}-1}$, https://eprint.iacr.org/2014/852, retrieved 2025-11-03

4. ↑ 4.00 4.01 4.02 4.03 4.04 4.05 4.06 4.07 4.08 4.09 4.10 4.11 4.12 4.13 4.14 4.15 Thall, Andrew. "Fast Mersenne Prime Testing on the GPU". https://ece.northeastern.edu/groups/nucar/GPGPU4/files/thall.pdf.
5. ↑ Craig-Wood, Nick (4 October 2023). "ncw/iprime". https://github.com/ncw/iprime.
6. ↑ Gallot, Yves (21 September 2025). "galloty/marin". https://github.com/galloty/marin.

## 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
* Percival, Colin (5 March 2002). "Rapid multiplication modulo the sum and difference of highly composite numbers". Mathematics of Computation 72 (241): 387–396. doi:10.1090/S0025-5718-02-01419-9.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Irrational base discrete weighted transform. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Irrational_base_discrete_weighted_transform&oldid=4226617"