Abstract | ||
---|---|---|
The well-know binary method is a generally acceptable method for modular exponentiation in public-key cryptosystems. In this paper, we propose a new binary exponentiation algorithm, which is based on common-multiplicand method, Montgomery modular reduction algorithm, signed-digit recoding technique, and binary exponentiation algorithm. The common-multiplicand technique is developed to solve the problem common-multiplicand multiplications, i.e., the same common part in two modular multiplications can be computed once rather twice. The "signed-digit recoding" has less occurrence probability of the nonzero digit than binary representation. Due to this advantage, we can efficiently lower down the amount of modular multiplications and we can therefore decrease the computational complexity of modular exponentiation. By using the proposed algorithm, the total number of multiplications can be reduced by about 66.7% as compared with the original Montgomery modular reduction algorithm. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1109/ISI.2008.4565086 | ISI 2008: 2008 IEEE INTERNATIONAL CONFERENCE ON INTELLIGENCE AND SECURITY INFORMATICS |
Keywords | Field | DocType |
public-key cryptosystem, signed-digit recoding, common-multiplicand multiplication, cryptography | Algorithm design,Computer science,Algorithm,Modular design,Exponentiation by squaring,Public-key cryptography,Exponentiation,Computational complexity theory,Binary number,Modular exponentiation | Conference |
Citations | PageRank | References |
4 | 0.47 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chia-Long Wu | 1 | 68 | 9.36 |
Der-Chyuan Lou | 2 | 468 | 37.88 |
Te-Jen Chang | 3 | 47 | 5.72 |