Modular multiplication without trial division. (English) Zbl 0559.10006

Montgomery, Peter L.

Math. Comput. 44, 519-521 (1985).

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.

MSC:

11A63	Radix representation; digital problems
68W99	Algorithms in computer science

Keywords:

modular multiplication; modular arithmetic