Discrete weighted transforms and large-integer arithmetic
HTML articles powered by AMS MathViewer
- by Richard Crandall and Barry Fagin PDF
- Math. Comp. 62 (1994), 305-324 Request permission
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 ${2^{{2^m}}} + 1$, or Mersenne Numbers ${2^q} - 1$, 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.References
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
- 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, DOI 10.1090/S0025-5718-1992-1134717-4
- Daniela Calvetti, A stochastic roundoff error analysis for the fast Fourier transform, Math. Comp. 56 (1991), no. 194, 755–774. MR 1068824, DOI 10.1090/S0025-5718-1991-1068824-0 K. Chen, A New Record: The largest known prime number, IEEE Spectrum 27 (1990), 47.
- 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, DOI 10.1090/S0025-5718-1989-0946602-9 B. Fagin, Large integer multiplication on hypercubes, J. Parallel Distrib. Comput. 14 (1992), 426-430. L. Leibowitz, A simplified arithmetic for the Fermat number transform, IEEE Trans. Acoust. Speech Signal Process. 24 (1976), 356-359. W. Li and A. Peterson, FIR filtering by the modified Fermat number transform, IEEE Trans. Acoust. Speech Signal Process. 38 (1990), 1641-1645.
- 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
- Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7 H. Nussbaumer, Fast Fourier and convolution algorithms, Springer-Verlag, Heidelberg, 1982.
- J. M. Pollard, The fast Fourier transform in a finite field, Math. Comp. 25 (1971), 365–374. MR 301966, DOI 10.1090/S0025-5718-1971-0301966-0
- F. P. Preparata and D. V. Sarwate, Computational complexity of Fourier transforms over finite fields, Math. Comp. 31 (1977), no. 139, 740–751. MR 436662, DOI 10.1090/S0025-5718-1977-0436662-8
- George U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757–768. MR 300488, DOI 10.1090/S0025-5718-1971-0300488-0
- Irving S. Reed and T. K. Truong, The use of finite fields to compute convolutions, IEEE Trans. Inform. Theory IT-21 (1975), 208–213. MR 406677, DOI 10.1109/tit.1975.1055352
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355 D. Slowinski and P. Gage, private communication (1992). 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. H. V. Sorenson et al., Real-valued fast Fourier transform algorithms, IEEE Trans. Acoust. Speech Signal Process. 35 (1987), 849-863. S. Wagstaff, private communications, 1991.
- Jeff Young and Duncan A. Buell, The twentieth Fermat number is composite, Math. Comp. 50 (1988), no. 181, 261–263. MR 917833, DOI 10.1090/S0025-5718-1988-0917833-8
Additional Information
- © Copyright 1994 American Mathematical Society
- 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