×

zbMATH — the first resource for mathematics

Modular multiplication without trial division. (English) Zbl 0559.10006
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
PDF BibTeX XML Cite
Full Text: DOI