Paper 2010/335

Analysis of Efficient Techniques for Fast Elliptic Curve Cryptography on x86-64 based Processors

Patrick Longa and Catherine Gebotys


In this work, we analyze and present experimental data evaluating the efficiency of several techniques for speeding up the computation of elliptic curve point multiplication on emerging x86-64 processor architectures. In particular, we study the efficient combination of such techniques as elimination of conditional branches and incomplete reduction to achieve fast field arithmetic over GF(p). Furthermore, we study the impact of (true) data dependencies on these processors and propose several generic techniques to reduce the number of pipeline stalls, memory reads/writes and function calls. We also extend these techniques to field arithmetic over GF(p^2), which is utilized as underlying field by the recently proposed Galbraith-Lin-Scott (GLS) method to achieve higher performance in the point multiplication. By efficiently combining all these methods with state-of-the-art elliptic curve algorithms we obtain high-speed implementations of point multiplication that are up to 31% faster than the best previous published results on similar platforms. This research is crucial for advancing high-speed cryptography on new emerging processor architectures.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Elliptic curve cryptosystempoint multiplicationfield arithmetic schedulingincomplete reductiondata dependencepipeline stallx86-64 instruction setsoftware implementation.
Contact author(s)
plonga @ uwaterloo ca
2010-06-13: received
Short URL
Creative Commons Attribution


      author = {Patrick Longa and Catherine Gebotys},
      title = {Analysis of Efficient Techniques for Fast Elliptic Curve Cryptography  on x86-64 based Processors},
      howpublished = {Cryptology ePrint Archive, Paper 2010/335},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.