|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 20 van 61 gevonden artikelen
| Titel: |
Fast exponentiation by folding the signed-digit exponent in half |
| Auteur: |
Lou, Der-Chyuan Wu, Chia-Long Chen, Chin-Yin |
| Verschenen in: |
International journal of computer mathematics |
| Paginering: | Jaargang 80 (2003) nr. 10 pagina's 1251-1259 |
| Jaar: |
2003-10 |
| Inhoud: |
For modern cryptographic systems, the public key cryptosystem such as RSA requires modular exponentiation (ME mod N). The M, E and N are either as large as the 1024-bit integers or even larger, it is not a very good idea to directly compute ME mod N. Recently, there are many techniques have been invented to solve the time-consuming computations of such time-consuming modular exponentiation. Among these useful algorithms, the “binary (square-and-multiply) algorithm” reduces the amount of modulo multiplications. As the “signed-digit representation algorithm” has the property of the nonzero digit occurrence probability equals to 1/3, taking this advantage, this method can more effectively decrease the amount of modular multiplications. Moreover, by using the technique of recording the common parts in the folded substrings, the “folding-exponent algorithm” can improve the efficiency of the binary algorithm, thus can further decrease the computational complexity of modular exponentiation. In this paper, a new modular exponentiation algorithm is proposed which based on the binary algorithm, signed-digit representation, and the folding-exponent technique. By using the parallel processing technique, in our proposed method, the modular multiplications and modular squaring can be executed in parallel, and thus lower down the computational complexity to k + 3 multiplications. As modular squaring operation over GF(2n) is carried out by a simple cyclic right shift operation, the computational complexity of our proposed method can be further reduced to 29k/36 + 3 multiplications. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 20 van 61 gevonden artikelen
| << vorige | volgende >> |