Modular multiplication without trial division

Montgomery, Peter L.

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

Modular multiplication without trial division
HTML articles powered by AMS MathViewer

by Peter L. Montgomery PDF

Math. Comp. 44 (1985), 519-521 Request permission

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

J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 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 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 10.1016/0898-1221(83)90133-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 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 10.1145/322217.322225

Abstracts Amer. Math. Soc.