The Compulation Of Characteristic Polynomials Of A Class Of Elliptic Curves

Elliptic curve cryptography (ECC) is a natural generalization of the public-key cryp-tosystem based on the discrete logarithm problem (ECDLP). Currently, the efective at-tack algorithm of other public-key cryptosystem is pressure index time, and ECDLP isfully exponential time. This means, under the same security conditions, the key lengthof ECC is shorter than the other cryptosystem. ECC can use less overhead (required forcalculating the amount of storage capacity, broadband, software and hardware to achievescale) and time delay (high speed encryption and signature) to implement the high securi-ty. Therefore, ECC is particularly suitable for broadband limited space, integrated circuitand computer power limited applications such as smart cards, wireless communication,and some computer network.The calculation of the characteristic polynomials of elliptic curves is very importantto speed up the divisor scalar multiplication on Jacobian group and improve the speed ofECC implementation. Meanwhile, it also has a practical significance for proved safe andpairing-based encryption, signature and key agreement scheme.We generally study the characteristics of elliptic curves from the isomorphic curvebecause the isomorphic curves have the same characteristic polynomials and group struc-tures. This paper studies a class of Jacobia quartic curves E40: y2=x+ax2+b andthe supersingular elliptic curve over prime fields, where a, b∈F. Then we calculate theircharacteristic polynomials over finite fields. The work and results mainly include thefollowing aspects.(1) In Chapter1, we first introduce the research status and the critical problems onECC. Then the existing methods to compute the characteristic polynomials of ellipticcurves over finite field are summarized. These methods include: computing the orderalgorithms, improving the classical algorithms, studying the distribution of rational pointsby the index and Selberg formula, computing isomorphic classes of the elliptic curves andcharacteristic polynomials of a special class of curves.(2) In Chapter3, we introduce various types of classical algorithms and their’simproved algorithm. These algorithms include: Schoof algorithm and its kangaroo ac-celerated algorithm, big step gaint step (BSGS) algorithm, SEA algorithm and BSGS improvement strategies. Compared with the original method, the improved algorithmscan increase about30%and6%.(3) In Chapter4, we discuss a class of Jacobia quartic curve E0: y2=x4+ax2+bover finite fields. According to the nature of the characteristics, we compute the numberof rational points and characteristic polynomials of E0in three conditions.(4)In Chapter5, we discusses the characteristic polynomials of the supersingularWeistrass curves E231: y+a1xy+a3y=x+a2x2+a4x+a6over prime fields, where m isany positive integer and ai∈Fq, q=pm. We first introduce the isomorphism class of thesupersingular elliptic curves, and then respectively discuss the characteristic polynomialsof each class.