Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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?)


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/S0025-5718-1994-1185244-1
PII: S 0025-5718(1994)1185244-1
Article copyright: © Copyright 1994 American Mathematical Society