Browse Prior Art Database

A Small Modular Exponentiation Circuit

IP.com Disclosure Number: IPCOM000123142D
Original Publication Date: 1998-Jun-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 56K

Publishing Venue

IBM

Related People

Satoh, A: AUTHOR

Abstract

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.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 83% of the total text.

A Small Modular Exponentiation Circuit

   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.  To keep the
intermediate value X in the range -n <= X < n, -N operation is
executed if X becomes a positive number after addition (A) or *2
operation.  On the other hand, if X becomes negative,  operation is
done.  An adjustment after the addition can be skipped when the sign
of X is changed by the addition.  An adjustment after the *2
operation also can be skipped when the 3 MSBs of X are '000' or
'111'.  Fig. 2 shows the block diagram of the modular exponentiation
circuit.  M**E mod N can be calculated by repeating an alternating
multiplication (X*M) and squaring (X*X), depending on the bit pattern
of the exponent E.  Registers M and N are used for additio...