Newsgroups: sci.math
From: "David M. Einstein" <Deinst@world.std.com>
Subject: Re: calculating a*b mod c
Date: Tue, 6 Aug 1996 03:54:22 GMT

Jeroen C. van Gelderen wrote:
> 
> Hello,
> 
> Lately I have studied the sources of PGP and I'm looking for more
> information on 'mulmod' functions. Can anyone tell me:
> 
> - What the most efficient function for calculating (a*b) mod c is
> (especcially when doing Public Key operations on long (>=1024 bits) on
> a PC (Intel / Macintosh PPC)?
> 
> - Where to find background information about (fast) (a*b) mod c
> algorithms?

   Montgomery, Peter L, "Modular Multiplication Without 
   Trial Division", _Mathematics of Computation_, Vol 44 
   #170, April 1995, pp 519-521.

 * Crandall R E 1995; "Topics in Advanced Scientific Computation,"
 *          TELOS/Springer-Verlag

> 
> Any pointers will be greatly appreciated.
> 
> 
> Jeroen C. van Gelderen
> gelderen@mediaport.org

==============================================================================

From: rgep@cam.ac.uk (Richard Pinch)
Newsgroups: sci.math,sci.crypt
Subject: Re: calculating a*b mod c
Date: 6 Aug 1996 13:30:32 GMT
Keywords: Montgomery multiplication

In article <4u4nae$1bm@mars.worldonline.nl>, 
gelderen@mediaport.org (Jeroen C. van Gelderen) writes:
|> Lately I have studied the sources of PGP and I'm looking for more
|> information on 'mulmod' functions. Can anyone tell me:
|> - Where to find background information about (fast) (a*b) mod c
|> algorithms?

Try looking at "Montgomery multiplication".  Here's the Latex source
of a brief description 

\newcommand{\congruent}{\equiv}
\subsection{Montgomery multiplication}

Multiplication modulo $N$ in practice requires a division by $N$ to reduce the
product.  The technique of {\em Montgomery} multiplication \cite{Mon:multmod}
\label{Montgomery-mult}
speeds up this step
by replacing the modulus $N$ by another divisor $R$ for which the division step
may be faster: for example, a shift operation if $R$ is a power of 2.

Fix $R > N$ and find $R', N'$ such that $RR' - NN' = 1$.  Numbers $x$ modulo $N$
will be represented by $\bar x = Rx \bmod N$.  Addition and tests for equality
are unchanged by replacing $x$ by $\bar x$.  Initial conversion of values $x$
into $\bar x$ requires multiplication modulo $N$ and a division.

Define a function $REDC(x)$, for $x < N^2$, as follows.

\begin{tabular}{r l}
$y \leftarrow$  & $xN' \bmod R$         \\
$z \leftarrow$  & $(x + yN) / R$        \\
{\bf if} $z<N$  & {\bf return} $z$      \\
{\bf else}      & {\bf return} $z-N$    \\
\end{tabular}

The function $REDC$ converts $\bar x$ back into $x$.

Now the product $\bar x \bar y \congruent Rx Ry \congruent R \overline{xy} \bmod N$,
so $\overline{xy} = REDC(xy)$ can be computed without any division by $N$.

This technique is exploited by Eldridge and Walters \cite{EW:modmult},
\cite{Wal:fastermult}.

Possible online references are at
	http://www.computer.org/pubs/micro/abs96.htm#26mi0696

and in the literature you could try firstly
@ARTICLE(,
        AUTHOR= "Montgomery, Peter L.",
        TITLE=  "Modular multiplication without trial division",
        JOURNAL="Math. Comp.",
        VOLUME= 44,
        NUMBER= 170,
        MONTH=  Apr,
        YEAR=   1985,
        PAGES=  "519--521",
        ANNOTE= {CNT? 43b},
)
and then
@ARTICLE(,
        AUTHOR= "Arazi, B.",
        TITLE=  "On primality testing using purely divisonless operations",
        JOURNAL="Computer J.",
        VOLUMe= 37,
        NUMBER= 4,
        YEAR=   1994,
        PAGES=  "219--222",
        ANNOTE= {42x??? 43x CNT??},
)
@ARTICLE(,
        AUTHOR= "Eldridge, Stephen E. and Walter, Colin D.",
        TITLE=  "Hardware implementation of {Montgomery}'s modular
                        multiplication algorithm",
        JOURNAL="IEEE Trans. Comp.",
        VOLUME= 42,
        NUMBER= 6,
        MONTH=  Jun,
        YEAR=   1993,
        PAGES=  "693--699",
)
@ARTICLE(,
        AUTHOR= "Iwamura, Keiichi and Matsumoto, Tsutomu and Imai, Hidehi",
        TITLE=  "Montgomery's modular-multiplication method and systolic arrays
                        suitable for modular exponentiation",
        JOURNAL="IEICE Trans. Fund. Electron. Comm. Comp. Sci.",
        VOLUME= "E76-A",
        PART=   8,
        MONTH=  Aug,
        YEAR=   1993,
        PAGES=  "1214--1223",
)
@ARTICLE(,
        AUTHOR= "Ko{\c c}, {\c C}etin Kaya and Acar, Tolga and Kaliski jr, Burton S.",
        TITLE=  "Analyzing and comparing {Montgomery} multiplication algorithms",
        JOURNAL="IEEE Micro",
        VOLUME= 29,
        NUMBER= 6,
        MONTH=  Jul,
        YEAR=   1996,
        PAGES=  "26--33",
        NOTE=   "See also {\tt http://www.computer.org/pubs/micro/abs96.htm#26mi0696}",
        ABSTRACT={This article discusses several Montgomery multiplication 
                algorithms, two of which have been proposed before. We describe 
                three additional algorithms, and analyze in detail the space 
                and time requirements of all five methods. These algorithms have 
                been implemented in C and in assembler. The analyses and actual 
                performance results indicate that the Coarsely Integrated Operand 
                Scanning (CIOS) method, detailed in this article, is the most 
                efficient of all five algorithms, at least for the general class 
                of processor we considered. The Montgomery multiplication methods 
                constitute the core of the modular exponentiation operation which 
                is the most popular method used in public-key cryptography for 
                encrypting and signing digital data.},
)
@ARTICLE(,
        AUTHOR= "Montgomery, Peter L. and Granlund, Torbjorn",
        TITLE=  " Division by integer invariants using multiplication",
        JOURNAL="SIGPLAN Notices",
        VOLUME= 29,
        NUMBER= 6,
        YEAR=   1994,
        PAGES=  "61--72",

)
@ARTICLE(,
        AUTHOR= "Walter, Colin D.",
        TITLE=  "Still faster modular multiplication",
        JOURNAL="Electron. Lett.",
        VOLUME= 31,
        NUMBER= 4,
        MONTH=  "Feb",
        YEAR=   1995,
        PAGES=  "263--264",
)

Richard Pinch;	Queens' College, Cambridge