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 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 354514, https://doi.org/10.1017/s0305004100049252
- [2] J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, https://doi.org/10.1007/bf01933667
- [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, https://doi.org/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, https://doi.org/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, https://doi.org/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:
https://doi.org/10.1090/S0025-5718-1985-0777282-X
Keywords:
Modular arithmetic,
multiplication
Article copyright:
© Copyright 1985
American Mathematical Society