Hyperelliptic curves, Cartier - Manin matrices and Legendre polynomials.pdf Let Fq be a finite field, q = pn, p > 2. A hyperelliptic curve of genus g over Fq is a q nonsingular curve, given by equation C : У2 = f (x), where f ф Fq[x], f - monic, deg f = 2g + 1 or deg f = 2g + 2. Hyperelliptic curves were first proposed for use in cryptography by Koblitz [1]. Every hyperelliptic curve has an associated group - its Jacobian JC (Fq), where all computations take place. For applications in cryptography it is required to compute the order of JC(Fq), which is equivalent to computing of the characteristic polynomial of the Frobenius endomorphism x(A) of the JC. (deg f)(p-l)/2 Let f (x)(p-l)/2 = cixi. Then the Cartier - Manin matrix of the hyperelliptic i=0 curve C is a matrix W = (wi,j) = (cip-j) of the size g x g. Manin [2] showed that the characteristic polynomial of the matrix W is connected with the polynomial x(A) in the following way. Let Wp = W • W(p) • ... • W(pn ), where W(pfc) = (wpj), then , x(A) ф (-1)gAg|Wp - A/g| (mod p). If the polynomial x(A) mod p is known, we can use Hasse - Weil bound in combination with other methods to recover the polynomial x(A). The Cartier - Manin matrices in general can be computed by optimized algorithms from [3, 4]. In our work we show that for specific curves we only need to compute a half of elements to find all matrix. Moreover, in the case of gcd(p, g) = 1 we can find all the possible variants of the polynomial x(A) mod p in explicit form in terms of Legendre polynomials. In this work we study hyperelliptic curves of the form Ci : y2 = x2g+l + axg+l + bx and C2 : y2 = x2g+2 + axg+l + b. These curves are isomorphic to curves Ci,p : y2 = x2g+l - 2pxg+l + x and C2,p : y2 = x2g+2 - 2pxg+l + 1 over the field K = Fq[л/b]. Therefore, we can restrict discussion to the case of Cl,p, C2,p and our results for polynomials x(A) holds over Fq if b is square and over Fq2 if b is not square in Fq. These forms of curves are generalizations of Jacobi quartics [5]. The curves Cl, C2 were first studied by Miller and Lubin [6], who proved that the Cartier - Manin matrices of these curves are generalized permutation (monomial) matrices. For g =1 these curves are elliptic curves. It is known that number of points of elliptic curves is congruent to Legendre polynomials [5, 7]. In this work we generalize this to the g > 1 case. We prove first that coefficients of the Cartier - Manin matrix of C1,p are either zeroes or Legendre polynomials. Theorem 1. Let W = (wjj) be a Cartier - Manin matrix of the curve C1,p. Then 1) wjj = 0, if ip - j ф (p - 1)/2 (mod g); 2) Wjj ф P(ip-j)/g-(p-1)/(2g)(p) (mod p), otherwise. Then using properties of Legendre polynomials [8] we get result. Theorem 2. The Cartier - Manin matrix of the curve C1,p is centrosymmetric in Fq. Therefore, it's sufficient to compute a half of coefficients for computation of this matrix. The Cartier - Manin matrix W of any hyperelliptic curve is defined upto transformation of the form S(p)WS-1, where S is non-singular [9]. Since centrosymmetic matrices are orthogonally similar to block-diagonal matrices, we can prove theorem. Theorem 3. The Cartier - Manin matrix W of C1,p is equivalent to a block-diagonal matrix via transformation of the form S(p)WS-1. Analogous results can be proved for the curve C2,p. Theorem 4. Let W = (wjj) be a Cartier - Manin matrix of C2,p. Then 1) Wjj = 0, if ip ф j (mod g + 1); 2) wi,j ф P(ip-j)/(g+1)(p) (mod g +1); 3) W is a centrosymmetric matrix in Fq; 4) W is equivalent to block-diagonal matrix via transformation of the form S(p)WS-1. In the case of gcd(p, g) = 1 the Cartier - Manin matrix of the curve C1,p is monomial and we get an explicit formula for x(A) mod p. Theorem 5. Let the curve C1,p is defined over the finite field Fq, q = pn, gcd(p, g) = 1 and W be a Cartier - Manin matrix of C1,p. Then W is a monomial matrix with a permutation a, such that a(i) ф ip - (p - 1)/2 (mod g) and Wp is a monomial matrix with permutation an, an(i) ф ipn - (pn - 1)/2 (mod g). If Wp = (wij) and an = a1a2 ... am is a decomposition of an into disjoint cycles, then m ( |oj| \ X(A) ф Ag П ( 1 - Д (mod p), where aj,fc = jfc for aj = (j'1,... , jjCTj.|). Coefficients wi,j of Wp can be computed by using formula: ( n-1 n-2 k \ WP = «j) = (^Wan-1(i),j Д 2, and the curve C1 over fields Fp and Fp2.

Скачать электронную версию публикации