A Verification of Brickell’s
Fast Modular Multiplication Algorithm

Colin D. Walter & Stephen E. Eldridge
Department of Computation
UMIST
PO Box 88
Manchester M60 1QD, UK
www.co.umist.ac.uk

Abstract. This paper refers to the algorithm and its hardware implementation described by Brickell [1] for modular multiplication in N +10clock pulses where N is the number of bits in the binary integers involved. That paper uses a delayed carry representation which consists of
two registers of N bits each − one for the uncarried carries. Of course,
up to N clocks ticks may eventually be required to assimilate the carries
at the end of the computation.
Several sources of possible error are reported here − one in the hardware, one in the specification which the intended hardware satisfies, andone in the definition of the control variables T1 and T2 . Our main contributions are the supply of further detail to remove such ambiguities, adetermination of the minimum number of extra bits required during the
calculation, a verification of the more detailed system, and its extension
to an integer division procedure.
The existence of a proof enables it to be used reliably for its intended
purpose in applications such as cryptography [5], where attempts havealready been made to use the algorithm or similar methods in RSA chips[4]. The reduced number of extra bits required also marginally increases
the speed.
Concurrent work by J. K. Gibson [2] describes different additional detailto make Brickell’s algorithm work. What is supplied in this article webelieve to be more natural than Gibson’s in that the standard delaycarry addition stands unaltered here, and the minimum number of clock
pulses required remains clear.
Key words: RSA algorithm, fast multiplication, verification, cryptography, computer arithmetic.
C.R. Categories: F.2.1, B.7.1, E.3.

2International J. of Computer Mathematics, vol. 33, 1990, pp. 153-169

1Introductory Detail

1.1Type Definitions

We use a slightly extended version of Pascal to describe the main parts of ourversion of Brickell’s algorithm [1]. Let N be the number of bits needed for each
input integer. An additional Q+1 (≥ 6) bits of working space are required sothat the natural size of binary integers becomes N +Q+1 bits. Brickell used 11
extra bits.
type BitIndex= 0..N+Q ;BinaryInteger= array[BitIndex] of Boolean ;DelayCarryInteger = array[1..2] of BinaryInteger ;Every D : DelayCarryInteger is required to satisfy the data invariant(not D[2, 0]) & (not(D[1, I−1] & D[2, I]) for I in 1 .. N +Q)
Here D[2] can be considered to contain the unassimilated carries resulting fromthe addition of P
two numbers of type DelayCarryInteger. The integer represented by D is I∈ BitIndex (D[1, I]+D[2, I])×2I where T rue and F alse are interpreted as 1 and 0 respectively. We will not, in fact, distinguish Booleans,
BinaryIntegers and DelayCarryIntegers from their values as integers unless the context makes it necessary. Maximum values are given by choosing
D[2, I] = 1 rather than D[1, I−1] = 1 in the data invariant. So,
Lemma 1 The maximum value of a delay carry integer with L bits is
2L + 2L−1 − 2.
1.2

The Half Adder

Brickell describes a half adder which takes as input two binary integers (X andY here) and produces as output two binary integers. We stress the relationshipbetween the output integers by combining them into a delay carry integer D.
This must then necessarily satisfy the data invariant above. The procedure
HalfAdd( X,Y: BinaryInteger; var D: DelayCarryInteger; var Overflow: Boolean)achievesbyandD + Overf low×2N +Q+1 =X +Y
D[2] + Overf low×2N +Q+1 = 2(X and Y )D[1]=X xor Y

which are interpreted bitwise. Software or hardware for the above can be executed in one clock pulse by performing the bit operations in parallel. To distinguish different overflows it is sometimes convenient to describe the one here asD[2, N +Q+1], although the register contains no such bit. Easily,
Lemma 2i) Suppose that 2L divides both inputs of HalfAdd. Then 2L divides
both the outputs D[1] and D[2].

C. D. Walter & S. E. Eldridge

3ii) Suppose that 2L divides one input of HalfAdd. Then 2L+1 divides
the output D[2].
Lemma 3i) The outputs D[2, I+1] and D[1, I] of HalfAdd depend only on the
inputs X[I] and Y [I]. In particular, the Overflow parameter returned
only depends on X[N +Q] and Y [N +Q].
ii) For delay carry integers X, Y and D, the result of the call
HalfAdd(X[1], Y [1], D, Overf low) satisfies (D[2] & X[2]) = 0 and(D[2] & Y [2]) = 0.

In[I]

z

}|

B ∗ [2, I+1]∨
Bits1




∨


∧

B ∗ [1, I]

D[1, I]⊕∧

Bits2

