Patent ID: 7197528

Claim:
A Jacobian group element adder, which is an arithmetic unit for executing addition in a Jacobian group of an algebraic curve defined by a polynomial defined over a finite field that is Y 3 +α 0 X 4 +α 1 XY 2 +α 2 X 2 Y+α 3 X 3 +α 4 Y 2 +α 5 XY+α 6 X 2 +α 7 Y+α 8 X+α 9 or Y 2 +α 0 X 5 +α 1 X 2 Y+α 2 X 4 +α 3 XY+α 4 X 3 +α 5 Y+α 6 X 2 +α 7 X+α 8 or Y 2 +α 0 X 7 +α 1 X 3 Y+α 2 X 6 +α 3 X 2 Y+α 4 X 5 +α 5 XY+α 6 X 4 +α 7 Y+α 8 X 3 +α 9 X 2 +α 10 X+α 11 , said Jacobian group element adder comprising: means for inputting an algebraic curve parameter file having an order of a field of definition, a monomial order, and a coefficient list described as a parameter representing said algebraic curve; means for inputting Groebner bases I 1 and I 2 of ideals of the coordinate ring of the algebraic curve designated by said algebraic curve parameter file, said Groebner bases representing elements of said Jacobian group; ideal reduction means for, in the coordinate ring of the algebraic curve designated by said algebraic curve parameter file, performing arithmetic of producing a Groebner basis J of the ideal which is a product of the ideal that the Groebner basis I 1 generates, and the ideal that the Groebner basis I 2 generates; first ideal reduction means for, in the coordinate ring of the algebraic curve designated by said algebraic curve parameter file, performing arithmetic of producing a Groebner basis J* of the ideal, which is smallest in the monomial order designated by said algebraic curve parameter file among the ideals equivalent to an inverse ideal of the ideal that the Groebner basis J generates; and second ideal reduction means for, in the coordinate ring of the algebraic curve designated by said algebraic curve parameter file, performing arithmetic of producing a Groebner basis J** of the ideal, which is smallest in the monomial order designated by said algebraic curve parameter file among the ideals equivalent to an inverse ideal of the ideal that the Groebner basis J* generates, to output it.