Logarithmi Speed Modular Multipli ation
Colin D. Walter

Department of Computation
UMIST
PO Box 88
Man hester M60 1QD, UK
www. o.umist.a .uk

A design for logarithmi speed modular multipli ation is
given and a omparison made with the best implementations of existing, more standard algorithms by Bri kell and Montgomery. A 40-foldin rease in speed is reported by using hip area at the limit of urrent
te hnology.
Abstra t.

Key words:

tography.

1Computer Arithmeti , Modular Multipli ation, RSA ryp-Introdu tion

Most modular multipli ation algorithms in urrent use perform their arithmeti
on n-digit inputs in O(n log n) time and O(n) spa e using what amounts to thestandard paper and pen il method with a redundant representation of the numbers [1℄. Mu h work has gone into improving the eÆ ien y of these algorithms
and good estimates of their speeds in terms of gate delays are now available [3℄,[9℄.
Many ryptographi appli ations, su h as de ryption of RSA [5℄, require highspeed modular arithmeti on large numbers. It is presumably well understoodthat modular multipli ation in parti ular an be performed on inputs with O(n)digits in O(log n) time at the pri e of O(n2 ) spa e. Here we give details for thisand quantify upper bounds on the time and spa e more pre isely in order tosee if a hange of algorithm an reasonably be made to trade spa e for speed
and yet remain within feasible te hnology. Pipelining the algorithm in reases
the throughput to 1 modular multipli ation per O(1) lo k y les, although thelaten y is still O(log n).
In a previous work [10℄ the author showed how a systoli array ould be built
for modular multipli ation with a throughput of one produ t per lo k y le ona very fast lo k (O(1) time), also using O(n2 ) spa e. However, it requires O(n)time between the input and output of orresponding digits. Using pipelining as
noted above, the algorithm here would provide essentially the same performan e

2as the systoli array the same throughput for the same ost in area - but themu h lower laten y of O(log(n)) time instead of O(n).
In a related work [6℄, Shand et al. des ribe a programmable array implementation of Montgomery's algorithm [4℄. The details of their implementation are
not given, but the performan e would appear to be similar to that of the systoli
array [10℄ if they have the ability to pipeline a number of modular multipli ations to use the hardware simultaneously. Thus the hardware here should again
provide a signi ant advantage. Their measure of time is an absolute one using aparti ular te hnology and gives an O(n) time for laten y, an order of magnitude
slower than what is des ribed here.
Upper and lower bounds on the area/time eÆ ien y of multipli ation are
given by Brent and Kung [1℄. By employing the dis rete Fourier transform, they
are able to des ribe a method that would provide modular multipli ation usingO(n log n) area and O(pn log n) time. This is intermediate in terms of botharea and time between the method here and the standard methods of [2℄ and[3℄. With its smaller produ t of AreaTime, as well as an absolute area thatsuits urrent te hnology, it is probably an over negle ted alternative. It is worth
noting that minimum AreaTime is believed to in rease as time is redu ed toits asymptoti minimum, and the area here still appears to be the best for the
logarithmi time it takes [7℄.
It turns out that ryptographi appli ations requiring around 500-bit numbers are well served by logarithmi methods as far as speed is on erned, although
not so well spa e-wise as far as urrent te hnology is on erned. Without e ort, a40-fold in rease in speed is obtained here for a 500-fold in rease in area, resulting
in the requirement for 5106 XOR gates or equivalent for a H/W implementation. Su h hardware is appropriate for heavy entralised RSA en ryption andde ryption using the same key or keys ontinuously, and is just about feasible
nowadays using redundan y in wafer-s ale integration te hniques.

2

The Algorithm

We split the omputation of (AB ) mod M into six distin t phases, namely thevarious fun tion appli ations in rnd(fra t((AB )(1=M ))M ) where fra t
dis ards the integer part of a real number, and retains the non-negative fra tional part, and rnd rounds a real to the nearest integer. Here fra t is dis arding (AB ) div M so that multipli ation by M leaves (AB ) mod M . Various
approximations are made, whi h leave a small fra tional part to be rounded o .
In parti ular, we assume that M 1 is already known to just over 3m pla es
after the point where m is the number of digits in M , A and B . Of ourse,
the rst m (approximately) of these digits are zero. Then (AB )(1=M ) has
an a ura y to over m pla es after the point, so that multiplying its fra tionalpart by M will give a result that is a urate to within 14 , say. Rounding to thenearest integer will then give the orre t answer. The pre ise a ura y neededin the al ulations is not important for the dis ussion here, but is easy to nd.

IEE Ele troni s Letters, vol.

30, No 17, 1994, pp. 1397-1398

3

The only requirement is that suÆ ient a ura y is employed to perform exa t
rounding by inspe ting a small onstant number of fra tional digits.
A urate appli ation of fra t takes time. A hange of 1 in the value of AB
hanges (AB )(1=M ) by about 1 in the position m pla es after the point.
Hen e fra t may need to examine just more than the rst m pla es after the
point for omplete a ura y. By examining only one or two su h pla es, fra t
may be out by 1, so that the end result di ers by M from (AB ) mod M . The
output is then in the range 0 to 2M rather than 0 to M . This is a typi al penalty
of saving time, but is not a problem in RSA ryptography where a large numberof onse utive modular multipli ations are performed. In su h ases, the orre t
range 0 to M need only be a hieved after the last operation. We will assume
this approximation to fra t is used.

3

The Notation

Using a redundant number system enables addition to be done with boundedarry propagation. We assume A and B and all intermediate results have su hforms, but not M or 1=M , whi h we will suppose to be in binary form. We will
also assume that ea h multipli ation is done sequentially on the same hardware.
The prohibitive ost of the extra hardware does not seem to warrant the small
extra speed a hievable by trying to do more at on e.
Let b be the base of our redundant representation. We may assume A < 2M
and B < 2M . Then m = dlogb 2Me is the maximum number of (redundant)
digits in A or B , and n = dlog2 Me the number of bits in the modulus M .
The largest multipli ation involved here is that by 1=M . So we need hardware
to perform a 2m digit2n bit multipli ation. The produ t AB of m digit redundant numbers an be split fairly easily to use this hardware if the degree of
redundan y is not unreasonable.

4

The Largest Multipli ation

The 2m digit2n bit multipli ation generates 4mn digits, with up to 2n of thesethrepresenting the same power of b. Here 18 of them will be dis arded when fra t
is applied be ause they over ow into the integer part. Also, almost half of them
represent su h low powers of b that they an only in uen e the rounding pro ess
through arry propagation: those with indi es below about m logb m will makea total di eren e of less than 12 to the nal out ome and so an be ignored. Thus
we an assume that only about 2mn digits need adding together. These an be
redu ed to 2 redundantly represented numbers using a tree stru ture of 3-to-2
redundant number adders built from 3-to-2 bit adders (Figure 1). This tree has
a maximum depth of about log3=2 n 3-to-2 bit adders and involves an area of
one 3-to-2 bit adder for every bit removed in transforming the input digits into
output digits. This is essentially Walla e's onstru tion [8℄.
In fa t, the 3-to-2 adders an be more losely pa ked than ounting a depth of
3 gates ea h as illustrated s hemati ally in Figure 2. Some inputs are not needed

4
1



2

2



^

^

_

2

1

(a) Full Adder for Bits(b) Full Adder for Numbers

Fig. 1.



3-to-2 Adder


















































































(a) 4-to-2 Adder(b) 15-to-2 Adder with depth of 12 gatesFig. 2.

Pa king of Adders

immediately and some outputs are generated early. Hen e adders like the 15-to2 adder in the gure an be onstru ted with depths of lose to log6=5 n=2 foran n-to-2 adder. In RSA ryptography we an expe t n to be a little in ex essof 512 and so about 32 gates depth will suÆ e to redu e the 2n summands ofthe multipli ation to 2 redundant numbers. A further 2 or at most 3 gates willredu e this to a single redundant number (e.g. onsider using 2 binary registers
to hold a redundant number).
Now let us onsider the initialisation time to reate the summands for adding.
Ea h input bit needs to be distributed to 2n di erent positions for ANDing witha bit from the other multipli and. This an be done by a tree of multiplexers of
depth no worse than, say, log4 2n, whi h is about 5 in our ase. However, only
one digit position has as many as 2n digits to sum, so that digits an be routed
preferentially there in order to ut the overall depth. Adding the time of 2 gates

IEE Ele troni s Letters, vol.

30, No 17, 1994, pp. 1397-1398

5

for setup and hold times of registers, plus one or two gates to enable the hardware
to be used for the various multipli ations leads to a grand total of about 40 gatesalong a riti al path. With 3 multipli ations being done to perform the modular
multipli - ation, we obtain 120 gates delays altogether over the three lo k y lesneeded.

5Comparison with Standard Implementations

The standard algorithms when pushed to their limits, require a onstant depthof 9 or 10 gates per lo k y le (see [9℄ and [3℄), with marginally over n lo k
y les per modular multipli ation. For n = 512 or so, this means the method
above provides a forty-fold in rease in speed, whi h almost doubles every time nis doubled. Indeed, repeating the al ulations shows a speed advantage for word
lengths right down to n = 8, at whi h point a non-redundant representation
would be employed to do the whole multipli ation in a single lo k ti k.
What is the ost? The area of the standard algorithm is linear, as is thetime. However, the logarithmi time for the new algorithm requires 0(n2 ) area.
Spe i ally, about 20n gates for the standard algorithms (more for the fastest
implementations), and 20n2 here if two binary numbers provide the redundan y,with linear hanges to both for other representations. Overall, the logarithmi
method is therefore n times more expensive in area, requiring some 5106 gates
for typi al hoi es of n  5102 . This is just about possible with urrent te hnology.
We have negle ted the e e t of long wire lengths. Along the riti al path
this will typi ally be omparable with the edge length of the area of the hip
being utilised in both algorithms be ause information needs to be transportedpright a ross the hip.
For the lassi al algorithms, this will be of length O( n),pand so adds O(n n) time to the multipli ation, whereas for the s heme here
the length is O(n), whi h adds just O(n) to the total time. Thus wire length
eventually dominates the time in both algorithms, but is always mu h greaterfor the standard algorithms.
Finally, we note that some of the hardware stands idle at the end of ea hmultipli ation y le. It is only the middle digits in the output whi h required
the full depth of the hardware for their al ulations. The end digits an beprodu ed with almost zero depth. However, on average a typi al digit requires
the summation of half the number of inputs that the middle digits have. The
tree stru ture of the addition means that, although only half the hardware isneed for this, its depth is just one gate less than for a middle digit, so that it
takes almost the same time as the worst ase. Hen e, overall the hardware is
running at almost full apa ity. The only improvement in use ould be throughpipelining, as mentioned earlier.

66Con lusion

It is now possible to onsider logarithmi time (Walla e tree) VLSI implementations for modular multipli ation. This stret hes urrent te hnology to the limit,
but provides nearly two orders of magnitude in rease in speed when inputs have
500 or so bits, as typi ally in RSA ryptography.

Referen es[1℄ R.P. Brent & H.T. Kung, The Area-Time Complexity of Binary Multipli ation,
J.ACM, vol. 28, 1981, pp 521-534.
[2℄ E. F. Bri kell, A Fast Modular Multipli ation Algorithm with Appli ation to Two
Key Cryptography, Advan es in Cryptology - CRYPTO '82, ed. Chaum et al.,Plenum, 1983, pp. 51-60.
[3℄ S.E. Eldridge & C.D. Walter, Hardware Implementation of Montgomery's Modular
Multipli ation Algorithm, IEEE Trans. Computers, vol. 42, 1993, pp. 693-699.
[4℄ P.L. Montgomery, Modular Multipli ation without Trial Division, Mathemati s ofComputation, vol. 44, 1985, pp. 519-521.
[5℄ R. L. Rivest, A. Shamir & L. Adleman, A Method for obtaining Digital Signatures
and Publi -Key Cryptosystems, Comm. ACM, vol. 21, 1978, pp. 120-126.
[6℄ M. Shand, P. Bertin & J. Vuillemin, Hardware speedups in long integer multipli ation, ACM SigAr h, vol. 19 no. 1, Mar h 1991, pp 106-113.
[7℄ B. Sugla & D.A. Carlson, Extreme Area-Time Tradeo s in VLSI, IEEE Trans.
Comput., vol. 39, 1990, pp 251-257.
[8℄ C.S. Walla e, A suggestion for a fast multiplier, IEEE Trans. Ele . Comput., vol.
EC-13, 1964, pp 14-17.
[9℄ C.D. Walter, Faster Modular Multipli ation by Operand S aling, Advan es in Cryptology - CRYPTO '91, Le ture Notes in Computer S ien e, vol. 576, SpringerVerlag, 1992, pp. 313-323.
[10℄ C.D. Walter, Systoli Modular Multipli ation, IEEE Trans Computers, vol. 42,
1993, pp 376-8.