Fast exponentation in cryptography
(1995) 11th International Symposium, AAECC-11 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:
https://lup.lub.lu.se/record/1474303
- author
- Bocharova, Irina LU and Kudryashov, Boris LU
- organization
- publishing date
- 1995
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 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
- conference location
- Paris, France
- conference dates
- 1995-07-17 - 1995-07-22
- 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
- 2016-04-01 12:20:25
- date last changed
- 2024-01-08 17:04:03
@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}},
doi = {{10.1007/3-540-60114-7_11}},
volume = {{948}},
year = {{1995}},
}