Paper 2010/004

Halving on Binary Edwards Curves

Qiping Lin and Fangguo Zhang

Abstract

Edwards curves have attracted great interest for their efficient addition and doubling formulas. Furthermore, the addition formulas are strongly unified or even complete, i.e., work without change for all inputs. In this paper, we propose the first halving algorithm on binary Edwards curves, which can be used for scalar multiplication. We present a point halving algorithm on binary Edwards curves in case of $d_1\neq d_2$. The halving algorithm costs about $3I+5M+4S$, which is slower than the doubling one. We also give a theorem to prove that the binary Edwards curves have no minimal two-torsion in case of $d_1= d_2$, and we briefly explain how to achieve the point halving algorithm using an improved algorithm in this case. Finally, we apply our halving algorithm in scalar multiplication with $\omega$-coordinate using Montgomery ladder.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curve cryptosystem
Contact author(s)
isszhfg @ mail sysu edu cn
History
2010-05-06: revised
2010-01-07: received
See all versions
Short URL
https://ia.cr/2010/004
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/004,
      author = {Qiping Lin and Fangguo Zhang},
      title = {Halving on Binary Edwards Curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/004},
      year = {2010},
      url = {https://eprint.iacr.org/2010/004}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.