Or[I+1]{K ∗ [I]

D[2, I+1]










⊕

∨

Bits3

Or[I]

⊕

∧









∧









⊕
⊕

∧
Sum[2, I+1]|

Sum[1, I]{z

Out[I]}

Fig. 1. Definitions of In[I], Or[I] and Out[I].

1.3

Adding Three Numbers

The main step in the modular multiplication algorithm requires the addition ofa binary integer and two delay carry integers. The precise specification is messy
to give, and so we make use of the code given to produce the results of thissection. A hardware implementation is given in Figure 2 of [1] using a cascadeof 5 half adders, but with an extra shift. The repeated unit without the shift isgiven in Figure 1.

4

International J. of Computer Mathematics, vol. 33, 1990, pp. 153-169

procedure Add(D,B∗ : DelayCarryInteger ; K∗ : BinaryInteger ;var Sum: DelayCarryInteger ; var Overflows: Integer);{ Post-Condition : Sum + Overflows*2N+Q+1 = B∗ +D+K∗ }var

Bits1 , Bits2 , Bits3 : BinaryInteger ;R1 , R2 , R3 , R4
: DelayCarryInteger ;Overflow1 , Overflow2 , Overflow3 , Overflow4 , OverflowSum: Boolean ;begin { Add }HalfAdd(K∗ , D[1], R1 , Overflow1 ) ;HalfAdd(R1 [1],B∗ [1],R2 ,Overflow2 ) ;Bits1 := D[2] OR R1 [2] ;HalfAdd(R2 [1],Bits1 ,R3 ,Overflow3 ) ;Bits2 := B∗ [2] OR R2 [2] ;HalfAdd(R3 [1],Bits2 ,R4 ,Overflow4 ) ;Bits3 := R3 [2] OR R4 [2] ;HalfAdd(R4 [1],Bits3 ,Sum,OverflowSum ) ;Overflows := Ord(Overflow1 )+Ord(Overflow2 )+Ord(Overflow3 )+Ord(Overflow4 )+Ord(OverflowSum )end ; { Add }Here the OR is interpreted componentwise for each BitIndex. For each callof it the ANDed inputs give 0 by Lemma 3(ii), and so the output is their sum.
Neglecting the Overf lows which may be regarded as [N +Q+1]-components,
the code of Add is now equivalent to 8 assignments each of which just adds
two binary integers, and so is easy to verify. Note from the figures that thisprocedure can be implemented by hardware which operates in a single clock
pulse. The following results are straightforward:
Lemma 4If 2L divides the inputs D[1], B ∗ [1] and K ∗ of Add, and 2L+1 divides the
inputs D[2] and B ∗ [2], then 2L divides the output Sum[1] of Add and2L+3 divides the output Sum[2]. In particular, Sum[2, 0] = Sum[2, 1] =Sum[2, 2] = 0.
Lemma 5i) Suppose 2L divides each of the five input binary integer componentsof the parameters D, B ∗ and K ∗ of Add. Then 2L divides both theoutputs Sum[1] and Sum[2].
ii) Suppose 2L divides at least four of the five input binary integer
components of the parameters D, B ∗ and K ∗ of Add. Then 2L+2
divides the output Sum[2].
Lemma 6i) The input bits of Add which contribute to the output bits Sum[1, I]
and Sum[2, I+1] are D[1, J], B ∗ [1, J], K ∗ [J], for J in I−2 .. I andD[2, J] and B ∗ [2, J] for J in I−1 .. I.

C. D. Walter & S. E. Eldridge

5ii) The input bits which contribute to overflow in Add are D[1, J],B ∗ [1, J] and K ∗ [J] for J in N +Q−2 .. N +Q, and D[2, J], B ∗ [2, J]
for J in N +Q−1 .. N +Q.
1.4

The Top Bits

Algorithms computing a result modulo C often progress by subtracting a multiple of C when possible. Where numbers are represented by registers of lengthL, subtraction of C is the same as addition of K = 2L − C, providing that there
is a single overflow of 2L which is neglected. Brickell’s algorithm does this, predicting in advance the overflows when the procedure Add is executed, as well as
the overflow when a subsequent shift is applied.
By Lemma 6 the Add overflow is given by looking at the top 3 bits only of the
inputs K ∗ , B ∗ [1] and D[1], and the top 2 bits only of B ∗ [2] and D[2]. For thisreason we look at 3-bit delay carry integers satisfying the usual data invariant.
By adding a subscript 3, all our definitions and procedures can be repeatedfor BitIndex3 = 0 .. 2 instead of BitIndex. Now Add3 applied to the mostsignificant bits of the input to Add will predict the overflows of Add correctly.
This creates a need for a function T op3Bits which will copy bits with indices in
the range N +Q−2 .. N +Q to a new type with indices 0 .. 2, discarding the rest.
The data invariant for the DelayCarryInteger3 output is obtained by forcing
the [2, 0]-component to be F alse. All this applies also with subscript I referring
to BitIndexI = [0 .. I−1]. For example,
Definition. For natural numbers I, the function
T opIBits(D : DelayCarryIntger) : DelayCarryIntegerI
is specified by T opIBits(D)[1] = D[1] div 2N +Q+1−I and T opIBits(D)[2] =2×(D[2] div 2N +Q+2−I ).
There is an analogous definition for T opIBits applied to a variable of type
BinaryInteger. Now, by Lemma 6,
Lemma 7i) If I ≥ 3 then, for the same input,
Add(D, B ∗ , K ∗ , Sum, Overf lows)
and
AddI (T opIBits(D), T opIBits(B ∗ ), T opIBits(K ∗ ), SumI , Overf lowsI )will satisfy Overflows = OverflowsI .
ii) If I ≥ 4 then, for the same input,
Add(D, B ∗ , K ∗ , Sum, Overf lows)
and
AddI (T opIBits(D), T opIBits(B ∗ ), T opIBits(K ∗ ), SumI , Overf lowsI )will satisfy Sum[1, N +Q] = SumI [1, I−1], Sum[2, N +Q] = SumI [2, I−1],
and Overflows = OverflowsI .

