Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Fast exponentation in cryptography

Publiceringsår: 1995
Språk: Engelska
Sidor: 146-157
Publikation/Tidskrift/Serie: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes/Lecture notes in computer science
Volym: 948
Dokumenttyp: Konferensbidrag
Förlag: Springer


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: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 3-540-60114-7

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen