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 $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.
- J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI https://doi.org/10.1017/s0305004100049252
- J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, DOI https://doi.org/10.1007/bf01933667
- 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, DOI https://doi.org/10.1016/0898-1221%2883%2990133-5
- 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, DOI https://doi.org/10.1145/359340.359342
- J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI https://doi.org/10.1145/322217.322225 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
Keywords:
Modular arithmetic,
multiplication
Article copyright:
© Copyright 1985
American Mathematical Society