Fast exponentation in cryptography
Publikation/Tidskrift/Serie: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes/Lecture notes in computer science
We consider the problem of minimizing the number of multiplications in computing f(x)=x n , where n is an integer and x is an element of any ring. We present new methods which reduce the average number of multiplications comparing with well-known methods, such as the binary method and the q-ary method. We do not compare our approach with algorithms based on addition chains since our approach is intended for cryptosystems with large exponent n and the complexity of constructing the optimal addition chain for such n is too high. We consider the binary representation for the number n and simplify exponentiation by applying ideas close to ideas exploited in data compression. Asymptotical efficiency of the new algorithms is estimated and numerical results are given.
- Electrical Engineering, Electronic Engineering, Information Engineering
11th International Symposium, AAECC-11
- ISSN: 0302-9743
- ISSN: 1611-3349
- ISBN: 3-540-60114-7