Fast exponentation in cryptography
(1995) 11th International Symposium, AAECC11 In Applied Algebra, Algebraic Algorithms and ErrorCorrecting Codes/Lecture notes in computer science 948. p.146157 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 wellknown methods, such as the binary method and the qary 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 wellknown methods, such as the binary method and the qary 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:
http://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
 in
 Applied Algebra, Algebraic Algorithms and ErrorCorrecting Codes/Lecture notes in computer science
 volume
 948
 pages
 146  157
 publisher
 Springer
 conference name
 11th International Symposium, AAECC11
 conference location
 Paris, France
 conference dates
 19950717  19950722
 external identifiers

 scopus:33747119046
 ISSN
 16113349
 03029743
 ISBN
 3540601147
 DOI
 10.1007/3540601147_11
 language
 English
 LU publication?
 yes
 id
 f1e20f392348492aa70f8169eeea3895 (old id 1474303)
 date added to LUP
 20090918 11:56:22
 date last changed
 20180529 11:53:06
@inproceedings{f1e20f392348492aa70f8169eeea3895, 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 wellknown methods, such as the binary method and the qary 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 ErrorCorrecting Codes/Lecture notes in computer science}, isbn = {3540601147}, issn = {16113349}, language = {eng}, location = {Paris, France}, pages = {146157}, publisher = {Springer}, title = {Fast exponentation in cryptography}, url = {http://dx.doi.org/10.1007/3540601147_11}, volume = {948}, year = {1995}, }