Modular Multiplication Without Trial Division

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

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of computation 1985, Vol.44 (170), p.519-521
Main Author: Montgomery, Peter L.
Format: Article
Language:English
Subjects:
Addition
Arithmetic
Integers
Mathematical induction
Multiplication
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-5718
1088-6842
DOI:10.1090/s0025-5718-1985-0777282-x