6International J. of Computer Mathematics, vol. 33, 1990, pp. 153-169

A numerical characterisation of overflows is useful. Working with the numbers
the bits represent rather than with the bits themselves is more elegant, and ourversion of Brickell’s algorithm is written in this way. However, Gibson [2] deals
directly with the overflow bits and, although it is not stated, we presume Brickell
also meant to refer to the overflow bits of the delay carry integers rather thanoverflows in their numerical equivalents.
Lemma 8i) The value of the overflows in Add is[T op3Bits(D)+T op3Bits(K ∗ )+T op3Bits(B ∗ )] div 8ii) The sum of the output bits Sum[1, N +Q] and Sum[2, N +Q] of Add
is[T op4Bits(D)+T op4Bits(K ∗ )+T op4Bits(B ∗ )] div 8−2( [T op3Bits(D)+T op3Bits(K ∗ )+T op3Bits(B ∗ )] div 8 )By Lemma 7(i), the proof of (i) can be simplified by first noting that it
suffices to look at the corresponding call to Add3 . From the analogue to Lemma
4 for Add3 (just take N +Q = 2 there), we have the output Sum3 of Add3
satisfying Sum3 [2, 0] = Sum3 [2, 1] = Sum3 [2, 2] = 0, i.e. Sum3 [2] = 0. So
Sum3 = Sum3 [1] and the maximum value of Sum3 is therefore that of Sum3 [1],namely 7. Thus Sum3 = Sum3 mod 8 and by the post-condition for Add reduced
modulo 8, Sum3 = (T op3Bits(D)+T op3Bits(K ∗ )+T op3Bits(B ∗ )) mod 8. The
post-condition for Add now taken div 8 gives the number of overflows as thatstated since Sum3 div 8 = 0.
Now consider part (ii). Suppose we ignore the topmost bits, i.e. those ofindex N +Q, so that T op3Bits extracts the bits of index N +Q−3 .. N +Q−1.
Then the expression of (i) would be the “overflow” from the N +Q−1st placerather than the N +Qth. The same “overflow” is obtained by applying T op4Bits
properly instead of T op3Bits, if we ignore the input bits of index N +Q. This
new expression, which is the first term in (ii), therefore represents all bits flowing
into the N +Qth place, both those coming from direct input and those passing
up the adder from lower positions. Some of these bits combine in pairs to givethe overflow bits from the N +Qth position, whilst the remainder give the output
from the N +Qth position. Hence this last output is given by subtracting twice
the number of overflow bits (as in (i)) from the number of bits flowing into the
N +Qth place.
Lemma 9a) If 24 > T op4Bits(D)+T op4Bits(K ∗ )+T op4Bits(B ∗ ) ≥ 16 then exclusively eitheri) there is one overflow from Add, orii) the two output bits from Add with index N +Q are 1;b) If 16 > T op4Bits(D)+T op4Bits(K ∗ )+T op4Bits(B ∗ ) ≥ 8 theni) there is no overflow from Add, andC. D. Walter & S. E. Eldridge

7ii) one output bit from Add with index N +Q is 1, the other 0;c) If 8 > T op4Bits(D)+T op4Bits(K ∗ )+T op4Bits(B ∗ ) theni) there is no overflow from Add, andii) neither output bit from Add with index N +Q is 1.
The proof of this depends on the previous lemma. Because in general
T op4Bits(S) ≥ 2×T op3Bits(S), it is clear from Lemma 8(i) that in cases (b)and (c) there can be no overflows, and in case (a) at most 1 overflow. As remarked
in the proof of Lemma 8(ii), the expression[T op4Bits(D)+T op4Bits(K ∗ )+T op4Bits(B ∗ )] div 8
gives the sum of the output bits with index N +Q and the overflow bits. In case(a) this amounts to 2, which can be split only as expressed in (i) or (ii). In cases(b) and (c) it amounts to 1 and 0 respectively, so that there is no overflow, as
stated in the parts (i), and the output bits must be as stated in the parts (ii).

2

The Modular Multiplication Algorithm

