On decreasing the computing time for modular arithmetic

1 October 1971

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02724847,p. 126-128
https://doi.org/10.1109/swat.1971.20

Abstract

In this paper it is shown that by suitably modifying Garner's algorithm for applying the Chinese Remainder Theorem to optimally employ the fast multiplication techniques of Schönhage and Strassen, one can often decrease the computing time of algebraic algorithms employing modular (congruence, residue) arithmetic.

Keywords

DIGITAL ARITHMETIC
TELEPHONY
LABORATORIES
COMPUTER SCIENCE
HARDWARE
ALGORITHM DESIGN AND ANALYSIS
FAST FOURIER TRANSFORMS

This publication has 4 references indexed in Scilit:

On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
Journal of the ACM, 1971
The calculation of multivariate polynomial resultants
Published by Association for Computing Machinery (ACM) ,1971
Multiplikation großer Zahlen
Computing, 1966
The Residue Number System
IEEE Transactions on Electronic Computers, 1959