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
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 $ {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

Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society