Modular multiplication without trial division

Author:
Peter L. Montgomery

Journal:
Math. Comp. **44** (1985), 519-521

MSC:
Primary 11Y16

DOI:
https://doi.org/10.1090/S0025-5718-1985-0777282-X

MathSciNet review:
777282

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let . We present a method for multiplying two integers (called *N-residues*) modulo *N* while avoiding division by *N*. *N*-residues are represented in a nonstandard way, so this method is useful only if several computations are done modulo one *N*. The addition and subtraction algorithms are unchanged.

**[1]**J. M. Pollard, "Theorems on factorization and primality testing,"*Proc. Cambridge Philos. Soc.*, v. 76, 1974, pp. 521-528. MR**0354514 (50:6992)****[2]**J. M. Pollard, "A Monte Carlo method for factorization,"*BIT*, v. 15, 1975, p. 331-334. MR**0392798 (52:13611)****[3]**George B. Purdy, "A carry-free algorithm for finding the greatest common divisor of two integers,"*Comput. Math. Appl.*v. 9, 1983, pp. 311-316. MR**719078 (85a:11026)****[4]**R. L. Rivest, A. Shamir & L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems,"*Comm. ACM*, v. 21, 1978, pp. 120-126; reprinted in*Comm. ACM*, v. 26, 1983, pp. 96-99. MR**700103 (83m:94003)****[5]**J. T. Schwartz, "Fast probabilistic algorithms for verification of polynomial identities,"*J. Assoc. Comput. Mach.*, v. 27, 1980, pp. 701-717. MR**594695 (82m:68078)****[6]**Gustavus J. Simmons, "A redundant number system that speeds up modular arithmetic," Abstract 801-10-427,*Abstracts Amer. Math. Soc.*, v. 4, 1983, p. 27.

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y16

Retrieve articles in all journals with MSC: 11Y16

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1985-0777282-X

Keywords:
Modular arithmetic,
multiplication

Article copyright:
© Copyright 1985
American Mathematical Society