改良在有限體上的橢圓曲線群的乘法運算

An Improved Multiplication on Elliptic Curves over Finite Fields

許仁傑(Jen-Chieh Hsu)

指導教授 ： 張介玉 ； 孫宏民

國立清華大學/理學院/數學系/碩士(2014年)

摘要

在西元1999年時，Lo ́pez and Dahab 想出一種基於蒙哥馬利演算法的演算法，用來計算在特徵值為2上的橢圓曲線群的乘法運算。這套演算法不需預先計算所需的數值，並且在某些特定的條件下，運算速度會比傳統的橢圓曲線群的乘法還快。這篇論文則是將這個演算法推廣到在特徵值大於3的上的橢圓曲線群上。

關鍵字

橢圓曲線 ； 蒙哥馬利演算法

並列摘要

In 1999,L ́opez and Dahab suggest an algorithm for non-supersingular elliptic curves y2 + xy = x3 + ax2 + b over GF(2m), and is based on an idea of Montgomery.Their algorithm is easy to implement in both hard- ware and software, works for any elliptic curved over GF(2m), requires no precomputed multiples of a point and faster on average than the tra- dition addition method. This paper describe an algorithm for computing elliptic scalar multiplications on non-supersingular elliptic curves defined over GF(p), and is based on an idea of algorithm of L ́opez and Dahab.

並列關鍵字

elliptic curves ； montgomery method

參考文獻

[1] T. ElGamal. Apublic key crypto system and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory,1985

[2] U.M. Maurer. Towards the equivalence of breaking the Di