The modular multiplication algorithm M can now be described. Several minorchanges have been introduced which make it different from Brickell’s description:
the loop is more naturally entered at a different point, the number of extra bits
required beyond the N of the inputs is made variable (Q+1 instead of 11), andthe Booleans T1 and T2 have been accumulated into a delay carry integer T whichalmost gives the result of integer division. Of course, if the integer quotient is
not required then T may be discarded.
One further possible difference between this algorithm and that given by
Brickell is worth noting. It concerns the definition of the Booleans T [1, J−1]
and T [2, J] − Brickell’s T1 and T2 . Our definition using the function T op4Bits
ignores the bit which might have formed the [2, 0]-component in the result, but
Brickell seems to include it. As it does not contribute to any overflows it must be
ignored if a numerical characterisation of the different cases is used as here. We
must assume therefore that when Brickell mentions overflows he is referring to
overflow in a delay carry representation not a binary integer representation. He
is not explicit on this distinction and so readers could be misled to an incorrect
definition of the Booleans T1 and T2 .
The idea is first to multiply the most significant bits of A by B to obtain themost significant bits of the product. Then, when the production of less significant
bits results in little or no change to the highest bits, multiples of C are subtracted.
In fact, since only addition is allowed, rather than subtracting C, the algorithm
must add a multiple of K = 2N −C. This is chosen to ensure that the overflows
match the multiple added. For example, adding KQ1 = 2Q+1 ×(2N −C) is done
when an overflow of exactly 2N +Q+1 is guaranteed, in order that the result is
equivalent to subtracting 2Q+1 ×C. These overflows, (which arise from either ofthe calls to Add or Shift in the algorithm below), are predicted by Lemma 9.
The specification given at the head of the procedure will show that it is notprecisely a modular multiplication algorithm: the residue may differ from the8International J. of Computer Mathematics, vol. 33, 1990, pp. 153-169

least non-negative one by the addition of C, so that the integer quotient is 1 lessthan it should be. Brickell makes no comment that the residue may not be in
the expected range. Examples which illustrate this are easy to find.
Finally note that our proof includes very naturally the limit case of C =2N −1 . That it works for such values of C is not as accidental as Brickell’s treatment suggests.
2.1

Code for the Algorithm

We introduce first one more function and a few definitions before giving thecode of the algorithm. Multiplication by a power of 2 whether to a positive or
negative exponent is achieved by a (hardwired) shift up or down. For this we
use a function
Shif t(D : DelayCarryInteger; E : Integer) : DelayCarryInteger
to shift D by E places. Possible overflow is important, but not underflow inthis context. Shifting in either direction will not change the invariant property
for delay carry integers D since it is accompanied within the function by finallysetting D[2, 0] = 0. Thus a possibly significant bit may be lost.
The code is documented with pre- and post- conditions, and a three partloop invariant. The proof and correct action of the algorithm depend upon theprevious properties established for a particular implementation of Add and on Q
being taken large enough: Q ≥ 5 is proved here and included as a pre-condition.
Incorrect action can be demonstrated for Q ≤ 4.
procedure M(A,B : DelayCarryInteger ; C : BinaryInteger ;var D,T : DelayCarryInteger ) ;{ Write Only:

{ Pre-Conditions :{ Post-Conditions:
var

D, T

}
N

N

A[1]<2 , A[2]<2 ,B[1]<2N , B[2]<2N ,2N−1 ≤C<2N ,Q ≥ 5.

}

A*B = C*T + D and 0 ≤ D < 7C/4 }K, KQ, KQ1, K∗ : BinaryInteger ;B∗: DelayCarryInteger ;J: BitIndex ;Overflows: Integer ;begin { M }K:= 2N - C ;KQ := Shift(K,Q) ;KQ1 := Shift(K,Q+1) ;D:= 0 ;
T:= 0 ;

C. D. Walter & S. E. Eldridge

9for J := N+Q downto 1 do
begin
{1: Top4Bits(D) + Top4Bits(KQ1) ≤ 19}
{2: Shift(A,Q-J)*2*B = Shift(T,-J)*2Q+1 *C + D}
{3: If J ≤ Q then 2Q+1−J divides D[1] and2Q+4−J divides D[2]}if J-Q > 0 thenB∗ := A[1,J-Q-1]*B + A[2,J-Q])*Shift(B,1)
elseB∗ := 0 ;T[2,J] := (Top4Bits(D)+Top4Bits(KQ1) >= 16) ;T[1,J-1]:= (not T[2,J]) and(Top4Bits(D)+Top4Bits(KQ) >= 8) ;K∗:= T[1,J-1]*KQ + T[2,J]*KQ1 ;Add(D,B∗ ,K∗ ,D,Overflows) ;D := Shift(D,1)
end ;D := Shift(D,-Q-1)
end ; { M }2.2

Remarks on the Hardware

