引用本文: | 林齐平,张方国.二元Edwards曲线的半分算法[J].国防科技大学学报,2012,34(2):21-24.[点击复制] |
LIN Qiping,ZHANG Fangguo.Halving on binary Edwards curves[J].Journal of National University of Defense Technology,2012,34(2):21-24[点击复制] |
|
|
|
本文已被:浏览 7233次 下载 5247次 |
二元Edwards曲线的半分算法 |
林齐平1, 张方国1,2 |
(1.中山大学 信息科学与技术学院,广东 广州 510006;2.中国科学院 软件研究所,北京 100190)
|
摘要: |
利用二元Edwards曲线加法公式的对称性得到可做半分的公式。在推导半分算法过程中曲线参数有两种情况:d1≠d2和d1=d2。当曲线参数d1≠d2时,利用和Weierstrass曲线的双有理等价关系、迹函数和半迹函数,得到了Edwards曲线的半分算法。而当曲线参数d1=d2时,给出了定理证明,虽然在这种情况下倍加公式更简单,但半分算法反而更复杂。进一步分析了半分算法的效率,指出虽然在二元Edwards曲线上可以进行半分运算,但目前半分算法的效率仍然比不上倍加方法。利用ω-坐标简化半分算法并应用在标量乘计算上。 |
关键词: 点半分 二元Edwards曲线 ω-坐标 |
DOI: |
投稿日期:2011-07-28 |
基金项目:国家自然科学基金资助项目(61070168,61003244) |
|
Halving on binary Edwards curves |
LIN Qiping1, ZHANG Fangguo1,2 |
(1.School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, China;2.Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)
|
Abstract: |
The formulas of binary Edwards curves which can be halved are transformed from the doubling ones by using the symmetry of the formulas. Two situations are to be handled in the derivation by the parameters of the curves. In the case of d1≠d2, it is naturally to get a halving algorithm by using the relation of birational equivalence from the Weierstrass curves, the trace functions and the half-trace functions. In the case of d1=d2, a theorem is given to prove it. It is not easy to get a halving algorithm, although the doubling formulas are simpler in this case. Then the efficiency of the halving algorithm is analyzed. The result shows that the efficiency of the halving algorithm cannot catch up with that of the doubling one. Using the ω-coordinate, the halving algorithm is simplified, and is further used to compute the scalar multiplication. |
Keywords: point halving binary Edwards curves ω-coordinate |
|
|