A verification of brickell's fast modular multiplication algorithm

Abstract

This paper refers to the algorithm and its hardware implementation described by Brickell [1] for modular multiplication in N+10 clock pulses where N is the number of bits in the binary integers involved. Brickell [1] 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, and one in the definition of the control variables T ₁ and T ₂. Our main contributions are the supply of further detail to remove such ambiguities, a determination 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 have already 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] described different additional detail to make Brickell's algorithm work. What is supplied in this article we believe to be more natural than Gibson's in that the standard delay-carry addition stands unaltered here, and the minimum number of clock pulses required remains clear.

Keywords:

• RSA algorithm
• fast multiplication
• verification
• cryptography
• computer arithmetic