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