Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 Free Access

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 $ {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 [Enhancements On Off] (What's this?)

  • [1] A. Aho, J. Hopcroft, and J. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974. MR 0413592 (54:1706)
  • [2] J. P. Buhler, R. E. Crandall, and R. W. Sompolski, Irregular primes to one million, Math. Comp. 59 (1992), 717-722. MR 1134717 (93a:11106)
  • [3] D. Calvetti, A stochastic roundoff error analysis for the Fast Fourier Transform, Math. Comp. 56 (1991), 755-774. MR 1068824 (91m:65341)
  • [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), 189-200. MR 946602 (90e:11182)
  • [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] J. McClellan and C. Rader, Number theory in digital signal processing, Prentice-Hall, Englewood Cliffs, NJ, 1979. MR 723867
  • [10] P. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243-264. MR 866113 (88e:11130)
  • [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 (46:1120)
  • [13] F. P. Preparata and D. V. Sarwate, Computational complexity of Fourier transforms over finite fields, Math. Comp. 31 (1977), 740-751. MR 0436662 (55:9603)
  • [14] G. U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757-786. MR 0300488 (45:9534)
  • [15] I. Reed and T. Truong, The use of finite fields to compute convolutions, IEEE Trans. Inform. Theory 21 (1975), 208-213. MR 0406677 (53:10463)
  • [16] A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292. MR 0292344 (45:1431)
  • [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] J. Young and D. Buell, The twentieth Fermat number is composite, Math. Comp. 50 (1988), 261-263. MR 917833 (89b:11012)

Similar Articles

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

American Mathematical Society