The Equivalence Of Discrete Logarithms Between Elliptic Curve And Real Quadratic Function Field

The elliptic curve cryptography (ECC) is now the hot point in public key cryptography after RSA, it then can be applied in message security and digital signatures. The security of ECC depends on the difficulty of discrete logarithms problem for elliptic curves (ECDLP) over finite fields.On the other hand, Scheidler, Stein and Williams [ 6] proposed a key exchange protocol which makes use of the discrete logarithms problem for real quadratic function fields. This infrastructure of quadratic function fields also can be used to implement ElGamal type signature schemes.In fact, the discrete logarithms problem for elliptic curves over finite fields is equivalent to the discrete logarithms problem for real quadratic function fields. In [1], Andreas Stein explicitly gave the one-to-one correspondence between the group generated by a rational point of a elliptic curve (without the point itself) over finite fields in characteristic p (p is not 2,3) and the set of reduced principal ideals of the corresponding real quadratic function fields, then their discrete logarithms problems are equivalent. In [4], Robert J. Zuccherato showed the similar case over finite fields in characteristic 2. In this paper, we show such equivalence also exists when the characteristic of finite fields is 3. The method is continued fraction.