Discrete weighted transforms and largeinteger arithmetic
Authors:
Richard Crandall and Barry Fagin
Journal:
Math. Comp. 62 (1994), 305324
MSC:
Primary 11Y11; Secondary 11A51, 11Y05
MathSciNet review:
1185244
Fulltext 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 zeropadding 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,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Second printing; AddisonWesley Series in Computer Science and Information
Processing. MR
0413592 (54 #1706)
 [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
(93a:11106), http://dx.doi.org/10.1090/S00255718199211347174
 [3]
Daniela
Calvetti, A stochastic roundoff error analysis
for the fast Fourier transform, Math. Comp.
56 (1991), no. 194, 755–774. MR 1068824
(91m:65341), http://dx.doi.org/10.1090/S00255718199110688240
 [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
numbertheoretic transforms using cyclotomic polynomials, Math. Comp. 52 (1989), no. 185, 189–200. MR 946602
(90e:11182), http://dx.doi.org/10.1090/S00255718198909466029
 [6]
B. Fagin, Large integer multiplication on hypercubes, J. Parallel Distrib. Comput. 14 (1992), 426430.
 [7]
L. Leibowitz, A simplified arithmetic for the Fermat number transform, IEEE Trans. Acoust. Speech Signal Process. 24 (1976), 356359.
 [8]
W. Li and A. Peterson, FIR filtering by the modified Fermat number transform, IEEE Trans. Acoust. Speech Signal Process. 38 (1990), 16411645.
 [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
(88e:11130), http://dx.doi.org/10.1090/S00255718198708661137
 [11]
H. Nussbaumer, Fast Fourier and convolution algorithms, SpringerVerlag, Heidelberg, 1982.
 [12]
J.
M. Pollard, The fast Fourier transform in a finite
field, Math. Comp. 25 (1971), 365–374. MR 0301966
(46 #1120), http://dx.doi.org/10.1090/S00255718197103019660
 [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
(55 #9603), http://dx.doi.org/10.1090/S00255718197704366628
 [14]
George
U. Ramos, Roundoff error analysis of the fast
Fourier transform, Math. Comp. 25 (1971), 757–768. MR 0300488
(45 #9534), http://dx.doi.org/10.1090/S00255718197103004880
 [15]
Irving
S. Reed and T.
K. Truong, The use of finite fields to compute convolutions,
IEEE Trans. Information Theory IT21 (1975),
208–213. MR 0406677
(53 #10463)
 [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
(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, 19901992.
 [19]
H. V. Sorenson et al., Realvalued fast Fourier transform algorithms, IEEE Trans. Acoust. Speech Signal Process. 35 (1987), 849863.
 [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
(89b:11012), http://dx.doi.org/10.1090/S00255718198809178338
 [1]
 A. Aho, J. Hopcroft, and J. Ullman, The design and analysis of computer algorithms, AddisonWesley, 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), 717722. MR 1134717 (93a:11106)
 [3]
 D. Calvetti, A stochastic roundoff error analysis for the Fast Fourier Transform, Math. Comp. 56 (1991), 755774. 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 numbertheoretic transforms using cyclotomic polynomials, Math. Comp. 52 (1989), 189200. MR 946602 (90e:11182)
 [6]
 B. Fagin, Large integer multiplication on hypercubes, J. Parallel Distrib. Comput. 14 (1992), 426430.
 [7]
 L. Leibowitz, A simplified arithmetic for the Fermat number transform, IEEE Trans. Acoust. Speech Signal Process. 24 (1976), 356359.
 [8]
 W. Li and A. Peterson, FIR filtering by the modified Fermat number transform, IEEE Trans. Acoust. Speech Signal Process. 38 (1990), 16411645.
 [9]
 J. McClellan and C. Rader, Number theory in digital signal processing, PrenticeHall, Englewood Cliffs, NJ, 1979. MR 723867
 [10]
 P. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243264. MR 866113 (88e:11130)
 [11]
 H. Nussbaumer, Fast Fourier and convolution algorithms, SpringerVerlag, Heidelberg, 1982.
 [12]
 J. M. Pollard, The fast Fourier transform in a finite field, Math. Comp. 25 (1971), 365374. MR 0301966 (46:1120)
 [13]
 F. P. Preparata and D. V. Sarwate, Computational complexity of Fourier transforms over finite fields, Math. Comp. 31 (1977), 740751. MR 0436662 (55:9603)
 [14]
 G. U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757786. MR 0300488 (45:9534)
 [15]
 I. Reed and T. Truong, The use of finite fields to compute convolutions, IEEE Trans. Inform. Theory 21 (1975), 208213. MR 0406677 (53:10463)
 [16]
 A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281292. 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, 19901992.
 [19]
 H. V. Sorenson et al., Realvalued fast Fourier transform algorithms, IEEE Trans. Acoust. Speech Signal Process. 35 (1987), 849863.
 [20]
 S. Wagstaff, private communications, 1991.
 [21]
 J. Young and D. Buell, The twentieth Fermat number is composite, Math. Comp. 50 (1988), 261263. 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:
http://dx.doi.org/10.1090/S00255718199411852441
PII:
S 00255718(1994)11852441
Article copyright:
© Copyright 1994
American Mathematical Society
