Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A High Speed Modular Exponentiation Circuit

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

Publishing Venue

IBM

Related People

Satoh, A: AUTHOR

Abstract

Disclosed is a high-speed modular exponentiation circuit. A modular exponentiation (M**E mod N) is accomplished by repeated execution of modular multiplications (A*B mod N). As shown in Fig. 1, the modular multiplication is in turn achieved by repeated partial product addition (+/-A) and adjustment operation (+/-N, +/-2N, +/-3 N, +/-4N) alternately. When the bit in the multiplicator B is '1', addition is executed, and when the bit is '0', adjustment is done. To make time for the adjustment, in another word, to avoid consecutive additions, binary redundant form is introduced into the multiplicator. Consecutive '1' bits in B are transformed such that 1111=10000-1. On the other hand, when sequential '0' bits are encountered, addition (+/-A) can be skipped.

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

A High Speed Modular Exponentiation Circuit

   Disclosed is a high-speed modular exponentiation circuit.  A
modular exponentiation (M**E mod N) is accomplished by repeated
execution of modular multiplications (A*B mod N).  As shown in Fig.
1, the modular multiplication is in turn achieved by repeated partial
product addition (+/-A) and adjustment operation (+/-N, +/-2N, +/-3
N, +/-4N) alternately.  When the bit in the multiplicator B is '1',
addition is executed, and when the bit is '0', adjustment is done.
To make time for the adjustment, in another word, to avoid
consecutive additions, binary redundant form is introduced into the
multiplicator.  Consecutive '1' bits in B are transformed such that
1111=10000-1.  On the other hand, when sequential '0' bits are
encountered, addition (+/-A) can be skipped.  The adjustment after
the addition can also be skipped when the absolute value of the
intermediate result X is smaller than N/2.  Furthermore, when A >=
N/2, A' (=A-N) is used for the multiplicand instead of A.  This
makes the absolute value of the multiplicand smaller than N/2, and
the adjustment operation is simplified.  To select the one value
from {+0, +/-N, +/-2N, +/-3N, +/-4N} in adjustment (where +0 means
skip), only 5 bits from the MSB-side including the sign bit are
necessary for comparison between X and {0.5N, 1.5N, 2.5N, 3.5N}.
Fig. 2 shows the block diagram of the modular exponentiation
circuit.  To calculate M**E mod N, initial value M is set in the...