A Study Of Some Arithmetic Problems Of Elliptic Curves Over Finite Fields

It is more and more important to study Public-key cryptosystems such as RSA, ECC, Hyper-ECC for they are widely used in practice now. ECC and Hyper-ECC arose from the arithmetic theory of elliptic curves over finite fields, and the study of many arithmetic problems inside it is very important for public-key cryptosystems. This thesis studies two basic problems in this area.In the Hyper-ECC public-key cryptosystems, the core problems are to compute the order of the Jacobian of a hyperelliptic curve and find some hyperelliptic curves whose Jacobians have given order. So the first question coming into mind is: for a given number n, does there exist an elliptic curve or a hyperelliptic curve whose Jacobian has order n? The construction problem is based on it. It is well known that the order of the Jacobian of a hyperelliptic curve is nothing but the evaluation at 1 of the L polynomial, i.e., the numerator of the Zeta function of this curve. This is the motivation of us to study the Zeta functions of curves in Chapter 2. In this chapter, we glue three elliptic curves through the covering and ramification theory of elliptic curves. We show that given three elliptic curves satisfying certain conditions, their product is isogenous to the Jacobian of a curve of genus 3. By this method, we can compute the Zeta functions of some curves of genus 3 more rapidly. Following the computational results, we firstly find that there exists a maximal curve of genus 3 over F₄₉, i.e., a curve whose number of rational points attains the Hasse-Weil upper bound.Before setting up an RSA public-key cipher, we need to find some big primes. The common method is to randomly choose a big integer and then test its primality. Therefore, an efficient algorithm of primality testing is extremely important. Some algorithms of primality testing such as ECPP and Goldwasser-Kilian algorithm use the arithmetic properties of elliptic curves over finite fields. A special class of elliptic curves is supersingular elliptic curves, which has an arithmetic property that the group order of a supersingular elliptic curve defined over F_p is p+1. To test the primality of a given integer n, similar to Goldwasser-Kilian algorithm, we can define a supersingular elliptic curve over ring Z_n first, then test the arithmetic properties of this curve. Based on this idea, in Chapter 3, we introduce a new efficient probabilistic algorithm of pri-mality test. For integers n≡3 (mod 4) or n≡1 (mod 3), it can be performed in polynomial time O(log⁸ n). Assume GRH, the running time holds for other integers.