Discrete weighted transforms and large-integer arithmetic

Authors:
Richard Crandall and Barry Fagin

Journal:
Math. Comp. **62** (1994), 305-324

MSC:
Primary 11Y11; Secondary 11A51, 11Y05

DOI:
https://doi.org/10.1090/S0025-5718-1994-1185244-1

MathSciNet review:
1185244

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 Fermat Numbers , or Mersenne Numbers , weighted transforms effectively reduce FFT run lengths. We indicate how these ideas can be applied to enhance known algorithms for general multiplication, division, and factorization of large integers.

**[1]**Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,*The design and analysis of computer algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR**0413592****[2]**J. P. Buhler, R. E. Crandall, and R. W. Sompolski,*Irregular primes to one million*, Math. Comp.**59**(1992), no. 200, 717–722. MR**1134717**, https://doi.org/10.1090/S0025-5718-1992-1134717-4**[3]**Daniela Calvetti,*A stochastic roundoff error analysis for the fast Fourier transform*, Math. Comp.**56**(1991), no. 194, 755–774. MR**1068824**, https://doi.org/10.1090/S0025-5718-1991-1068824-0**[4]**K. Chen,*A New Record*:*The largest known prime number*, IEEE Spectrum**27**(1990), 47.**[5]**R. Creutzburg and M. Tasche,*Parameter determination for complex number-theoretic transforms using cyclotomic polynomials*, Math. Comp.**52**(1989), no. 185, 189–200. MR**946602**, https://doi.org/10.1090/S0025-5718-1989-0946602-9**[6]**B. Fagin,*Large integer multiplication on hypercubes*, J. Parallel Distrib. Comput.**14**(1992), 426-430.**[7]**L. Leibowitz,*A simplified arithmetic for the Fermat number transform*, IEEE Trans. Acoust. Speech Signal Process.**24**(1976), 356-359.**[8]**W. Li and A. Peterson,*FIR filtering by the modified Fermat number transform*, IEEE Trans. Acoust. Speech Signal Process.**38**(1990), 1641-1645.**[9]**James H. McClellan and Charles M. Rader,*Number theory in digital signal processing*, Prentice Hall Signal Processing Series, Prentice Hall, Inc., Englewood Cliffs, NJ, 1979. Including reprinted papers. MR**723867****[10]**Peter L. Montgomery,*Speeding the Pollard and elliptic curve methods of factorization*, Math. Comp.**48**(1987), no. 177, 243–264. MR**866113**, https://doi.org/10.1090/S0025-5718-1987-0866113-7**[11]**H. Nussbaumer,*Fast Fourier and convolution algorithms*, Springer-Verlag, Heidelberg, 1982.**[12]**J. M. Pollard,*The fast Fourier transform in a finite field*, Math. Comp.**25**(1971), 365–374. MR**0301966**, https://doi.org/10.1090/S0025-5718-1971-0301966-0**[13]**F. P. Preparata and D. V. Sarwate,*Computational complexity of Fourier transforms over finite fields*, Math. Comp.**31**(1977), no. 139, 740–751. MR**0436662**, https://doi.org/10.1090/S0025-5718-1977-0436662-8**[14]**George U. Ramos,*Roundoff error analysis of the fast Fourier transform*, Math. Comp.**25**(1971), 757–768. MR**0300488**, https://doi.org/10.1090/S0025-5718-1971-0300488-0**[15]**Irving S. Reed and T. K. Truong,*The use of finite fields to compute convolutions*, IEEE Trans. Information Theory**IT-21**(1975), 208–213. MR**0406677****[16]**A. Schönhage and V. Strassen,*Schnelle Multiplikation grosser Zahlen*, Computing (Arch. Elektron. Rechnen)**7**(1971), 281–292 (German, with English summary). MR**0292344****[17]**D. Slowinski and P. Gage, private communication (1992).**[18]**D. Smitley, R. Crandall, B. Fagin, W. Colquitt, R. Frye, J. Buhler, J. Doenias, D. Slowinski, and R. Silverman,*"Gang of Nine" network group for Mersenne prime search*, 1990-1992.**[19]**H. V. Sorenson et al.,*Real-valued fast Fourier transform algorithms*, IEEE Trans. Acoust. Speech Signal Process.**35**(1987), 849-863.**[20]**S. Wagstaff, private communications, 1991.**[21]**Jeff Young and Duncan A. Buell,*The twentieth Fermat number is composite*, Math. Comp.**50**(1988), no. 181, 261–263. MR**917833**, https://doi.org/10.1090/S0025-5718-1988-0917833-8

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y11,
11A51,
11Y05

Retrieve articles in all journals with MSC: 11Y11, 11A51, 11Y05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1994-1185244-1

Article copyright:
© Copyright 1994
American Mathematical Society