Paper 2006/115

Fast exponentiation via prime finite field isomorphism

Alexander Rostovtsev

Abstract

Raising of the fixed element of prime order group to arbitrary degree is the main operation specified by digital signature algorithms DSA, ECDSA. Fast exponentiation algorithms are proposed. Algorithms use number system with algebraic integer base (-2)^(1/4), 2^(1/4). Prime group order r can be factored as r = pi*pi1 in Euclidean ring Z[Sqrt[-2]], Z[Sqrt[2]] by Pollard and Schnorr algorithm. Farther factorization of prime quadratic divisor as pi = rho*rho1 in the ring Z[(-2)^(1/4)], Z[2^(1/4)] can be done similarly. Finite field of r elements is represented as quotient ring Z[(-2)^(1/4)]/(rho), Z[2^(1/4)]/(rho). Integer exponent k is reduced in corresponding quotient ring by minimization of its absolute norm. Algorithms can be used for fast exponentiation in arbitrary cyclic group if its order can be factored in corresponding number rings. If window size is 4 bits, this approach allows speeding-up 2.5 times elliptic curve digital signature verification comparatively to known methods with the same window size.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. the paper was not published elsewhere
Keywords
fast exponentiationcyclic groupalgebraic integersdigital signatureelliptic curve
Contact author(s)
rostovtsev @ ssl stu neva ru
History
2006-03-26: received
Short URL
https://ia.cr/2006/115
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/115,
      author = {Alexander Rostovtsev},
      title = {Fast exponentiation via prime finite field isomorphism},
      howpublished = {Cryptology ePrint Archive, Paper 2006/115},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/115}},
      url = {https://eprint.iacr.org/2006/115}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.