Halving on Binary Edwards Curves.
Lin Qi-ping, Fangguo Zhang · 2010
Abstract. Edwards curves have attracted great interest for their e-cient addition and doubling formulas. Furthermore, the addition formulas are strongly unied or even complete, i.e., work without change for all inputs. In this paper, we propose the rst 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 d1 6 = d2. 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 d1 = d2, and we brie y 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!-coordinate using Montgomery ladder.