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

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

PII: S 0025-5718(1994)1185244-1
Article copyright: © Copyright 1994 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia