Modular multiplication without trial division

Montgomery, Peter L.

doi:10.1090/S0025-5718-1985-0777282-X

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.