A Small Modular Exponentiation Circuit
Original Publication Date: 1998-Jun-01
Included in the Prior Art Database: 2005-Apr-04
Disclosed is a small modular exponentiation circuit. The modular exponentiation (M**E mod N) is achieved by repeated number of modular multiplications (A*B mod N). As shown in Fig. 1, one modular multiplication is in turn executed by repeated addition of partial product (+/-A), followed by an adjustment operation (+/-N), shift operation (*2), and another adjustment. When a bit '1' is found in the multiplicator B by checking each bit in B sequentially from the MSB-side, addition and adjustment are executed. When the bit is '0', only adjustment is done. After that, *2 operation and adjustment are executed. To reduce the number of additions, binary redundant form is used for the multiplicator B. The consecutive '1' bits in B are transformed such that 1111=10000-1.