Advanced

Fast exponentation in cryptography

Bocharova, Irina LU and Kudryashov, Boris LU (1995) 11th International Symposium, AAECC-11 In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes/Lecture notes in computer science 948. p.146-157
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Applied Algebra, Algebraic Algorithms and Error-Correcting Codes/Lecture notes in computer science
volume
948
pages
146 - 157
publisher
Springer
conference name
11th International Symposium, AAECC-11
external identifiers
  • scopus:33747119046
ISSN
0302-9743
1611-3349
ISBN
3-540-60114-7
DOI
10.1007/3-540-60114-7_11
language
English
LU publication?
yes
id
f1e20f39-2348-492a-a70f-8169eeea3895 (old id 1474303)
date added to LUP
2009-09-18 11:56:22
date last changed
2017-06-11 03:48:22
@inproceedings{f1e20f39-2348-492a-a70f-8169eeea3895,
  abstract     = {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.},
  author       = {Bocharova, Irina and Kudryashov, Boris},
  booktitle    = {Applied Algebra, Algebraic Algorithms and Error-Correcting Codes/Lecture notes in computer science},
  isbn         = {3-540-60114-7},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {146--157},
  publisher    = {Springer},
  title        = {Fast exponentation in cryptography},
  url          = {http://dx.doi.org/10.1007/3-540-60114-7_11},
  volume       = {948},
  year         = {1995},
}