|
The public key system play a important role in crypto- graphy.
Most public key system, such as RSA, ElGamal crypto- system,
are constructed based on modular exponentiation. We must
execute large number modular multiplication to complete modular
exponentitation. The design of a fast algorithm for modular
multiplication with a large modules is the key to developing
a high-speed cryptosystem. The left-shift modular
multiplication is used in cryptosystem widely. The
left-shift algorithm computes the production in n step for n-
bits modules N, where at each step one left shift, one
addition and some comparison are performed. However, the
magnitude additions and comparison slow down for large
operands. The key point to increasing computation speed is to
keep the number of required comparison and addition as
small as possible. The Chiou & Yang propose a algorithm
without magnitude comparisons to increasing the performance of
modular multiplication. We based on the Chiou & Yang
algorithm to propose a modify algorithm that can reduce
about 39% addition operation without magnitude comparisons.
|