Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ N > 1$. 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.

References [Enhancements On Off] (What's this?)

  • [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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y16

Retrieve articles in all journals with MSC: 11Y16

Additional Information

Keywords: Modular arithmetic, multiplication
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society