As the data invariant clearly holds for A and T , the calculations of B ∗ andK ∗ involve a choice rather than an addition, and so only one clock cycle isneeded for each iteration of the loop. If we neglect the time spent to initialise
the parameters, during which the first five assignments can also be made, or toemit the result, during which the last shift can be done, the algorithm performs
the work in just N +Q cycles. The least time is achieved with the minimal valueof Q = 5, as opposed to Brickell’s unexplained choice of Q = 10.
The topmost nonzero bit of B ∗ will have index at most N and its top Q
bits are therefore all 0. Feeding this property into the hardware allows the top
parts of the second and fourth half adders to be removed, as in Figure 2, because
they no longer perform a non-trivial function. The naming of the output bits inBrickell’s Figure 3 suggests that the top part of the fifth half adder might also
be removed to leave only two half adders. That this is not the case in general isclear from trying to patch together the top section with the middle one. This is
the possible source of error in the hardware referred to in the abstract. The lower
end of the adder can also be simplified in an obvious way using the information
given in Lemma 4 and the data invariant restriction on the [2, 0] bit.

10International J. of Computer Mathematics, vol. 33, 1990, pp. 153-169
K ∗ [N +5]

K ∗ [N +4]

D[1, N +5]
D[2, N +5]
∧ ⊕
R1
∨

∧ ⊕

∨
Bits1

R1

∨
Bits1

K ∗ [N +2]

D[1, N +3]

D[2, N +4]

D[2, N +3]

∧ ⊕
R1

∨
Bits1

K ∗ [N +1]

D[1, N +2]

∧ ⊕
R1

Bits1

∧ ⊕

∧ ⊕

∧ ⊕

R3

R3

R3

∧ ⊕

∧ ⊕

∨

B [1, N ]

∧ ⊕

R3

∧ ⊕

∨

∧ ⊕

Bits1
∧ ⊕

∨

B ∗ [2, N ]

∗

R1

R1

D[2, N ]D[1, N ]D[2, N +1]

∧ ⊕

∨

∧ ⊕

K ∗ [N ]D[1, N +1]

D[2, N +2]

R3∧ ⊕Overflows

K ∗ [N +3]

D[1, N +4]

R2∨

Bits1∨

∧ ⊕
R3

Bits2

∧ ⊕

∨

Bits3 R4
Bits3 R4
Bits3
∧ ⊕
∧ ⊕
∧ ⊕

Sum[2, N +5] Sum[2, N +4] Sum[2, N +3] Sum[2, N +2]
Sum[1, N +5] Sum[1, N +4] Sum[1, N +3] Sum[1, N +2]

Sum[2, N +1]

Sum[1, N +1]

Sum[2, N ]Sum[1, N ]Fig. 2. Special delayed carry adder: Upper end for Q = 5.

2.3

The First Loop Invariant

The crux of our proof of the algorithm is the verification of the loop invariants.
A little preparation is necessary; to study the flow of bits up the adder it isconvenient to start with a definition, illustrated in Figure 1.
Definition. Using the notation of the code for Add,i) let Or[I] denote Bits1 [I]+Bits2 [I]+Bits3 [I] ;ii) let In[I] denote 2×D[2, I+1] + D[1, I] + 2×B ∗ [2, I+1] + B ∗ [1, I] +K ∗ [I];iii) let Out[I] denote 2×Sum[2, I+1] + Sum[1, I].
These quantities relate to the input and output from the single cascade of fivecomponents of the half adders representing 2I , taking into account the naturalpairing of bits under the data invariant. The bits are weighted to give 1 for an
index I, and 2 for an index I+1. Equating input and output bits clearly yields
the first two of the following lemmas:
Lemma 10 With the above notation,
In[I]+Or[I] = 2×Or[I+1] + Out[I]Lemma 11 Execution of the code of Add makes its parameters satisfy
T op4Bits(D) + T op4Bits(B ∗ ) + T op4Bits(K ∗ ) + Or[N +Q−3]=

T op4Bits(Sum) + Overf lows×24

C. D. Walter & S. E. Eldridge

11

