Modular multiplication without trial division

Author:
Peter L. Montgomery

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

MSC:
Primary 11Y16

MathSciNet review:
777282

Full-text PDF Free Access

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.**76**(1974), 521–528. MR**0354514****[2]**J. M. Pollard,*A Monte Carlo method for factorization*, Nordisk Tidskr. Informationsbehandling (BIT)**15**(1975), no. 3, 331–334. MR**0392798****[3]**George B. Purdy,*A carry-free algorithm for finding the greatest common divisor of two integers*, Comput. Math. Appl.**9**(1983), no. 2, 311–316. MR**719078**, 10.1016/0898-1221(83)90133-5**[4]**R. L. Rivest, A. Shamir, and L. Adleman,*A method for obtaining digital signatures and public-key cryptosystems*, Comm. ACM**21**(1978), no. 2, 120–126. MR**700103**, 10.1145/359340.359342**[5]**J. T. Schwartz,*Fast probabilistic algorithms for verification of polynomial identities*, J. Assoc. Comput. Mach.**27**(1980), no. 4, 701–717. MR**594695**, 10.1145/322217.322225**[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:
http://dx.doi.org/10.1090/S0025-5718-1985-0777282-X

Keywords:
Modular arithmetic,
multiplication

Article copyright:
© Copyright 1985
American Mathematical Society