在橢圓曲線上的解log問題

The discrete logarithm problem on an elliptic curve

林桂暖(Lin Kuei-Nuan)

指導教授 ： 于靖

國立臺灣師範大學/理學院/數學系/碩士(1999年)

摘要

這一篇論文主要討論在橢圓曲線上解log問題，我把M-O-V, Semave, 和Voloch的論文作重新的整理。
橢圓曲線上解log問題如下：E是一個在有限體F上的橢圓曲線，給曲線上任兩點有理點P, Q. 我們想算出是否有整數m滿足Q=[m]P.
如果P的order是n,且F的特徵值是p,我們分兩個部分討論
(1)n跟p互質
(2)n跟p不互質
並且我們比較出每個方法的優缺點。

關鍵字

橢圓曲線 ； 解log問題

並列摘要

In this master thesis, we talk about the discrete logarithm on an elliptic curve, and this is a reorganization of M-O-V's, Semaev's, and Voloch's papers.
Let E be an elliptic curve over a finite field F and char(F)=p,
the discrete logarithm problem on an elliptic curve is to compute an integer m such that Q=[m]P, where P and Q are rational points on E. If P has order n, we consider two cases:
(1)gcd(n,p)=1
(2)gcd(n,p) is not 1
Finally, we can use the Chinese remainder theorem to compute m

並列關鍵字

elliptic curve ； discrete logarithm

參考文獻

[MOV] A.Menezes, T.Okamoto and S. Vanstone, Reducing elliptic curves logarithms to logarithms in a finite field, IEEE Trans. Info. Theory, 39(1993) 1639-1646.

[M] Alfred Menezes, Elliptic curve public key crytosystems, kluwer Academic Puublishers, 1993.

[Se] I.A. Semave, Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p, Math. Comp.,67(1998),353-356.

[V1] J.F. Voloch, The discrete logarithm problem on elliptic curves and descents, to appear. Available at http://www.ma.utexas.edu/users/voloch

[V3] J.F. Voloch, An analogue of the Weierstrass z-function in characteristic p, Acta Arithmetica. LXXIX(1997)1-6.