Lemma 12 The call of Add in M satisfiesi) If Q ≥ 4 then 2Or[N +Q−3] + Out[N +Q−4] ≤ 6 + K ∗ [N +Q−4];ii) If Q ≥ 5 then 2Or[N +Q−3] + Out[N +Q−4] ≤ 5 + K ∗ [N +Q−4];iii) If Q ≥ 5 and K ∗ = 0 then 2Or[N +Q−3] + Out[N +Q−4] ≤ 4;iv) If Q ≥ 6 then 2Or[N +Q−3] + Out[N +Q−4] ≤ 4 + K ∗ [N +Q−4];v) If Q ≥ 7 and K ∗ = 0 then 2Or[N +Q−3] + Out[N +Q−4] ≤ 3.
Lemma 10 allows the properties claimed in Lemma 12 to be translated into
upper bounds on In[N +Q−4]+Or[N +Q−4]. In the first case, from the definitionof In, B ∗ [2, N +Q−3] = 0 gives In[N +Q−4] ≤ 3 + K ∗ [N +Q−4], and Or[I] ≤ 3completes the proof. In subsequent cases, B ∗ [2, N +Q−3] = B ∗ [1, N +Q−4] = 0
gives In[N +Q−4] ≤ 2+K ∗ [N +Q−4], and the proofs are completed by bounding
Or[N +Q−4]. In the second case, as for (i), Or[I] ≤ 3 suffices. In the third caseit remains to obtain Or[N +Q−4] ≤ 2. This last is apparent from the hypothesis
K ∗ = 0, B ∗ [2, N +Q−4] = 0 and
Bits1 [N +Q−4] + Bits2 [N +Q−4]= D[2, N +Q−4] + R1 [2, N +Q−4] + B ∗ [2, N +Q−4] + R2 [2, N +Q−4]= D[2, N +Q−4] + K ∗ [N +Q−5]×D[1, N +Q−5]+(K ∗ [N +Q−5] 6= D[1, N +Q−5])×B ∗ [1, N +Q−5]= D[2, N +Q−4] + D[1, N +Q−5]×B ∗ [1, N +Q−5]≤ D[2, N +Q−4] + D[1, N +Q−5]≤1
The last two cases are concluded by showing Or[N +Q−4] ≤ 2 and Or[N +Q−4] ≤1 respectively. They are left as exercises for the reader and involve showing
Bits2 [N +Q−4] = 0 for both cases and that Bits3 [N +Q−4] and Bits1 [N +Q−4]
are not both 1 in the last case. The next lemma is also an exercise.
Lemma 13 If I < N +Q then T op4Bits(KQ1) ≤ 8 − K ∗ [I].
In the first loop invariant the aim is to bound the value which the partial
product D may have: it should satisfy
1 : T op4Bits(D) + T op4Bits(KQ1) ≤ 19 .
This is clearly the case when the loop is entered because D = 0, and the restriction C ≥ 2N −1 forces T op4Bits(KQ1) ≤ 8. An inductive argument is used todeduce that (1) holds at the start of a general iteration. We make essential useof the consequence T op4Bits(B ∗ ) = 0 of choosing Q ≥ 4. This leads to a simplification in Lemma 9 which forms the basis of the proof. Note that Gibson [2]achieves an essentially similar loop invariant by his normalisation process which
produces numbers for which the invariant cannot be false.
The induction step in the proof is divided into three cases according to thevalues of T [2, J] and T [1, J−1]. Initially, suppose that T [2, J] holds. This with
the induction hypothesis (1) provides
16 ≤ T op4Bits(D) + T op4Bits(KQ1) ≤ 19.

12International J. of Computer Mathematics, vol. 33, 1990, pp. 153-169

By Lemmas 9(a) and 11 with T op4Bits(B ∗ ) = 0, we have, after the call whichadds D, KQ1 and B ∗ , that T op4Bits(D) ≤ 19 + Or[N +Q−3] − 16d for d = 1
or 0 according as Add overflows or not respectively. Using
T op5Bits(Sum) = 2×T op4Bits(Sum) + Out[N +Q−4],
which is immediate from the definition of Out, we have
T op5Bits(D) ≤ 2×(19+Or[N +Q−3]−16d) + Out[N +Q−4].
By Lemma 9(a) Shift overflows if and only if d = 0. So, after the Shift call,
T op4Bits(D) ≤ 2×(19+Or[N +Q−3]−16d) + Out[N +Q−4] − 2×16(1−d)= 6 + 2×Or[N +Q−3] + Out[N +Q−4].
By Lemma 12(ii), T op4Bits(D) ≤ 6+5+K ∗ [N +Q−4] at the end of the iteration,and this with Lemma 13 yields
T op4Bits(D) + T op4Bits(KQ1) ≤ 11 + T op4Bits(KQ1) + K ∗ [N +Q−4]≤ 11 + 8= 19
for the start of the next iteration.
The second case is when T [2, J] is false, but T [1, J−1] holds. Now
8 ≤ T op4Bits(D) + T op4Bits(KQ) ≤ T op4Bits(D) + T op4Bits(KQ1) ≤ 15
before the Add call, which adds D, B ∗ , and K ∗ = KQ. Lemmas 9(b) and 11
make it possible to deduce that after the Add call D satisfies
T op4Bits(D) − T op4Bits(KQ) + T op4Bits(KQ1) ≤ 15 + Or[N +Q−3].
Just as in the previous case,T op5Bits(D) ≤ 2×(T op4Bits(KQ) − T op4Bits(KQ1)+15 + Or[N +Q−3]) + Out[N +Q−4],
and the use of Lemma 12(ii) produces
T op5Bits(D) ≤ 30+2×(T op3Bits(KQ1)−T op4Bits(KQ1))+5+K ∗ [N +Q−4].
After the Shift, which by Lemma 9(b) with our initial hypothesis must overflow
once,
T op4Bits(D)≤ 30 − 16 + 5 + 2×(T op3Bits(KQ1)−T op4Bits(KQ1)) + KQ1[N +Q−3]
Thus,
T op4Bits(D) + T op4Bits(KQ1)≤ 19 + 2×T op3Bits(KQ1) − T op4Bits(KQ1) + KQ1[N +Q−3]= 19
at the start of the next iteration.
If T [2, J] and T [1, J−1] are both false, then T op4Bits(D)+T op4Bits(KQ) ≤7 for the initial value of D and K ∗ = 0. Lemma 9(c) applies and states that neither of the calls to Add nor Shift will overflow. So, using Lemma 11 as before,

