The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Fast exponentation in cryptography

På svenska

Author

  • Irina Bocharova
  • Boris Kudryashov

Summary, in English

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.

Publishing year

1995

Language

English

Pages

146-157

Publication/Series

Applied Algebra, Algebraic Algorithms and Error-Correcting Codes/Lecture notes in computer science

Volume

948

Document type

Conference paper

Publisher

Springer

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering

Conference name

11th International Symposium, AAECC-11

Conference date

1995-07-17 - 1995-07-22

Conference place

Paris, France

Status

Published

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 3-540-60114-7