C. D. Walter & S. E. Eldridge

13

after the Add call
T op4Bits(D) + T op4Bits(KQ) ≤ 7 + Or[N +Q−3],
which gives
T op5Bits(D) ≤ 2×(7 − T op4Bits(KQ) + Or[N +Q−3]) + Out[N +Q−4].
Directly Lemma 12(iii) yields
T op5Bits(D) ≤ 14 − 2×T op4Bits(KQ) + 4.
After the Shift therefore
T op4Bits(D) ≤ 18 − 2×T op3Bits(KQ1).
Hence the next iteration starts with
T op4Bits(D) + T op4Bits(KQ1) ≤ 18 + T op4Bits(KQ1) − 2×T op3Bits(KQ1)= 18 + KQ1[N +Q−3]≤ 19,
as required.
So the first loop invariant holds by induction before and after each iterationof the loop.
2.4

The Second Loop Invariant

The second loop invariant in the code for procedure M relates the partial quotient T and intermediate residue D to the part of the product A×B computed
so far.
2 : Shif t(A, Q−J)×2×B = Shif t(T, −J)×2Q+1 ×C + D .
This holds when the loop is entered as the right side of the equality is zero, andshifting A down N bits removes every non-trivial bit so that the left side also iszero.
Now suppose the invariant holds at the beginning of iteration J. From thefirst loop invariant and Lemma 9(a), when T [2, J] = 1 either Add has an overflow of 2N +Q+1 or there are two overflows from the subsequent Shift. Similarly,
when T [1, J−1] = 1, the Shift has exactly one overflow. So, assuming bits of A
with negative indices are zero, at the end of that iteration,
Dout = 2×(Din +B ∗ +K ∗ ) − T [2, J]×2N +Q+2 − T [1, J−1]×2N +Q+1
= 2×(Shif t(A, Q−J)×2×B − Shif t(T, −J)×2Q+1 ×C+A[1, J−Q−1]×B + A[2, J−Q]×(2×B)+T [1, J−1]×KQ + T [2, J]×KQ1)−T [2, J]×2N +Q+2 − T [1, J−1]×2N +Q+1
= 2×(2×Shif t(A, Q−J) + A[1, J−Q−1] + 2×A[2, J−Q])×B−(2×Shif t(T, −J) + T [1, J−1] + 2×T [2, J]) × 2Q+1 × C= 2×Shif t(A, Q+1−J)×B − Shif t(T, 1−J) × 2Q+1 × C

14International J. of Computer Mathematics, vol. 33, 1990, pp. 153-169

This is clearly the loop invariant again, with J−1 in place of J. Hence decrementing J to start the next loop iteration will establish the loop invariant correctlyagain. Thus by induction, the loop invariant will always hold.
2.5

The Third Loop Invariant

The last of the three loop invariants, namely
3 : If J ≤ Q then 2Q+1−J divides D[1] and 2Q+4−J divides D[2],holds for J = Q by virtue of the case L = 0 of Lemma 4 and the Shift at the endof the previous iteration. In general, suppose it holds at the start of an iteration
with J ≤ Q. Clearly B ∗ = 0 and 2Q divides K ∗ . So all three [1]-component
inputs to Add are divisible by 2Q+1−J and both the [2]-component inputs aredivisible by 2Q+4−J . Now Lemma 4 forces the outputs D[1] and D[2] of Add also
to be divisible by 2Q+1−J and 2Q+4−J respectively. The Shift of the iteration
then adds 1 to the exponent of those powers of 2 dividing each component of D,
yielding the loop invariant for the start of the next iteration.
2.6

The Post-Condition

For Q ≥ 5 each of the three parts of the loop invariant has been establishedalso to hold at the end of the last iteration. Thus we may set J = 0 to obtain apost-condition for the loop. With appropriate simplifications, this becomes:
1: T op4Bits(D) + T op4Bits(KQ1) ≤ 19
2: A×B×2Q+1 = T ×2Q+1 ×C + D
3: 2Q+1 divides D[1] and 2Q+4 divides D[2].
Because of the third assertion, it is possible to divide D by 2Q+1 using Shift
without losing significant bits. Hence, after the final Shift down of D by Q+1
places, (2) yields
A×B = C×T + D
which is most of the claimed post-condition.
By using the obvious bounds on the least significant bits of D and KQ1, thefirst assertion yields (D−2N +Q−2 +2)+(KQ1−2N +Q−3 +1) ≤ 19×2N +Q−3 at theend of the loop, and therefore D−2N −3 + 2N −C−2N −4 < 19×2N −4 at the endof the algorithm, i.e. D < C+6×2N −4 . By making use of 2N −1 ≤ C one obtains
the required post-condition easily from 6×2N −4 ≤ 3C/4. Clearly, the stronger
post-condition D < C+6×2N −4 might be preferable in some circumstances.

3

Different Values of Q

Firstly, observe that with the example N = 8, Q = 4, C = 129, A[1]/A[2] =64/126, and B[1]/B[2] = 160/190, the wrong answer is obtained as Q is too
small.

C. D. Walter & S. E. Eldridge

15

To obtain bounds on the incorrect behaviour of the algorithm for small values of Q, note that if the algorithm fails for Q = Q0 then it also fails for all
Q < Q0 . To see this, suppose (N, Q0 , A, B, C) is a failing instance for finding
A×B mod C with Q = Q0 . Then (N +(Q0 −Q), Q, A×2Q0 −Q , B, C×2Q0 −Q ) is a
failing instance for Q ≤ Q0 because exactly the same bits are processed in bothcases during the loop of the modular multiplier, with the resulting residue D
being shifted fewer times to give 2Q0 −Q times what it was before. Furthermore,
if the algorithm fails for N = N0 then it also fails for all N ≥ N0 . Thus, if(N0 , Q, A, B, C) is a failing instance, then so is (N, Q, A, B×2N −N0 , C×2N −N0 )for the same reasons as before: the same bits are processed after an initial N −N0loop iterations in which D remains 0, but with an additional N −N0 zero bits at
the lower end of all the registers. Hence,
Theorem 14. If the algorithm is incorrect for the pair (N0 , Q0 ) of valuesof (N, Q) then it is incorrect for all pairs (N, Q) with N ≥ N0 andQ ≤ Q0 . It is incorrect for (N, Q) = (8, 4).
The benefits of larger values of Q are not substantial. Taking Q ≥ 7 eliminatescompletely the effect of the most significant bits of B ∗ on the overflows during
one iteration of the loop. Repeating the proof of Section 2 using Lemma 12 (iv,v)
for such Q provides:
Theorem 15 If Q ≥ 7 then the algorithm works as stated but with
18 in place of 19 in the first loop invariant, and D < 13C/8 in the
post-condition (or D < C+5×2N −4 ).
This slightly increases the likelihood of the residue being less than C and therefore makes it more likely to find D < C by checking just the top few bits
(instead of accumulating the carries). However, the advantage in those few cases
may not outweigh the extra loop cycles involved. Gibson [2], by choosing to “normalise” his partial answer D on each iteration achieves the slightly better result
D < 3C/2, but the cost seems to be a longer clock cycle time to incorporate thenormalisation.

4

Conclusions

Our results have already been summarised in the abstract at the start of thepaper. Several omissions which could lead to errors are indicated, illustrating
the care with which it is necessary to check such algorithms for the completenessand correctness of definitions, specifications, and implementations. In particular,
note that our definition of “T op4Bits” (see Section 1.4 before Lemma 12) is not
the one which Brickell may seem to choose. Indeed, care has to be taken overwhether “overflow” applies to a binary or delay carry representation. The conceptof the algorithm is simple enough but its proof is complicated by having so many
bits coming up from lower indices which tighten the inequalities that must be
established.

16International J. of Computer Mathematics, vol. 33, 1990, pp. 153-169

P. Riess and J. Shawe-Taylor [3] remark that all relevant input to Brickell’salgorithm had been tested and found to be correct. This pre-supposes certain
details and assumptions which we failed to find explicitly in the original paper[1], but have now supplied.
The work described here was implemented in hardware in early 1988 and has
now run without fault in systems for many months. Our completion of the detailsof Brickell’s work differs from that described by Gibson [2] in several ways. The
most important of these is that we preferred to keep the repetitive nature of theadding hardware so that there was greater flexibility to use it for inputs which
did not have N bits. This might enable results to be obtained not just from the
top end of the registers. The price of the natural addition is, however, a more
complicated proof of correctness, but the benefits are flexibility, simplicity, andprobably a shorter cycle time.

References
1. Brickell, Ernest F., A Fast Modular Multiplication Algorithm with Application to
Two Key Cryptography, Advances in Cryptology (Proceedings of CRYPTO 82)
edited by Chaum et al., Plenum, 1983, pp 51-60.
2. Gibson, J. K., A generalisation of Brickell’s algorithm for fast modular multiplication, BIT 28 (1988) pp 755-763.
3. Riess, P. and Shawe-Taylor, J., The RSA public key cryptosystem, Dept. of Stats.
& Comp. Sci. Notes, RHNBC, Egham Hill, Egham, Surrey, England, TW20 0EX.
4. Rivest, Ronald L., RSA Chips (Past / Present / Future), Advances in Cryptology,(Proceedings of EUROCRYPT 84), LNCS 209, Springer Verlag, 1985, pp 159-165.
5. Rivest, R.L., Shamir, A. and Adleman, L., A method of obtaining digital signaturesand public key cryptosystems, Comm. ACM, 21 (1978), pp.120-126.