# Patent

## Title
Jacobian group element adder

## Abstract

An objective is to obtain a Jacobian group element adder that can calculate addition in a Jacobian group of a Cab curve at a high speed, and can enhance practicality of the Cab curve.
An algebraic curve parameter file A 10, and Groebner bases I1 and I2 of ideals of a coordinate ring of an algebraic curve designated by this file A are input into an ideal composition section 11 to perform arithmetic of producing a Groebner basis J of an ideal product of the ideal generated by I1 and ideal generated by I2. In a first ideal reduction section 12, arithmetic is performed of producing a Groebner basis J* of an ideal that is smallest in a monomial order designated by the file A among ideals equivalent to an inverse ideal of an ideal that J in the coordinate ring of the algebraic curve designated by the file A generates. In a second ideal reduction section 13, arithmetic is performed of producing a Groebner basis J** of a ideal that is smallest in the monomial order designated by the file A among ideals equivalent to an inverse ideal of an ideal that this J* generates to output it.

## Background
BACKGROUND OF THE INVENTION
The present invention relates to a Jacobian group element adder, and more particularly technology for discrete logarithmic cryptography employing a Jacobian group of an algebraic curve (hereinafter, referred to as algebraic curve cryptography) that is a kind of the discrete logarithmic cryptography, which is cryptography technology as information security technology.
It is an elliptic curve cryptography that has come in practice most exceedingly among the algebraic curve cryptography. However, an elliptic curve for use in the elliptic curve cryptography is a very special one as compared with a general algebraic curve. There is the apprehension that an aggressive method of exploiting its specialty would be discovered in the near future. For this, so as to secure safety more reliably, a general algebraic curve of which specialty is lower is desirably employed. Cab curve cryptography is known as an algebraic curve cryptography capable of employing a more general algebraic curve as mentioned above.
The Cab curve cryptography, however, is less employed in the industrial field as compared with the elliptic curve cryptography. Its main reason is that the conventional additive algorithm in the Jacobian group of the conventional Cab curve is tens of times slower than additive algorithm in the Jacobian group of the elliptic curve, and as a result, process efficiency of encryption/decryption in the Cab curve cryptography is remarkably inferior as compared with the elliptic curve cryptography, which was shown in “Jacobian Group Additive algorithm of Cab Curve and its Application to Discrete Logarithmic Cryptography” by Seigo Arita, Japanese-version collection of The Institute of Electronics, Information and Communication Engineers, Vol. J82-A, No.8, pp.1291–1299, 1999.
Also, another additive algorithm in the Jacobian group of the Cab curve was proposed in “A Fast Jacobian Group Arithmetic Scheme for Algebraic Curve Cryptography” by Ryuichi Harasawa, and Joe Suzuki, Vol. E84-A No.1, pp.130–139, 2001 as well; however, even though an asymptotic calculation quantity of algorithm was given, no execution speed data in a packaging experiment was shown, and, also, no report on the packaging experiment by a third party was provided, and the extent to which the execution speed can practically be achieved is uncertain.
As seen from the foregoing, non-efficiency of the additive algorithm in the Jacobian group of the Cab curve prevents the cryptography of the above curve from coming in practice, which gives rise to the necessity of executing addition in the Jacobian group of the Cab curve at a high speed.
DISCLOSURE OF THE INVENTION
The present invention has been accomplished in consideration of such problems, and an objective thereof is to provide a Jacobian group element adder that enables the additive algorithm in the Jacobian group of the cab curve to be executed at a high speed.
The Jacobian group element adder in accordance with the present invention, 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

Y3+α0X4+α1XY2+α2X2Y+α3X3+α4Y2+α5XY+α6X2+α7Y+α8X+α9

or

Y2+α0X5+α1X2Y+α2X4+α3XY+α4X3+α5Y+α6X2+α7X+α8

or

Y2+α0X7+α1X3Y+α2X6+α3X2Y+α4X5+α5XY+α6X4+α7Y+α8X3+α9X2+α10X+α11,

is characterized in 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 I1 and I2 of ideals of the coordinate ring of the algebraic curve designated by said algebraic curve parameter file, which represent elements of said Jacobian group;
ideal composition means for, in the coordinate ring of the algebraic curve designated by said algebraic curve parameter file, performing arithmetic of a producing Groebner basis J of the ideal which is a product of the ideal that the Groebner basis I1 generates, and the ideal that the Groebner basis I2 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.
[Cab Curve and its Jacobian Group]
The Cab curve C to be treated in the present invention is a nonsingular plane curve to be defined by a polynomial F(X,Y) having the following formula for two natural numbers a and b that are relatively prime.

F(X,Y)=Ya+c0Xb+Σci,jXiYj

Here, indexes i and j in the above equation, which are natural numbers equal to or more than zero, vary in a range of ai+bj<ab. Also, suppose that c0 and ci,j are elements of a defining field k, and that c0 is not zero. The Cab curve C has a unique point at infinity P∞, and the polynomials Y and X have a unique b-order pole and a-order pole at P∞ respectively. Set a group subtended by divisors of degree 0 on the Cab curve C to Dc0(k), and set a group composed of principal divisors to Pc(k).
A Jacobian group Jc(k) of which the additive algorithm is required to be found in the present invention is defined as

Jc(k)=Dc0(k)/Pc(k)

On the other hand, let R=k[X,Y]/F be the coordinate ring of the Cab curve C, it follows that the ring R becomes an integrally-closed integral domain, which is a Dedekind domain, because the Cab curve C is nonsingular by definition. Thus, all of the fractional ideals of the ring R that is not zero compose a group IR(k). Set a subgroup by subtended by the principal ideal of the ring R to PR(k), then an ideals class group HR(k) of the ring R is defined as

HR(k)=IR(k)/PR(k)

As a rule, it is known that, for the nonsingular algebraic curve, the divisor on the curve can be identified with the ideal of the coordinate ring, and that its Jacobian group and the ideal class group are of intrinsic isomorphism. In particular, a Jacobian group JC(k) of the Cab curve C and the ideal class group HR(k) of the coordinate ring R are of intrinsic isomorphism. The ideal is more convenient than the divisor for packaging algorithm, whereby, hereinafter, the Jacobian group JC(k) of the Cab curve C is treated as the ideal class group HR(k) of the coordinate ring R.
[Preparation Relating to a Groebner Basis]
Since the Groebner basis of the ideal is employed in calculation of which an object is the ideal class group HR(k), a preparation relating hereto is made in this chapter. As a rule, for a polynomial ring S=k[X1, . . . , Xn], an order ‘<’ among its monomials, if it is compatible with a product, that is, M1<M2 always yields M1M3, is called a monomial order. In this chapter, from now on, suppose an arbitrary monomial order ‘<’ is given to a polynomial ring S.
For a polynomial f in S, call the largest monomial in the monomial order ‘<’ that appears in f a leading monomial of f, which is denoted by LM(f). Also, for an ideal I, LM(I) denotes an ideal that is generated by leading monomials of the polynomial belonging to I generates by LM(I).
For an ideal I=(f1, . . . , fs) of S that is generated by a polynomials f1, . . . , fs, when {f1, . . . , fs} meets IM(I)=(LM(f1), . . . , LM(fs)), {f1, . . . , fs} is called a Groebner basis of the ideal I. For the ideal I of the polynomial ring S, the entirety Δ(I) of the monomial (or its multi degree) Δ(I) that does not belong to LM(I) is called a delta set of I. When (multi degrees of) monomials in Δ(I) are plotted, a convex set appears, and a lattice point encircling its convex set corresponds to the leading monomial of an element of the Groebner basis of I. Also, Δ(I) subtends the basis of a vector space S/I over k.
The ideal I of an the coordinate ring R=S/F of a nonsingular affine algebraic curve C can be identified with the ideal of the polynomial ring S that includes a defining ideal F of the curve C. Thus, for the ideal of the coordinate ring R as well, as mentioned above, Groebner basis can be considered. For a zero-dimensional ideal I (that is, a set of zeros of I is a finite set) of the coordinate ring R=S/F, call a dimension of a vector space S/I over k an order of the ideal I, which is denoted by δ(I). Immediately from definition, it can be seen that δ(I) is equivalent to the order of the set Δ(I). Also, by assumption of being nonsingular, it follows that δ(IJ)=δ(I)δ(J). When I=(f) is a principal ideal of R, then δ(I)=−vP∞(f), where vP∞(f) represents a valuation of the polynomial f at P∞.
[Additive Algorithm on Jacobian Group of Cab Curve, Part 1]
Now think about the coordinate ring R=k[X,Y]/F of the Cab curve C defined by the polynomial F(X,Y). Regard the monomial of two variables XmYn as a function on the curve C, and call the monomial order obtained by ordering the monomials based on the size of a pole order-vP∞(XmYn) at P∞ a Cab order. Here, in the case that the pole orders at P∞ thereof are the same, the monomial with the larger is supposed to be larger. Hereinafter, the Cab order is employed as the monomial order of the coordinate ring R of the Cab curve C. For the ideal I of the coordinate ring R, let fI be the non-zero polynomial with the smallest leading monomial among the polynomials in I. Furthermore, let I*=(fI):I(={g∈R|g·I⊂(fI)}).
Now, it can be easily shown that, when I and J are arbitrary (integral) ideals of the coordinate ring R, then (1) I and I** are linearly equivalent, (2) I**, which is an (integral) ideal equivalent to I, has the smallest order among ideals equivalent to I, and (3) if I and J are equivalent, then I*=J*, in particular, J**=(I**)**. For an ideal I of the coordinate ring R, when I**=(I), we call I a reduced ideal. From the above-mentioned equations (1) and (3), an arbitrary ideal is equivalent to the unique reduced ideal. That is, the reduced ideals compose a representative system of the ideal classes. This property is not limited to the Cab order, and holds also in the event of having employed an arbitrary monomial order; however, in the event of having employed the Cab order, from the above-mentioned equation (2), the reduced ideal has the property of becoming an ideal of which the order is the smallest among the equivalent ideals. This is advantageous in packaging the algorithm. Using reduced ideal as a representative system of the ideal classes, we obtain additive algorithm on Jacobian of Cab curve, mentioned below.
[Additive Algorithm on Jacobian Group 1]
Inputs: reduced ideals I1 and I2 of the coordinate ring R
Output: a reduced ideal I3 equivalent to an ideal product I1·I2 

    1. J←I1·I2 
    2. J*←(fJ):J
    3. I3←(fJ*):J*

[Classification of Ideals]



So as to realize the above-mentioned additive algorithm on Jacobian group 1 as a program that is efficient, and yet is easy to package, the ideals that appear during execution of the additive algorithm 1 are classified. Hereinafter, for simplification, explanation is made with a C34 curve (that is, the Cab curve with a=3, and b=4) taken as an object; however, for the general Cab curve as well, the matter is similar. A genus of the C34 curve is 3, whereby the order of the ideal that appears during execution of the additive algorithm 1 is equal to or less than 6. The Groebner bases in their C34 orders are classified as follows order by order. However, from now on, even though a defining equation F of the C34 curve C appears in the Groebner basis of the ideal, F is omitted, and is not expressed. Also, coefficients ai, bj, and ck of each polynomial constructing the Groebner basis are all elements of k.
(Ideal of Order 6)
Suppose I is an ideal of order 6 of the coordinate ring R. By definition of the order, V=R/I is a six-dimensional vector space over the defining field k. When six points that the ideal I represents are at a “generalized” position, six monomials from the beginning in the C34 order 1, X, Y, X2, XY, and Y2 are linearly independent at these six points. That is, the monomials 1, X, Y, X2, XY, and Y2 compose a basis of the vector space V. At this time, we call such an ideal I an ideal of a type 61.
As a rule, a delta set Δ(I) of the ideal I can be identified with the basis of the vector space V, whereby the delta set of the ideal I of a type 61 becomes Δ(I)={(0,0),(1,0),(0,1),(2,0),(1,1),(0,2)} The lattice points encircling these are (0,3),(1,2),(2,1),(3,0)}. Thus, the Groebner basis of the ideal I of a type 61 takes the following form.
The Groebner basis of the ideal of a type 61={X3+a6Y2+a5XY+a4X2+a3Y+a2X+a1,X2Y+b6Y2+b5XY+b4X2+b3Y+b2X+b1, XY2+c6Y2+c5XY+c4X2+c3Y+c2X+c1}
These three polynomials correspond to the lattice points (3,0), (2,1), and (1,2) respectively (The lattice point (0,3) corresponds to the defining equation F). As a rule, six monomials 1, X, Y, X2, XY, and Y2 are not always linearly independent at the six points that the ideal I represents, i.e. in the vector space V.
So, next, we study the case in which five monomials from the beginning in the C34 order 1, X, Y, X2, and XY are linearly independent in V, and the sixth monomial Y2 is represented by a linear combination of them. By assumption, Δ(I) is a convex set of order 6 that includes {(0,0),(1,0),(0,1),(2,0),(1,1)}, and does not include (2,0). Thus, it becomes either of Δ(I)={(0,0),(1,0),(0,1),(2,0),(1,1),(2,1)}, or Δ(I)={(0,0),(1,0),(0,1),(2,0),(1,1),(3,0)}. When Δ(I) is the former, call I an ideal of a type 62, and in the event that it is the latter, call I an ideal of type 63.
The lattice point set encircling Δ(I) is {(0,2),(3,0)} when I is of type 62, and is (0,2),(2,1),(4,0)} when I is of type 63. Thus, the Groebner basis becomes the following. The Groebner basis of the ideal of a type 62={Y2+a5XY+a4X2+a3Y+a2X+a1,X3+b5XY+b4X2+b3Y+b2X+b1}
These two polynomials correspond to the lattice points (0,2), and (3,0) respectively.
The Groebner basis of the ideal of a type 63={Y2+a5XY+a4X2+a3Y+a2X+a1,X2Y+b6X3+b5XY+b4X2+b3Y+b2X+b1}
These two polynomials correspond to the lattice points (0,2), and (2,1) respectively.
Although the polynomial, which corresponds to the lattice point (4,0), originally exists in the Groebner basis of the ideal of a type 63; it was omitted since from the defining equation F, and an equation f=Y2+a5XY+a4X2+a3Y+a2X+a1 that corresponds to the lattice point (0,2), it can be immediately calculated as F−Yf.
Next, suppose four monomials from the beginning 1, X, Y, and X2 are linearly independent in V, and that the fifth monomial XY is represented by a linear combination thereof. That is, Δ(I) includes {(0,0),(1,0),(0,1),(2,0)}, and does not include (1,1).Here, assume Δ(I) does not includes (0,2), then there is no other choice but Δ(I)=(0,0),(1,0),(0,1),(2,0),(3,0),(4,0)} so that Δ(I) has order 6. As it is, by assumption, I includes a polynomial f=Y2+ . . . of which the leading term is Y2. As a result, (4,0) does not belong to Δ(I) because Yf−F=X4+ . . . belongs to I. That is contradictory. From the foregoing, it can be seen that Δ(I) is sure to include (0,2), then Δ(I)={(0,0),(1,0),(0,1),(2,0),(0,2),(3,0)}. At this time, call I an ideal of a type 64.
The lattice point set encircling the delta set Δ(I) of the ideal I of a type 64 is {(0,3),(1,1),(4,0)}. Thus the Groebner basis of the ideal I of a type 64 becomes the following.
The Groebner basis of the ideal of a type 64={XY+a4X2+a3Y+a2X+a1,X4+b6X3+b5Y2+b4X2+b3Y+b2X+b1}
These two equations correspond to the lattice points (1,1), and (4,0) respectively (The lattice point (0,3) corresponds to the defining equation F).
Next, suppose three monomials from the beginning 1, X, and Y in the C34 order are linearly independent in V=R/I, and that the fourth monomial X2 is represented by a linear combination thereof. At this time, since a polynomial f of which the leading term is X2 is included in the ideal I, the delta set becomes Δ(I)={(0,0),(1,0),(0,1),(1,1),(0,2),(1,2)} and the lattice point set encircling these becomes {(0,3),(2,0)}, whereby I becomes a monomial ideal to be generated in f. At this time, call I an ideal of a type 65.
The Groebner basis of the ideal of a type 65={X2+a3Y+a2X+a1}
The above equation corresponds to the lattice point (2,0) (The lattice point (0,3) corresponds to the defining equation F)
There is no possibility that, from deg((f)0)=−vp∞ (f)=4<6, the polynomial f of which the leading term is (a term equal to or lower than) Y disappears simultaneously at six points that correspond to the ideal I of order 6. Thus, three monomials 1, X, and Y from the beginning are always linearly independent in V=R/I, and above, the classification of the ideal of order 6 was completed.
(Ideal of Order 5)
Suppose I is an ideal of order 5 of coordinate ring R. The ideal of order 5 is also classified into a type 51 to a type 54 similarly to the ideal of order 6, as mentioned below.
The Groebner basis of the ideal of a type 51={Y2+a5XY+a4X2+a3Y+a2X+a1,X3+b5XY+b4X2+b3Y+b2X+b1, X2Y+c5XY+c4X2+c3Y+c2X+c1}
The Groebner basis of the ideal of a type 52={XY+a4X2+a3Y+a2X+a1,Y2+b4X2+b3Y+b2X+b1}
The Groebner basis of the ideal of a type 53={XY+a4X2+a3Y+a2X+a1,X3+b5Y2+b4X2+b3Y+b2X+b1}
The Groebner basis of the ideal of a type 54={X2+a3Y+a2X+a1,XY2+b5Y2+b4XY+b3Y+b2X+b1}
(Ideal of Order 4)
The ideal I of order 4 is also classified into a type 41 to a type 44 similarly, as mentioned below.
The Groebner basis of the ideal of a type 41={XY+a4X2+a3Y+a2X+a1,Y2+b4X2+b3Y+b2X+b1,X3+c4X2+c3Y+c2X+c1}
The Groebner basis of the ideal of a type 42={X2+a3Y+a2X+a1,XY+b3Y+b2X+b1}
The Groebner basis of the ideal of a type 43={X2+a3Y+a2X+a1,Y2+b4XY+b3Y+b2X+b1}
The Groebner basis of the ideal of a type 44={Y+a2X+a1}
(Ideal of Order 3)
The ideal I of order 3 is also classified into a type 31 to a type 33 similarly, as mentioned below.
The Groebner basis of the ideal of a type 31={X2+a3Y+a2X+a1,XY+b3Y+b2X+b1,Y2+c3Y+c2X+c1}
The Groebner basis of the ideal of a type 32={Y+a2X+a1,X3+b3X2+b2X+b1}
The Groebner basis of the ideal of a type 33={X+a1}
(Ideal of Order 2)
The ideal I of order 2 is also classified into a type 21 and a type 22 similarly, as mentioned below.
The Groebner basis of the ideal of a type 21={Y+a2X+a1,X2+b2X+b1}
The Groebner basis of the ideal of a type 22={X+a1,Y2+b2Y+b1}
(Ideal of Order 1)
Needless to say, the ideal of order 1 is only of type 11, as mentioned below.
The Groebner basis of the ideal of a type 11={X+a1,Y+b1}
[Remark]
Ideals of a type 65, 44, and 33 among the ideals mentioned above, which are a principal ideal, represent a unit element as a Jacobian group element. Also, the reduced ideal types among the ideal types mentioned above are only 31, 21, 22, and 11. For example, the reason why the ideal of a type 32 is not a reduced one is understood in a manner mentioned below.
Suppose I is an ideal of a type 32, then fI=Y+a2X+a1, thus δ(I*)=−v∞(fI)−δ(I)=4−3=1, thus, fI*=X+a′, and δ(I**)=−v∞(fI*)−δ(I*)=3−1=2 because I* is of type 11. The order thereof is different, whereby I≠I**.
[Additive Algorithm on Jacobian Group of the C34 Curve, Part 2]
Set the coordinate ring of the C34 curve C defined over a field k having the defining equation F to R=k[X,Y]/F. Now let the additive algorithm 1 take concrete shape more clearly for estimating its execution speed. However, hereinafter, the order of the field k is supposed to be sufficiently large in consideration of an application to the discrete logarithmic cryptography.
(Composition Operation 1)
At first, study a first step of the additive algorithm 1 for different ideals I1 and I2, which is hereinafter referred to as a composition operation 1. That is, fJ is to be found for an ideal product J=I1·I2. To this end, the Groebner basis of the ideal product J should be found (since fJ is its first element). The genus of the C34 curve is 3, whereby the order of the ideal I1 or I2 is equal to or less than 3. Thus, its type is anyone of 11, 21, 22, 31, and 32. The case is mentioned here in which both of the ideals I1 and I2 are of type 31; however the other case is also similar.
We can Suppose I1 and I2 are selected at random from the Jacobian group, Then we have at almost every case,

V(I1)∩V(I2)=φ  (1)

Because the order of the field k is supposed to be sufficiently large. Here for the ideal I, a set of zero of I is denoted by V(I) (φ represents an empty set). Also in the event that the condition (1) is not met, upon generating element R1 and R2 that yields R1+R2=0, and calculating (I1+R1)+(I2+R2) instead of (I1+I2), then it boils down to the case in which the condition (1) holds. Also, the case is very rare (a probability of 1/q or something like it when the size of the defining field k is taken as q) in which the condition (1) is not met, whereby only the case in which the condition (1) is met should be considered in evaluating efficiency of the algorithm. Thereupon, hereinafter, assume that I1 and I2 meet the condition (1).

Suppose J=I1I2 is a product of I1 and I2 in R. I1 and I2 are both ideals of order 3, whereby the order of J becomes 6. Thus, the type of J is anyone of 61, 62, 63, 64, and 65. So as to decide which the type of J is, a linear relation should be found in a residue ring R/J among ten monomials

1, X, Y, X2, XY, Y2, X3, X2Y, XY2 and X4  (2)

An ideal Ii(i=1,2) is of type 31, whereby




  
    
      
        
          
            R
            /
            
              I
              i
            
          
          ≅
          
            
              k
              ·
              1
            
            ⊕
            
              k
              ·
              X
            
            ⊕
            
              k
              ·
              Y
            
          
        
        ⁢
        
          

        
        ⁢
        
          m
          ⁢
          
            
          
          ↦
          
            
          
          ⁢
          
            v
            m
            
              (
              i
              )
            
          
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          1
        
        ]
      
    
  




From the condition (1), it follows that




  
    
      
        
          
            R
            /
            J
          
          ≅
          
            
              R
              /
              
                I
                1
              
            
            ⊕
            
              R
              /
              
                I
                2
              
            
          
          ≅
          
            
              ⊕
              
                i
                =
                1
              
              6
            
            ⁢
            k
          
        
        ⁢
        
          

        
        ⁢
        
          m
          ↦
          
            (
            
              
                m
                ⁢
                
                  
                
                ⁢
                
                  mod
                  (
                  
                    I
                    i
                  
                  )
                
              
              ,
              
                m
                ⁢
                
                  
                
                ⁢
                
                  mod
                  ⁡
                  
                    (
                    
                      I
                      2
                    
                    )
                  
                
              
            
            )
          
          ↦
          
            
              v
              m
              
                (
                1
                )
              
            
            :
            
              v
              m
              
                (
                2
                )
              
            
          
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          2
        
        ]
      
    
  




where v(1)m:v(2)m is a six-dimensional vector over k to be obtained by connecting two vectors v(i)m(i=1,2). Thus, so as to find a linear relation in R/J among ten monomials mi in the equation (2), an intra-row linear relation of the following 10×6 matrix Mc should be found with vectors v(1)mi:v(2)mi(i=1, 2, . . . , 10) taken as a row.





  
    
      
        
          M
          C
        
        =
        
          (
          
            
              
                
                  
                    v
                    1
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    1
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    X
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    X
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    Y
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    Y
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      2
                    
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    
                      X
                      2
                    
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    XY
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    XY
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      Y
                      2
                    
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    
                      Y
                      2
                    
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      3
                    
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    
                      X
                      3
                    
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      
                        X
                        2
                      
                      ⁢
                      Y
                    
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    
                      
                        X
                        2
                      
                      ⁢
                      Y
                    
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      ⁢
                      
                        
                      
                      ⁢
                      
                        Y
                        2
                      
                    
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    
                      X
                      ⁢
                      
                        
                      
                      ⁢
                      
                        Y
                        2
                      
                    
                    
                      (
                      2
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      4
                    
                    
                      (
                      1
                      )
                    
                  
                  :
                  
                    v
                    
                      X
                      4
                    
                    
                      (
                      2
                      )
                    
                  
                
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          3
        
        ]
      
    
  




As well known, the intra-row linear relation of the matrix Mc is obtained by triangulating a matrix Mc with row-reducing transformation, and this allows a type of the ideal J and its Groebner basis to be obtained. The details will be described in embodiments.
(Remark)
In the event that the condition (1) does not hold for the ideals I1 and I2, the rank of the matrix Mc becomes equal to or less than 5. In calculating the ideal product of I1 and I2, at first, assume that they meet the condition (1) for calculation, and as a result of the row-reducing transformation, if it becomes clear that the rank of the matrix Mc is equal to or less than 5, then the elements R1 and R2 that yields R1+R2=0 should be generated to calculate (I1+R1)+(I2+R2) instead of I1+I2.
(Composition Operation 2)
Now study a first step of the additive algorithm 1 for the same ideals I1=I, and I2=I of the coordinate ring R=k[X,Y]/F, which is hereinafter referred to as a composition operation 2. That is, for an ideal product J=I2, its Groebner basis is to be found for calculation of fJ. The case is mentioned in which the ideal I is of type 31; however the other case is also similar. The order of the field k is supposed to be sufficiently large, whereby no multiple point exists in V(I) in almost every case. (3)
Also, in evaluating efficiency of the algorithm, only the case should be considered in which the condition (3) is met. Hereinafter, assume that I meets the condition (3). J=I2 is still an ideal of order 6, whereby, so as to calculate its Groebner basis, a linear relation should be found in the residue ring R/J among the monomials of the equation (1). The ideal I is of type 31, whereby




  
    
      
        
          
            R
            /
            I
          
          ≅
          
            
              k
              ·
              1
            
            ⊕
            
              k
              ·
              X
            
            ⊕
            
              k
              ·
              Y
            
          
        
        ⁢
        
          

        
        ⁢
        
          m
          ⁢
          
            
          
          ↦
          
            
          
          ⁢
          
            v
            m
          
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          4
        
        ]
      
    
  




Also, from the condition (3), the necessary and sufficient condition for causing the polynomial f(∈R) to belong to J=I2 is

f∈I,fXFY−fYFX∈I

(Here, for the polynomial f, fX denotes a differential of f with regard to X. As to fY as well, the matter is similar.) Thus,





  
    
      
        
          
            R
            /
            J
          
          ≅
          
            
              R
              /
              I
            
            ⊕
            
              R
              /
              I
            
          
          ≅
          
            
              ⊕
              
                i
                =
                1
              
              6
            
            ⁢
            k
          
        
        ⁢
        
          
        
        ⁢
        
          

        
        ⁢
        
          m
          ↦
          
            (
            
              
                m
                ⁢
                
                  
                
                ⁢
                
                  mod
                  (
                  I
                  )
                
              
              ,
              
                
                  
                    m
                    X
                  
                  ⁢
                  
                    F
                    Y
                  
                
                -
                
                  
                    m
                    Y
                  
                  ⁢
                  
                    F
                    X
                  
                  ⁢
                  
                    mod
                    ⁡
                    
                      (
                      I
                      )
                    
                  
                
              
            
            )
          
          ↦
          
            
              v
              m
            
            :
            
              v
              
                (
                
                  
                    
                      m
                      X
                    
                    ⁢
                    
                      F
                      Y
                    
                  
                  -
                  
                    
                      m
                      Y
                    
                    ⁢
                    
                      F
                      X
                    
                  
                
                )
              
            
          
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          5
        
        ]
      
    
  




Where, vm:v(mX FY−mY FX) is a six-dimensional vector over k to be obtained by connecting two vectors vm and v(mX FY−mY FX). After all, so as to find the above-mentioned linear relation, for ten monomials mi in the equation (1), a intra-row linear relation should be found of the following 10×6 matrix MD mentioned below with a six-dimensional vector vmi:v(miX FY−miY FX) over k taken as a row.




  
    
      
        
          M
          C
        
        =
        
          (
          
            
              
                
                  
                    v
                    1
                  
                  :
                  0
                
              
            
            
              
                
                  
                    v
                    X
                  
                  :
                  
                    v
                    
                      (
                      
                        F
                        Y
                      
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    Y
                  
                  :
                  
                    v
                    
                      (
                      
                        -
                        
                          F
                          X
                        
                      
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      2
                    
                  
                  :
                  
                    v
                    
                      (
                      
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        
                          F
                          Y
                        
                        ⁢
                        X
                      
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      ⁢
                      
                        
                      
                      ⁢
                      Y
                    
                  
                  :
                  
                    v
                    
                      (
                      
                        
                          
                            -
                            
                              F
                              X
                            
                          
                          ⁢
                          X
                        
                        +
                        
                          
                            F
                            Y
                          
                          ⁢
                          Y
                        
                      
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      Y
                      2
                    
                  
                  :
                  
                    v
                    
                      (
                      
                        
                          -
                          2
                        
                        ⁢
                        
                          F
                          X
                        
                        ⁢
                        Y
                      
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      3
                    
                  
                  :
                  
                    v
                    
                      (
                      
                        3
                        ⁢
                        
                          F
                          Y
                        
                        ⁢
                        
                          X
                          2
                        
                      
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      
                        X
                        2
                      
                      ⁢
                      Y
                    
                  
                  :
                  
                    v
                    
                      (
                      
                        
                          
                            -
                            
                              F
                              X
                            
                          
                          ⁢
                          
                            X
                            2
                          
                        
                        +
                        
                          2
                          ⁢
                          
                            F
                            Y
                          
                          ⁢
                          X
                          ⁢
                          
                            
                          
                          ⁢
                          Y
                        
                      
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      ⁢
                      
                        
                      
                      ⁢
                      
                        Y
                        2
                      
                    
                  
                  :
                  
                    v
                    
                      (
                      
                        
                          
                            -
                            2
                          
                          ⁢
                          
                            F
                            X
                          
                          ⁢
                          X
                          ⁢
                          
                            
                          
                          ⁢
                          Y
                        
                        +
                        
                          
                            F
                            Y
                          
                          ⁢
                          
                            Y
                            2
                          
                        
                      
                      )
                    
                  
                
              
            
            
              
                
                  
                    v
                    
                      X
                      4
                    
                  
                  :
                  
                    v
                    
                      (
                      
                        4
                        ⁢
                        
                          F
                          Y
                        
                        ⁢
                        
                          X
                          3
                        
                      
                      )
                    
                  
                
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          6
        
        ]
      
    
  




From now on, upon triangulating the matrix MD with the row-reducing transformation, the type of the ideal J and its Groebner basis can be obtained similarly to the composition operation 1.
(Remark)
In the event that the condition (3) does not hold for the ideal I, the rank of the matrix MD becomes equal to or less than 5. In calculating the Groebner basis of I2, at first, assume that it meets the condition (3) for calculation, and as a result of the row-reducing transformation, if it becomes clear that the rank of the matrix MD is equal to or less than 5, then elements R1 and R2 that yields R1+R2=0 should be generated to calculate (I+R1)+(I+R2) instead of I+I.
(Reduction Operation)
Now study a second step (and a third step) of the additive algorithm 1, which is hereinafter referred to as a reduction operation. That is, for the ideal J of which the order is equal to or less than 6, the Groebner basis of J*=fJ:J is to be found. The case is mentioned below in which J is of type 61; however the other case is also similar.
J is of type 61, whereby its Groebner basis can be expressed by

{fJ=X3+a6Y2+ . . . , g=X2Y+b6Y2+ . . . , h=XY2+c6Y2+ . . . }

By definition, J*=fJ:J, whereby δ(J*)=−v∞(fJ)−δ(J)=3. Thus, it can be seen that J* becomes an ideal of a type 31 because J* is a reduced ideal. Thus so as to find its Groebner basis, for the monomial mi in

1, X, Y, X2, XY, and Y2  (4)

a linear relation Σidimi should be found in which Σidimig and Σidimih become zero simultaneously in R/fJ.

From LM(F)=Y3,LM(fJ)=X3, then




  
    
      
        
          
            
              
                R
                /
                
                  f
                  J
                
              
              ⁢
              R
            
            ≅
            
              
                k
                ·
                1
              
              ⊕
              
                k
                ·
                X
              
              ⊕
              
                k
                ·
                Y
              
              ⊕
              
                k
                ·
                
                  X
                  2
                
              
              ⊕
              
                
                  k
                  ·
                  X
                
                ⁢
                
                  
                
                ⁢
                Y
              
              ⊕
              
                k
                ·
                
                  Y
                  2
                
              
              ⊕
              
                k
                ·
                
                  

                
                ⁢
                f
              
            
          
          ⁢
          
            
          
          ↦
          
            
          
          ⁢
          
            w
            j
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              X
              2
            
            ⁢
            Y
          
          ⊕
          
            
              k
              ·
              X
            
            ⁢
            
              
            
            ⁢
            
              Y
              2
            
          
          ⊕
          
            
              k
              ·
              
                X
                2
              
            
            ⁢
            
              
            
            ⁢
            
              Y
              2
            
          
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          7
        
        ]
      
    
  




whereby, so as to find the above-mentioned linear relation, for each of six monomials mi in the equation (4), an intra-row linear relation should be found of the following 6×18 matrix MR with a 18-dimensional vector w(mi g):w(mi h) over k to be obtained by connecting two vectors w(mi g) and w(mi h) taken as a row.





  
    
      
        
          M
          R
        
        =
        
          (
          
            
              
                
                  
                    w
                    g
                  
                  :
                  
                    w
                    h
                  
                
              
            
            
              
                
                  
                    w
                    
                      X
                      ⁢
                      
                        
                      
                      ⁢
                      g
                    
                  
                  :
                  
                    w
                    
                      X
                      ⁢
                      
                        
                      
                      ⁢
                      h
                    
                  
                
              
            
            
              
                
                  
                    w
                    
                      Y
                      ⁢
                      
                        
                      
                      ⁢
                      g
                    
                  
                  :
                  
                    w
                    
                      Y
                      ⁢
                      
                        
                      
                      ⁢
                      h
                    
                  
                
              
            
            
              
                
                  
                    w
                    
                      
                        X
                        2
                      
                      ⁢
                      g
                    
                  
                  :
                  
                    w
                    
                      
                        X
                        2
                      
                      ⁢
                      h
                    
                  
                
              
            
            
              
                
                  
                    w
                    
                      X
                      ⁢
                      
                        
                      
                      ⁢
                      
                        Y
                        g
                      
                    
                  
                  :
                  
                    w
                    
                      X
                      ⁢
                      
                        
                      
                      ⁢
                      Y
                      ⁢
                      
                        
                      
                      ⁢
                      h
                    
                  
                
              
            
            
              
                
                  
                    w
                    
                      
                        Y
                        2
                      
                      ⁢
                      g
                    
                  
                  :
                  
                    w
                    
                      
                        Y
                        2
                      
                      ⁢
                      h
                    
                  
                
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          8
        
        ]
      
    
  




From now on, upon triangulating the matrix MR with the row-reducing transformation, the Groebner basis of the ideal J* can be obtained. However, as matter of fact, in almost every case, it is enough to triangulate not the matrix MR itself but a certain submatrix Mr of its 6×3. This will be described in details in the next chapter.
(Arithmetic Quantity of Algorithm)
An arithmetic quantity of the algorithm will be evaluated. Set the order of the defining field to q, then a random element of the Jacobian group is represented by the ideal of a type 31 apart from an exception of a probability of 1/q. Also, the result of the composition operations 1 and 2 for the ideal of a type 31 demonstrates that it becomes an ideal of a type 61 apart from an exception of a probability of 1/q. Thus, so as to evaluate the arithmetic quantity of the algorithm, the arithmetic quantity of the composition operations 1 and 2 at the time of having input the ideal of a type 31, and the arithmetic quantity of the reduction operation at the time of having input the ideal of a type 61 or a type 31 should be evaluated. Also, the arithmetic quantity of the algorithm is represented below with the number of the times of multiplication and reciprocal arithmetic.
At first, the arithmetic quantity of the composition operation 1 is examined. Suppose that I1 and I2 are ideals of type 31: then

I1={X2+a3Y+a2X+a1,XY+b3Y+b2X+b1,Y2+c3Y+c2X+c1}

I2={X2+s3Y+s2X+s1,XY+t3Y+t2X+t1,Y2+u3Y+u2X+u1}

For the ideals I1 and I2, the matrix Mc is expressed by





  
    
      
        
          M
          C
        
        =
        
          (
          
            
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
            
            
              
                
                  -
                  
                    a
                    1
                  
                
              
              
                
                  -
                  
                    a
                    2
                  
                
              
              
                
                  -
                  
                    a
                    3
                  
                
              
              
                
                  -
                  
                    s
                    1
                  
                
              
              
                
                  -
                  
                    s
                    2
                  
                
              
              
                
                  -
                  
                    s
                    3
                  
                
              
            
            
              
                
                  -
                  
                    b
                    1
                  
                
              
              
                
                  -
                  
                    b
                    2
                  
                
              
              
                
                  -
                  
                    b
                    3
                  
                
              
              
                
                  -
                  
                    t
                    1
                  
                
              
              
                
                  -
                  
                    t
                    2
                  
                
              
              
                
                  -
                  
                    t
                    3
                  
                
              
            
            
              
                
                  -
                  
                    c
                    1
                  
                
              
              
                
                  -
                  
                    c
                    2
                  
                
              
              
                
                  -
                  
                    c
                    3
                  
                
              
              
                
                  -
                  
                    u
                    1
                  
                
              
              
                
                  -
                  
                    u
                    2
                  
                
              
              
                
                  -
                  
                    u
                    3
                  
                
              
            
            
              
                
                  
                    
                      a
                      1
                    
                    ⁢
                    
                      a
                      2
                    
                  
                  +
                  
                    
                      a
                      3
                    
                    ⁢
                    
                      b
                      1
                    
                  
                
              
              
                
                  
                    -
                    
                      a
                      1
                    
                  
                  +
                  
                    a
                    2
                    2
                  
                  +
                  
                    
                      a
                      3
                    
                    ⁢
                    
                      b
                      2
                    
                  
                
              
              
                
                  
                    
                      a
                      2
                    
                    ⁢
                    
                      a
                      3
                    
                  
                  +
                  
                    
                      a
                      3
                    
                    ⁢
                    
                      b
                      3
                    
                  
                
              
              
                
                  
                    
                      s
                      1
                    
                    ⁢
                    
                      s
                      2
                    
                  
                  +
                  
                    
                      s
                      3
                    
                    ⁢
                    
                      t
                      1
                    
                  
                
              
              
                
                  
                    -
                    
                      s
                      1
                    
                  
                  +
                  
                    s
                    2
                    2
                  
                  +
                  
                    
                      s
                      3
                    
                    ⁢
                    
                      t
                      2
                    
                  
                
              
              
                
                  
                    
                      s
                      2
                    
                    ⁢
                    
                      s
                      3
                    
                  
                  +
                  
                    
                      s
                      3
                    
                    ⁢
                    
                      t
                      3
                    
                  
                
              
            
            
              
                
                  
                    
                      a
                      2
                    
                    ⁢
                    
                      b
                      1
                    
                  
                  +
                  
                    
                      a
                      3
                    
                    ⁢
                    
                      c
                      1
                    
                  
                
              
              
                
                  
                    
                      a
                      2
                    
                    ⁢
                    
                      b
                      2
                    
                  
                  +
                  
                    
                      a
                      3
                    
                    ⁢
                    
                      c
                      2
                    
                  
                
              
              
                
                  
                    -
                    
                      a
                      1
                    
                  
                  +
                  
                    
                      a
                      2
                    
                    ⁢
                    
                      b
                      3
                    
                  
                  +
                  
                    
                      a
                      3
                    
                    ⁢
                    
                      c
                      3
                    
                  
                
              
              
                
                  
                    
                      s
                      2
                    
                    ⁢
                    
                      t
                      1
                    
                  
                  +
                  
                    
                      s
                      3
                    
                    ⁢
                    
                      u
                      1
                    
                  
                
              
              
                
                  
                    
                      s
                      2
                    
                    ⁢
                    
                      t
                      2
                    
                  
                  +
                  
                    
                      s
                      3
                    
                    ⁢
                    
                      u
                      2
                    
                  
                
              
              
                
                  
                    -
                    
                      s
                      1
                    
                  
                  +
                  
                    
                      s
                      2
                    
                    ⁢
                    
                      t
                      3
                    
                  
                  +
                  
                    
                      s
                      3
                    
                    ⁢
                    
                      u
                      3
                    
                  
                
              
            
            
              
                
                  
                    
                      b
                      1
                    
                    ⁢
                    
                      b
                      2
                    
                  
                  +
                  
                    
                      b
                      3
                    
                    ⁢
                    
                      c
                      1
                    
                  
                
              
              
                
                  
                    b
                    2
                    2
                  
                  +
                  
                    
                      b
                      3
                    
                    ⁢
                    
                      c
                      2
                    
                  
                
              
              
                
                  
                    -
                    
                      b
                      1
                    
                  
                  +
                  
                    
                      b
                      2
                    
                    ⁢
                    
                      b
                      3
                    
                  
                  +
                  
                    
                      b
                      3
                    
                    ⁢
                    
                      c
                      3
                    
                  
                
              
              
                
                  
                    
                      t
                      1
                    
                    ⁢
                    
                      t
                      2
                    
                  
                  +
                  
                    
                      t
                      3
                    
                    ⁢
                    
                      u
                      1
                    
                  
                
              
              
                
                  
                    t
                    2
                    2
                  
                  +
                  
                    
                      t
                      3
                    
                    ⁢
                    
                      u
                      2
                    
                  
                
              
              
                
                  
                    -
                    
                      t
                      1
                    
                  
                  +
                  
                    
                      t
                      2
                    
                    ⁢
                    
                      t
                      3
                    
                  
                  +
                  
                    
                      t
                      3
                    
                    ⁢
                    
                      u
                      3
                    
                  
                
              
            
            
              
                
                  e
                  
                    10
                    ,
                    1
                  
                
              
              
                
                  e
                  
                    10
                    ,
                    2
                  
                
              
              
                
                  e
                  
                    10
                    ,
                    3
                  
                
              
              
                
                  e
                  
                    10
                    ,
                    4
                  
                
              
              
                
                  e
                  
                    10
                    ,
                    5
                  
                
              
              
                
                  e
                  
                    10
                    ,
                    6
                  
                
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          9
        
        ]
      
    
  




where,

e10,1=a12−a1a22−2a2a3b1−a32c1

e10,2=2a1a2−a23−2a2a3b2−a32c2

e10,3=2a1a3−a22a3−2a2a3b3−a32c3

e10,4=s12−s1s22−2s2s3t1−s32u1

e10,5=2s1s2−s23−2s2s3t2−s32u2

e10,6=2s1s3−s22s3−2s2s3t3−s32u3

From this, it can be seen that upon eliminating multiplicity successfully, the matrix Mc can be constructed with at most 44-times multiplication.

Upon paying attention to the fact that the row-reduction transformation for the matrix Mc′ takes a formula having the first row to the third row thereof already row-reduction, and that its component is 0 or 1, it can be executed with three-times division and at most 6×6+6×5+6×4=90-times multiplication. From the foregoing, the arithmetic quantity of the composition operation 1 is at most three-times reciprocal arithmetic, and 134-times multiplication. Similarly, it can be seen that the arithmetic quantity of the composition operation 2 is at most three-times reciprocal arithmetic, and 214-times multiplication. The arithmetic quantity is increased by the extent to which the matrix MD is more complex than Mc.
Next, the arithmetic quantity of the reduction operation at the time of having input the ideal of a type 61 is examined. Suppose J is an ideal of type 61: then

J={X3+a6Y2+a5XY+a4X2+a3Y+a2X+a1,X2Y+b6Y2+b5XY+b4X2+b3Y+b2x+b1,XY2+c6Y2+c5XY+c4X2+c3Y+c2X+c1}

A 6×3 minor Mr obtained by taking a seventh column to a ninth column of the matrix MR for the ideal J becomes



  
    
      
    
    ⁢
    
      [
      
        EQ
        .
        
          
        
        ⁢
        10
      
      ]
    
  




  
    
      M
      r
    
    =
    
      (
      
        
          
            1
          
          
            0
          
          
            0
          
        
        
          
            
              
                -
                
                  a
                  4
                
              
              -
              
                
                  a
                  5
                
                ⁢
                
                  a
                  6
                
              
              +
              
                b
                5
              
            
          
          
            
              
                -
                
                  a
                  5
                
              
              -
              
                a
                6
                2
              
              +
              
                b
                6
              
            
          
          
            0
          
        
        
          
            
              
                b
                4
              
              +
              
                
                  a
                  5
                
                ⁢
                
                  b
                  6
                
              
            
          
          
            
              
                b
                5
              
              +
              
                
                  a
                  6
                
                ⁢
                
                  b
                  6
                
              
            
          
          
            1
          
        
        
          
            
              e
              
                4
                ,
                1
              
            
          
          
            
              e
              
                4
                ,
                2
              
            
          
          
            
              
                -
                
                  a
                  5
                
              
              -
              
                a
                6
                2
              
              +
              
                b
                6
              
            
          
        
        
          
            
              e
              
                5
                ,
                1
              
            
          
          
            
              e
              
                5
                ,
                2
              
            
          
          
            
              
                -
                
                  a
                  4
                
              
              -
              
                2
                ⁢
                
                  a
                  5
                
                ⁢
                
                  a
                  6
                
              
              -
              
                a
                6
                3
              
              +
              
                b
                5
              
              +
              
                
                  a
                  6
                
                ⁢
                
                  b
                  6
                
              
            
          
        
        
          
            
              e
              
                6
                ,
                1
              
            
          
          
            
              e
              
                6
                ,
                2
              
            
          
          
            
              e
              
                6
                ,
                3
              
            
          
        
      
      ⁢
      
        
      
      )
    
  



where




  
    
      e
      
        4
        ,
        1
      
    
    =
    
      
        -
        
          a
          2
        
      
      +
      
        a
        4
        2
      
      -
      
        
          a
          3
        
        ⁢
        
          a
          6
        
      
      +
      
        3
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          a
          6
        
      
      +
      
        
          a
          5
          2
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        b
        3
      
      -
      
        
          a
          5
        
        ⁢
        
          b
          4
        
      
      -
      
        
          a
          4
        
        ⁢
        
          b
          5
        
      
      -
      
        
          a
          5
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          5
        
      
    
  




  
    
      e
      
        4
        ,
        2
      
    
    =
    
      
        -
        
          a
          3
        
      
      +
      
        
          a
          4
        
        ⁢
        
          a
          5
        
      
      +
      
        
          a
          5
          2
        
        ⁢
        
          a
          6
        
      
      +
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        
          a
          5
        
        ⁢
        
          a
          6
          3
        
      
      -
      
        
          a
          6
        
        ⁢
        
          b
          4
        
      
      -
      
        
          a
          5
        
        ⁢
        
          b
          5
        
      
      -
      
        
          a
          6
          2
        
        ⁢
        
          b
          5
        
      
    
  




  
    
      e
      
        5
        ,
        1
      
    
    =
    
      
        
          -
          2
        
        ⁢
        
          a
          3
        
        ⁢
        
          a
          5
        
      
      +
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
          2
        
      
      -
      
        
          a
          2
        
        ⁢
        
          a
          6
        
      
      +
      
        
          a
          4
          2
        
        ⁢
        
          a
          6
        
      
      +
      
        
          a
          5
          3
        
        ⁢
        
          a
          6
        
      
      -
      
        
          a
          3
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        3
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        
          a
          5
          2
        
        ⁢
        
          a
          6
          3
        
      
      +
      
        b
        2
      
      -
      
        
          a
          4
        
        ⁢
        
          b
          4
        
      
      -
      
        
          a
          5
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          4
        
      
      +
      
        
          a
          3
        
        ⁢
        
          b
          6
        
      
      -
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          b
          6
        
      
      -
      
        
          a
          5
          2
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          6
        
      
    
  




  
    
      e
      
        5
        ,
        2
      
    
    =
    
      
        -
        
          a
          2
        
      
      +
      
        a
        5
        3
      
      -
      
        2
        ⁢
        
          a
          3
        
        ⁢
        
          a
          6
        
      
      +
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          a
          6
        
      
      +
      
        2
        ⁢
        
          a
          5
          2
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          6
          3
        
      
      +
      
        
          a
          5
        
        ⁢
        
          a
          6
          4
        
      
      +
      
        b
        3
      
      -
      
        
          a
          5
        
        ⁢
        
          b
          4
        
      
      -
      
        
          a
          6
          2
        
        ⁢
        
          b
          4
        
      
      -
      
        
          a
          5
          2
        
        ⁢
        
          b
          6
        
      
      -
      
        
          a
          4
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          6
        
      
      -
      
        
          a
          5
        
        ⁢
        
          a
          6
          2
        
        ⁢
        
          b
          6
        
      
    
  




  
    
      e
      
        6
        ,
        1
      
    
    =
    
      
        
          -
          2
        
        ⁢
        
          a
          3
        
        ⁢
        
          a
          4
        
      
      -
      
        2
        ⁢
        
          a
          2
        
        ⁢
        
          a
          5
        
      
      +
      
        3
        ⁢
        
          a
          4
          2
        
        ⁢
        
          a
          5
        
      
      -
      
        4
        ⁢
        
          a
          3
        
        ⁢
        
          a
          5
        
        ⁢
        
          a
          6
        
        ⁢
        6
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
          2
        
        ⁢
        
          a
          6
        
      
      -
      
        
          a
          2
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        
          a
          4
          2
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        2
        ⁢
        
          a
          5
          3
        
        ⁢
        
          a
          6
          2
        
      
      -
      
        
          a
          3
        
        ⁢
        
          a
          6
          3
        
      
      +
      
        3
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          a
          6
          3
        
      
      +
      
        
          a
          5
          2
        
        ⁢
        
          a
          6
          4
        
      
      +
      
        
          a
          5
        
        ⁢
        
          b
          3
        
      
      +
      
        
          a
          3
        
        ⁢
        
          b
          5
        
      
      -
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          b
          5
        
      
      -
      
        
          a
          5
          2
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          5
        
      
      +
      
        
          a
          2
        
        ⁢
        
          b
          6
        
      
      -
      
        
          a
          4
          2
        
        ⁢
        
          b
          6
        
      
      +
      
        
          a
          3
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          6
        
      
      -
      
        3
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          6
        
      
      -
      
        
          a
          5
          2
        
        ⁢
        
          a
          6
          2
        
        ⁢
        
          b
          6
        
      
    
  




  
    
      e
      
        6
        ,
        2
      
    
    =
    
      
        
          -
          2
        
        ⁢
        
          a
          3
        
        ⁢
        
          a
          5
        
      
      +
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
          2
        
      
      -
      
        2
        ⁢
        
          a
          2
        
        ⁢
        
          a
          6
        
      
      +
      
        
          a
          4
          2
        
        ⁢
        
          a
          6
        
      
      +
      
        2
        ⁢
        
          a
          5
          3
        
        ⁢
        
          a
          6
        
      
      -
      
        3
        ⁢
        
          a
          3
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        5
        ⁢
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          a
          6
          2
        
      
      +
      
        3
        ⁢
        
          a
          5
          2
        
        ⁢
        
          a
          6
          3
        
      
      +
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          6
          4
        
      
      +
      
        
          a
          5
        
        ⁢
        
          a
          6
          5
        
      
      +
      
        b
        2
      
      +
      
        
          a
          6
        
        ⁢
        
          b
          3
        
      
      -
      
        
          a
          5
          2
        
        ⁢
        
          b
          5
        
      
      -
      
        
          a
          4
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          5
        
      
      -
      
        
          a
          5
        
        ⁢
        
          a
          6
          2
        
        ⁢
        
          b
          5
        
      
      +
      
        
          a
          3
        
        ⁢
        
          b
          6
        
      
      -
      
        
          a
          4
        
        ⁢
        
          a
          5
        
        ⁢
        
          b
          6
        
      
      -
      
        
          a
          5
          2
        
        ⁢
        
          a
          6
        
        ⁢
        
          b
          6
        
      
      -
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          6
          2
        
        ⁢
        
          b
          6
        
      
      -
      
        
          a
          5
        
        ⁢
        
          a
          6
          3
        
        ⁢
        
          b
          6
        
      
    
  




  
    
      e
      
        6
        ,
        3
      
    
    =
    
      
        -
        
          a
          5
          2
        
      
      -
      
        2
        ⁢
        
          a
          4
        
        ⁢
        
          a
          6
        
      
      -
      
        3
        ⁢
        
          a
          5
        
        ⁢
        
          a
          6
          2
        
      
      -
      
        a
        6
        4
      
      +
      
        b
        4
      
      +
      
        
          a
          6
        
        ⁢
        
          b
          5
        
      
      +
      
        
          a
          5
        
        ⁢
        
          b
          6
        
      
      +
      
        
          a
          6
          2
        
        ⁢
        
          b
          6
        
      
    
  



This leads to the result that, if a (2,2) component d=−a5−a62+b6 of the matrix Mr is not zero, the rank of the matrix Mr becomes 3. Thus, when d≠0, instead of the 6×18 matrix MR the 6×3 matrix Mr should be employed that is its minor. It is acceptable to let d≠0 in evaluating efficiency of the algorithm because the probability of d=0 is considered to be 1/q or something like it. From the above equation, it can be seen that upon eliminating multiplicity successfully, the matrix Mr can be constructed with at most 40-times multiplication. Upon paying attention to the fact that the matrix Mr is already a triangle matrix, and that (1,1) and (3,3) components thereof are 1, it can be seen that the row-reduction transformation for the matrix Mr′ can be executed with at most one-time reciprocal arithmetic and 2×4+2×3=14-times multiplication. From the foregoing, the arithmetic quantity of the reduction operation at the time of inputting the ideal of a type 61 is at most one-time reciprocal arithmetic and 54-times multiplication. Also at the time of inputting the ideal of a type 31, from the similar consideration, it can be seen that the reduction operation requires most one-time reciprocal arithmetic and 16-times multiplication.
Upon summarizing the foregoing, it follows that the arithmetic quantity of the additive algorithm on Jacobian group of the present invention is one as shown in FIG. 16. In FIG. 16, I and M represent the reciprocal arithmetic and the multiplication respectively. On the elliptic curve, the addition (of different elements) can be executed with one-time reciprocal arithmetic and three-times multiplication, and the arithmetic of two-times multiple can be executed with one-time reciprocal arithmetic and four-times multiplication. However, so as to obtain a group of the same bit length, the bit length of the finite field requires three times as large arithmetic quantity as the case of the C34 curve does. Suppose that the arithmetic quantity of the reciprocal arithmetic is twenty times as large as that of the multiplication, and that the arithmetic quantity of the reciprocal arithmetic and the multiplication is on the order of a square of the bit length, then it can be seen that the addition on the C34 curve can be executed with 304/(23×9)≈1.47 times as large arithmetic quantities as that on the elliptic cure can be done, and the arithmetic of two-times multiple 384/(24×9)≈1.78 times.



BRIEF DESCRIPTION OF THE DRAWING
This and other objects, features and advantages of the present invention will become more apparent upon a reading of the following detailed description and drawings, in which:
FIG. 1 is a block diagram illustrating an embodiment of the present invention;
FIG. 2 is a functional block diagram of an ideal composition section;
FIG. 3 is a functional block diagram of an ideal reduction section;
FIG. 4 is one specific example of an algebraic curve parameter file A for the C34 curve;
FIG. 5 is one specific example of an ideal type table for the C34 curve;
FIG. 6 is one specific example of a monomial list table for the C34 curve;
FIG. 7 is one specific example of a table for a Groebner basis construction for the C34 curve;
FIG. 8 is one specific example of the algebraic curve parameter file for the C27 curve;
FIG. 9 is one specific example of the ideal type table for the C27 curve;
FIG. 10 is one specific example of the monomial list table for the C27 curve;
FIG. 11 is one specific example of the table for a Groebner basis construction for the C27 curve;
FIG. 12 is one specific example of the algebraic curve parameter file for the C25 curve;
FIG. 13 is one specific example of the ideal type table for the C25 curve;
FIG. 14 is one specific example of the monomial list table for the C25 curve;
FIG. 15 is one specific example of the table for a Groebner basis construction table for the C25 curve; and
FIG. 16 is a table illustrating the arithmetic quantity of the additive algorithm on Jacobian group in accordance with the present invention.



DESCRIPTION OF THE EMBODIMENT
Embodiments of the present invention will be explained below in details by employing the accompanied drawings. FIG. 1 is a functional block diagram of the embodiment of the present invention, and the FIG. 2 is a block diagram illustrating an example of the ideal composition section of FIG. 1. FIG. 3 is a block diagram illustrating an example of a first and a second ideal reduction section of FIG. 1.
At first, the embodiment of the case in which the C34 curve was employed is shown. In this embodiment, the algebraic curve parameter file of FIG. 4 is employed as an algebraic curve parameter file, the ideal type table of FIG. 5 as an ideal type table, the monomial list table of FIG. 6 as an monomial list table, and the table for a Groebner basis construction of FIG. 7 as a table for a Groebner basis construction respectively.
In a Jacobian group element adder of FIG. 1, suppose the Groebner bases

I1={X2+726Y+836X+355,XY+36Y+428X+477,Y2+764Y+425X+865}

and

I2={X2+838Y+784X+97,XY+602Y+450X+291,Y2+506Y+542X+497}

were input of the ideal of the coordinate ring of the algebraic curve designated by an algebraic curve parameter file A, which represents an element of the Jacobian group of the C34 curve designated by an algebraic curve parameter file A 16 and an algebraic curve parameter file A of FIG. 4.

At first, an ideal composition section 11, which takes the above-mentioned algebraic curve parameter file A, and the above-mentioned Groebner bases I1 and I2 as an input, operates as follows according to a flow of a process of the functional block shown in FIG. 2. At first, the ideal composition section 11 makes a reference to an ideal type table 25 of FIG. 5 in an ideal type classification section 21 of FIG. 2, retrieves a record in which the ideal type described in an ideal type field accords with the type of the input ideal I1 for obtaining a fourteenth record, and acquires a value N1=31 of an ideal type number field and a value d1=3 of an order field of the fourteenth record.
Similarly, the ideal composition section 11 retrieves a record in which the ideal type accords with the type of the input ideal I2 for obtaining the fourteenth record, and acquires a value N2=31 of the ideal type number field and a value d2=3 of the order field of the fourteenth record.
Next, the ideal composition section 11 calculates the sum d3=d1+d2=6 of said values d1=3 and d2=3 of said order field in a monomial vector generation section 22, makes a reference to a monomial list table 26, retrieves a record of which the value of the order field is said d3=6 for obtaining a first record, and acquires a list 1, X, Y, X2, XY, Y2, X3, X2Y, XY2, and X4 of the monomial described in the monomial list field of the first record.
I1 and I2 are different, whereby a remainder to be attained by dividing Mi by I1 for each of Mi(1<=i<=10) in said list 1, X, Y, X2, XY, Y2, X3, X2Y, XY2, and X4 of said monomial is calculated to obtained a polynomial a(i)1+a(i)2X+a(i)3Y, to arrange its coefficients in order of the monomial order 1, X, Y, . . . of the algebraic curve parameter file A, and to generate a vector (a(i)1,a(i)2, a(i)3). Furthermore, a remainder to be attained by dividing Mi by I2 is calculated to obtain a polynomial b(i)1+b(i)2X+b(i)3Y, to arrange its coefficients in order of the monomial order 1, X, Y, . . . of the algebraic curve parameter file A, to generate a vector (b(i)1,b(i)2,b(i)3), and to connect the above-mentioned two vectors for generating a vector vi=(a(i)1,a(i)2,a(i)3,b(i)1,b(i)2,b(i)3)
That is, divide M1=1 by I1: then I=0·(X2+726Y+836X+355)+0·(XY+36Y+428X+477)+0·(Y2+746Y+425X+865)+1 whereby, 1 is obtained as a remainder to generate a vector (1,0,0). Divide M1=1 by I2: then I=0·(X2+838Y+784X+97)+0·(XY+602Y+450X+291)+0·(Y2+506Y+524X+497)+1 whereby, 1 is obtained as a remainder to generate a vector (1,0,0). These two vectors are connected to generate a vector v1=(1,0,0,1,0,0).
Next, divide M2=X by I1: then X=0·(X2+726Y+836X+355)+0·(XY+36Y+428X+477)+0·(Y2+746Y+425X+865)+X whereby, X is obtained as a remainder to generate a vector (0,1,0). Divide M2=X by I2: then 1=0·(X2+838Y+784X+97)+0·(XY+602Y+450X+291)+0·(Y2+506Y+524X+497)+X whereby, X is obtained as a remainder to generate a vector (0,1,0). These two vectors are connected to generate a vector v2=(0,1,0,0,1,0).
Next, divide M3=Y by I1: then Y=0·(X2+726Y+836X+355)+0·(XY+36Y+428X+477)+0·(Y2+746Y+425X+865)+Y whereby, Y is obtained as a remainder to generate a vector (0,0,1). Divide M3=Y by I2: then Y=0·(X2+838Y+784X+97)+0·(XY+602Y+450X+291)+0·(Y2+506Y+524X+497)+Y whereby, Y is obtained as a remainder to generate a vector (0,0,1). These two vectors are connected to generate a vector v3=(0,0,1,0,0,1).
Next, divide M4=X2 by I1: then X2=1·(X2+726Y+836X+355)+0·(XY+36Y+428X+477)+0·(Y2+746Y+425X+865)+654+173X+283Y whereby, 654+173X+283Y is obtained as a remainder to generate a vector (654,173,283). Divide M4=X2 by I2: then X2=1·(X2+838Y+784X+97)+0·(XY+602Y+450X+291)+0·(Y2+506Y+524X+497)+912+225X+171Y, whereby, 912+225X+171Y is obtained as a remainder to generate a vector (912,225,171). These two vectors are connected to generate a vector v4=(654,173,283,912,225,171).
Next, divide M5=XY by I1: then XY=0·(X2+726Y+836X+355)+1·(XY+36Y+428X+477)+0·(Y2+746Y+425X+865)+532+581X+973Y whereby, 532+581X+973Y is obtained as a remainder to generate a vector (532,581,973). Divide M5=XY by I2: then XY=0·(X2+838Y+784X+97)+1·(XY+602Y+450X+291)+0·(Y2+506Y+524X+497)+718+559X+407Y, whereby, 718+559X+407Y is obtained as a remainder to generate a vector (718,559,407). These two vectors are connected to generate a vector v5=(532,581,973,718,559,407).
Next, divide M6=Y2 by I1: then Y2=0·(X2+726Y+836X+355)+0·(XY+36Y+428X+477)+1·(Y2+746Y+425X+865)+144+584X+263Y, whereby, 144+584X+263Y is obtained as a remainder to generate a vector (144,584,263). Divide M6=Y2 by I2: then Y2=0·(X2+838Y+784X+97)+0·(XY+602Y+450X+291)+1·(Y2+506Y+524X+497)+512+485X+503Y, whereby, 512+485X+503Y is obtained as a remainder to generate a vector (512,485,503). These two vectors are connected to generate a vector v6=(144,584,263,512,485,503).
Next, divide M7=X3 by I1: then X3=(173+X)·(X2+726Y+836X+355)+283·(XY+36Y+428X+477)+0·(Y2+746Y+425X+865)+349+269X+429Y, whereby, 349+269X+429Y is obtained as a remainder to generate a vector (349,269,429). Divide M7=X3 by I2: then X3=(255+X)·(X2+838Y+784X+97)+171·(XY+602Y+450X+291)+0·(Y2+506Y+524X+497)+53+821X+109Y, whereby, 53+821X+109Y is obtained as a remainder to generate a vector (53,821,109). These two vectors are connected to generate a vector v7=(349,269,429,53,821,109)
Next, divide M8=X2Y by I1: then X2Y=Y·(X2+726Y+836X+355)+173·(XY+36Y+428X+477)+283·(Y2+746Y+425X+865)+609+418X+243Y, whereby, 609+418X+243Y is obtained as a remainder to generate a vector (609,418,243). Divide M8=X2Y by I2: then X2Y=Y·(X2+838Y+784X+97)+225·(XY+602Y+450X+291)+171·(Y2+506Y+524X+497)+888+856X+916Y, whereby, 888+856X+916Y is obtained as a remainder to generate a vector (888,856,916). These two vectors are connected to generate a vector v8=(609,418,243,888,856,916).
Next, divide M9=XY2 by I1: then XY2=0·(X2+726Y+836X+355)+(581+Y)·(XY+36Y+428X+477)+973·(Y2+746Y+425X+865)+199+720X+418Y, whereby, 199+720X+418Y is obtained as a remainder to generate a vector (199,720,418). Divide M9=XY by I2: then XY2=0·(X2+838Y+784X+97)+(559+Y)·(XY+602Y+450X+291)+407·(Y2+506Y+524X+497)+310+331X+91Y, whereby, 310+331X+91Y is obtained as a remainder to generate a vector (310,331,91). These two vectors are connected to generate a vector v9=(199,720,418,310,331,91).
Next, divide M10=X4 by I1: then X4=(313+173X+X2+283Y)·(X2+726Y+836X+355)+45·(XY+36Y+428X+477)+378·(Y2+746Y+425X+865)+554+498X+143Y whereby, 554+498X+143Y is obtained as a remainder to generate a vector (554,498,143). Divide M10=X4 by I2: then X4=(78+225X+X2+171Y)·(X2+838Y+784X+97)+266·(XY+602Y+450X+291)+989·(Y2+506Y+524X+497)+643+522X+107Y, whereby, 643+522X+107Y is obtained as a remainder to generate a vector (643,522,107). These two vectors are connected to generate a vector v10=(554,498,143,643,522,107). Above, the process of the ideal composition section 11 in the monomial vector generation section 22 is finished.
Next, in a basis construction section 23, the ideal composition section 11 inputs ten six-dimensional vectors v1, v2, v3, v4, v5, v6, v7, v8, v9, and v10 generated in the monomial vector generation section 22 into a linear-relation derivation section 24, and obtains a plurality of 10-dimensional vectors m1, m2, . . . as an output. The linear-relation derivation section 24 derives a linear relation of the vectors, which were input, employing a discharging method. The discharging method is a well-known art, whereby, as to an operation of the linear-relation derivation section 24, only its outline is shown below.
The linear-relation derivation section 24 firstly arranges the ten six-dimensional vectors v1, v2, v3, v4, v5, v6, v7, v8, v9, and v10, which were input, in order for constructing a 10×6 matrix




  
    
      
        
          M
          c
        
        =
        
          (
          
            
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
            
            
              
                654
              
              
                173
              
              
                283
              
              
                912
              
              
                225
              
              
                171
              
            
            
              
                532
              
              
                581
              
              
                973
              
              
                718
              
              
                559
              
              
                407
              
            
            
              
                144
              
              
                584
              
              
                263
              
              
                512
              
              
                485
              
              
                503
              
            
            
              
                349
              
              
                269
              
              
                429
              
              
                53
              
              
                821
              
              
                109
              
            
            
              
                609
              
              
                418
              
              
                243
              
              
                888
              
              
                856
              
              
                916
              
            
            
              
                199
              
              
                720
              
              
                418
              
              
                310
              
              
                331
              
              
                91
              
            
            
              
                554
              
              
                498
              
              
                143
              
              
                643
              
              
                522
              
              
                107
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          11
        
        ]
      
    
  




Next, the linear-relation derivation section 24 connects a 10-dimensional unity matrix to a matrix Mc to obtain




  
    
      
        
          
        
        ⁢
        
          
            [
            
              EQ
              .
              
                
              
              ⁢
              12
            
            ]
          
          ⁢
          
            

          
          ⁢
          
            
              M
              c
            
            =
            
              (
              
                
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    654
                  
                  
                    173
                  
                  
                    283
                  
                  
                    912
                  
                  
                    225
                  
                  
                    171
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    532
                  
                  
                    581
                  
                  
                    973
                  
                  
                    718
                  
                  
                    559
                  
                  
                    407
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    144
                  
                  
                    584
                  
                  
                    263
                  
                  
                    512
                  
                  
                    485
                  
                  
                    503
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    349
                  
                  
                    269
                  
                  
                    429
                  
                  
                    53
                  
                  
                    821
                  
                  
                    109
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    609
                  
                  
                    418
                  
                  
                    243
                  
                  
                    888
                  
                  
                    856
                  
                  
                    916
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    199
                  
                  
                    720
                  
                  
                    418
                  
                  
                    310
                  
                  
                    331
                  
                  
                    91
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                
                
                  
                    554
                  
                  
                    498
                  
                  
                    143
                  
                  
                    643
                  
                  
                    522
                  
                  
                    107
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                
              
              )
            
          
        
      
    
    
      
        
      
    
  




Next, the linear-relation derivation section 24 triangulates a matrix M′c by adding a constant multiple of an i-th row to an (i+1)-th (i=1,2, . . . 6) row to a tenth row to obtain the following matrix m



  
    
      
    
    ⁢
    
      [
      
        EQ
        .
        
          
        
        ⁢
        13
      
      ]
    
  




  
    m
    =
    
      (
      
        
          
            1
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            258
          
          
            52
          
          
            897
          
          
            355
          
          
            836
          
          
            726
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            621
          
          
            688
          
          
            268
          
          
            365
          
          
            592
          
          
            187
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            31
          
          
            514
          
          
            469
          
          
            637
          
          
            669
          
          
            155
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            28
          
          
            132
          
          
            31
          
          
            271
          
          
            469
          
          
            166
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            856
          
          
            618
          
          
            747
          
          
            909
          
          
            132
          
          
            636
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            652
          
          
            322
          
          
            240
          
          
            978
          
          
            826
          
          
            846
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            333
          
          
            346
          
          
            980
          
          
            935
          
          
            824
          
          
            614
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
        
      
      ⁢
      
        
      
      )
    
  



As well known, the vector that is composed of a seventh component and afterward of the seventh row to the tenth row of the matrix m is a vector {m1,1,m1,2, . . . ,m1,n), (m2,1,m2,2, . . . ,m2,n) . . . } representing a linearly-independent linear dependence relation Σi10mjivi=0(j=1, 2, . . . ) of all of the ten six-dimensional vectors v1, v2, v3, v4, v5, v6, v7, v8, v9, and v10 that were input. The linear-relation derivation section 24 outputs a vector m1=(28,132,31,271,469,166,1,0,0,0) that is composed of the seventh component and afterward of the seventh row of the matrix m, a vector m2=(856,618,747,909,132,636,0,1,0,0) that is composed of the seventh component and afterward of the eighth row of the matrix m, and a vector m3=(652,322,240,978,826,846,0,0,1,0) that is composed of the seventh component and afterward of the ninth row of the matrix m, and a vector m4=(333,346,980,935,824,614,0,0,0,1) that is composed of the seventh component and afterward of the tenth row of the matrix m. Now return to the explanation of the process of the ideal composition section 11 in the basis construction section 23.
Next, the ideal composition section 11 makes a reference to a table 27 for a Groebner basis construction of FIG. 7, and retrieves a record, of which the value of the order field is said value d3=6, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(28,132,31,271,469,166,1,0,0,0), m2=(856,618,747,909,132,636,0,1,0,0), m3=(652,322,240,978,826,846,0,0,1,0), and m4=(333,346,980,935,824,614,0,0,0,1). The value of the order field of a first record is 6, and a vector, of which the component number lists 7, 8, 9, and 10 of the first record are all zero, does not lie in the vectors m1, m2, m3, and m4, whereby the first record is obtained as a retrieval result
Furthermore, the value of a first vector type of the first record is (*,*,*,*,*,*,1,0,0,0)(A code * is interpreted as representing any number), which coincides with the vector m1=(28,132,31,271,469,166,1,0,0,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, X3, X2Y, XY2, and X4 of the algebraic curve parameter file A to generate a polynomial f1=28+132X+31Y+271X2+469XY+166Y2+X3 
Similarly, the value of a second vector type of the first record is (*,*,*,*,*,*,0,1,0,0)(A code * is interpreted as representing any number), which coincides with the vector m2=(856,618,747,909,132,636,0,1,0,0), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, X3, X2Y, XY2, and X4 of the algebraic curve parameter file A to generate a polynomial f2=856+618X+747Y+909X2+132XY+636Y2+X2Y.
Similarly, the value of a third vector type of the first record is (*,*,*,*,*,*,0,0,1,0)(A code * is interpreted as representing any number), which coincides with the vector m3=(652,322,240,978,826,846,0,0,1,0), whereby the vector m3 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, X3, X2Y, XY2, and X4 of the algebraic curve parameter file A to generate a polynomial f3=652+322X+240Y+978X2+826XY+846Y2+XY2. Finally, the ideal composition section 11 constructs a set J={f1,f2,f3} of the polynomial to output it. Above, the operation of the ideal composition section 11 is finished.
Next, the first ideal reduction section 12, which takes as an input the algebraic curve parameter file A of FIG. 4, and the Groebner basis J={28+132X+31Y+271X2+469XY+166Y2+X3, 856+618X+747Y+909X2+132XY+636Y2+X2Y, 652+322X+240Y+978X2+826XY+846Y2+XY2}that the ideal composition section 11 output, operates as follows according to a flow of the process of the functional block shown in FIG. 3.
At first, the ideal reduction section 12 makes a reference to an ideal type table 35 of FIG. 5 in an ideal type classification section 31 of FIG. 3, retrieves a record in which the ideal type described in the ideal type field accords with the type of the input ideal J for obtaining a first record, and acquires a value N=61 of the ideal type number field and a value d=3 of the reduction order field of the first record. Next, the ideal reduction section 12 confirms that said value d=3 is not zero, makes a reference to a monomial list table 36 in a polynomial vector generation section 32, retrieves a record of which the value of the order field is said d=3 for obtaining a fourth record, and acquires a list 1, X, Y, X2, XY, Y2, and X3 of the monomial described in the monomial list field of the fourth record.
Furthermore, the ideal reduction section 12 acquires a first element f=28+132X+31Y+271X2+469XY+166Y2+X3, a second element g=856+618X+747Y+909X2+132XY+636Y2+X2Y, and a third element h=652+322X+240Y+978X2+826XY+846Y2+XY2 of J in the polynomial vector generation section 32, regards a coefficient list 0, 7, 0, 0, 0, 0, 0, 0, 0, 1, and 1 of the algebraic curve parameter file A as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, X3, X2Y, XY2, X4, and Y3 of the algebraic curve parameter file A, and generates a defining polynomial F=Y3+X4+7X.
Next, for each Mi(1<=i<=7) in said list 1, X, Y, X2, XY, Y2, and X3 of said monomial, the ideal reduction section 12 calculates a remainder equation ri of a product Mi·g of Mi and the polynomial g by the polynomials f and F in the polynomial vector generation section 32, arranges its coefficients in order of the monomial order 1, X, Y, . . . of the algebraic curve parameter file A, and generates a vector w(i)1. Furthermore, the ideal reduction section 12 calculates a remainder equation si of a product Mi·h of M and the polynomial h by the polynomials f and F, arranges its coefficient in order of the monomial order 1, X, Y, . . . of the algebraic curve parameter file A, and generates a vector w(i)2, and connects the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi.
That is, at first, for a first monomial M1=1, divide 1·g=856+618X+747Y+909X2+132XY+636Y2+X2Y by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then g=0·f+0·F+856+618X+747Y+909X2+132XY+636Y2+X2Y, whereby a remainder 856+618X+747Y+909X2+132XY+636Y2+X2Y is obtained to generate a vector w(i)=(856,618,747,909,132,636,1,0,0).
Also, divide 1·h=652+322X+240Y+978X2+826XY+846Y2+XY2 by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then h=0·f+0·F+652+322X+240Y+978X2+826XY+846Y2+XY2, whereby a remainder 652+322X+240Y+978X2+826XY+846Y2+XY2 is obtained to generate a vector w(i)2=(652,322,240,978,826,846,0,1,0). And, the vectors w(1)1 and w(1)2 are connected to obtain a vector v1=(856,618,747,909,132,636,1,0,0,652,322,240,978,826,846, 0,1,0).
Next, for a second monomial M2=X, divide Xg=X(856+618X+747Y+909X2+132XY+636Y2+X2Y) by f=28+132X+31Y+271X2+469XY+166Y2+X and F=Y3+X4+7X: then Xg=(319+166Y+Y)f+843F+149+667X+220X2+173Y+235XY+709X2Y+492Y2+863XY2, whereby a remainder 149+667X+220X2+173Y+235XY+709X2Y+492Y2+863XY2 is obtained to generate a vector w(2)1=(149,667,173,220,235,492,709,863,0).
Also, divide Xh=X(652+322X+240Y+978X2+826XY+846Y2+XY2) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: Xh=978f+0·F+868+708X+651X2+961Y+653XY+826X2Y+101Y2+846XY2+X2Y2, whereby a remainder 868+708X+651X2+961Y+653XY+826X2Y+101Y2+846XY2+X2Y2 is obtained to generate a vector w(2)2=(868,708,961,651,653,101,826,846,1). And, the vectors w(2)1 and w(2)2 are connected to obtain a vector v2=(149,667,173,220,235,492,709,863,0,868,708,961,651,653, 101,826,846,1).
Next, for a third monomial M3=Y, divide Yg=Y(856+618X+747Y+909X2+132XY+636Y2+X2Y) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: Yg=(826+373X) f+636F+79+179X+357X2+475Y+216XY+529X2Y+855Y2+772XY2+X2Y2, whereby a remainder 79+179X+357X2+475Y+216XY+529X2Y+855Y2+772XY2+X2Y2 is obtained to generate a vector w(3)1=(79,179,475,357,216,855,529,772,1).
Also, divide Yh=Y(652+322X+240Y+978X2+826XY+846Y2+XY2) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then Yh=(327+595X+1008X2+469Y)f+(685+X)F+934+966X+358X2+590Y+694XY+473X2Y+31Y2+939XY2+166X2Y2 whereby a remainder 934+966X+358X2+590Y+694XY+473X2Y+31Y2+939XY2+166X2Y2 is obtained to generate a vector w(3)2=(934,966,590,358,694,31,473,939,166). And, the vectors w(3)1 and w(3)2 are connected to obtain a vector v3=(79,179,475,357,216,855,529,772,1,934,966,590,358,694,3 1,473,939,166).
Next, for a fourth monomial M4=X2, divide X2g=X2(856+618X+747Y+909X2+132XY+636Y2+X2Y) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then X2g=(645+969X+166X2+709Y+XY)f+(359+843X)F+102+241X+394X2513Y+647XY+683X2Y+103Y2+1004XY2+863X2Y2, whereby a remainder 102+241X+394X2+513Y+647XY+683X2Y+103Y2+1004XY2+863X2Y2 is obtained to generate a vector w(4)1=(102,241,513,394,647,103,683,1004,863).
Also, divide X2h=X2(652+322X+240Y+978X2+826XY+846Y2+XY2) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then X2h=(725+16X+782X2+754Y+166XY+Y2)f+(930+227X+843Y)F+889+260X+560X2+809Y+425XY+552X2Y+535Y2+671XY2+763X2Y2, whereby a remainder 889+260X+560X2+809Y+425XY+552X2Y+535Y2+671XY2+763X2Y2 is obtained to generate a vector w(4)2=(889,260,809,560,425,535,552,671,763). And, the vectors w(4)1 and w(4)2 are connected to obtain a vector v4=(102,241,513,394,647,103,683,1004,863,889,260,809,560,425,535,552,671,763).
Next, for a fifth monomial M5=XY, divide XYg=XY(856+618X+747Y+909X2+132XY+636Y2+X2Y) by f=28+132X+31Y+271X2+469XY+166Y2+X and F=Y3+X4+7X: then XYg=(95+3X+146X2+457Y+166XY+Y2)f+(791+863X+843Y)F+367+X+54X2+403Y+361XY+276X2Y+305Y2+600XY2+689X2Y2, whereby a remainder 367+X+54X2+403Y+361XY+276X2Y+305Y2+600XY2+689X2Y2 is obtained to generate a vector w(5)1=(367,1,403,54,361,305,276,600,689).
Also, divide XYh=XY(652+322X+240Y+978X2+826XY+846Y2+XY2) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then XYh=(804+648X+246X2+1008X3+629Y+782XY+166Y2)f+(421+25X+X2+696Y)F+695+924X+28 9X2+851Y+210XY+321X2Y+802Y2+522XY2+278X2Y2, whereby a remainder 695+924X+289X2+851Y+210XY+321X2Y+802Y2+522XY2+278X2Y2 is obtained to generate a vector w(5)2=(695,924,851,289,210,802,321,522,278). And, the vectors w(5)1 and w(5)2 are connected to obtain a vector v5=(367,1,403,54,361,305,276,600,689,695,924,851,289,210, 802,321,522,278).
Next, for a sixth monomial M6=Y2, divide Y2g=Y2(856+618X+747Y+909X2+132XY+636Y2+X2Y) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then Y2g=(687+214X+320X2+1008X3+77Y+146XY+166Y2)f+(981+960X+X2+323Y)F+944+384X+956X2+763Y+737XY+925X2Y+859Y2+416XY2+814X2Y2, whereby a remainder 944+384X+956X2+763Y+737XY+925X2Y+859Y2+416XY2+814X2Y2 is obtained to generate a vector w(6)1=(944,384,763,956,737,859,925,416,814).
Also, divide Y2h=Y2(652+322X+240Y+978X2+826XY+846Y2+XY2) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then Y2h=(260+17X+731X2+843X3+382Y+246XY+1008X2Y+782Y2)f(369+868X+166X2+186Y+XY)F+792+963X+643X2+415Y+539XY+887X2Y+438Y2+102XY2+363X2Y2, whereby a remainder 792+963X+643X2+415Y+539XY+887X2Y+438Y2+102XY2+363X2Y2 is obtained to generate a vector w(6)2=(792,963,415,643,539,438,887,102,363). And, the vectors w(6)1 and w(6)2 are connected to obtain a vector v6=(944,384,763,956,737,859,925,416,814,792,963,415,643, 539,438,887,102,363).
Finally, for a seventh monomial M7=X3, divide X3g=X3(856+618X+747Y+909X2+132XY+636Y2+X2Y) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then X3g=(323+583X+814X2+166X3+96Y+689XY+X2Y+863Y2)f+(698+514X+843X2+20Y) F+37+730X+831X2+416Y+136XY+55X2Y+971Y2+398XY2+5X2Y2, whereby a remainder 37+730X+831X2+416Y+136XY+55X2Y+971Y2+398XY2+5X2Y2 is obtained to generate a vector w(7)1=(37,730,416,831,136,971,55,398,5).
Also, divide X3h=X3(652+322X+240Y+978X2+826XY+846Y2+XY2) by f=28+132X+31Y+271X2+469XY+166Y2+X3 and F=Y3+X4+7X: then X3h=(449+750X+363X2+782X3+102Y+278XY+166X2Y+763Y2+XY2)f+(784+583X+227X2+476Y+843XY)F+545+9X+173X2+378Y+902XY+16X2Y+831Y2+820XY2+909X2Y2, whereby a remainder 545+9X+173X2+378Y+902XY+16X2Y+831Y2+820XY2+909X2Y2 is obtained to generate a vector w(7)2=(545,9,378,173,902,831,16,820,909). And, the vectors w(7)1 and w(7)2 are connected to obtain a vector v7=(37,730,416,831,136,971,55,398,5,545,9,378,173,902,831, 16,820,909). Above, the process of the first ideal reduction section 12 in the polynomial vector generation section 32 is finished.
Next, in a basis construction section 33, the first ideal reduction section 12 inputs seven 18-dimensional vectors v1, v2, v3, v4, v5, v6, and v7, generated in the polynomial vector generation section 32 into a linear-relation derivation section 34, and obtains a plurality of seven-dimensional vectors m1, m2, . . . as an output. The linear-relation derivation section 34 derives a linear relation of the vectors, which were input, employing a discharging method. The discharging method belongs to a known art, whereby as to an operation of the linear-relation derivation section 34, only its outline is shown below.
The linear-relation derivation section 34 firstly arranges the seven 18-dimensional vectors v1, v2, v3, v4, v5, v6, and v7, which were input, in order for constructing a 7×18 matrix




  
    
      
        
          M
          R
        
        =
        
          (
          
            
              
                856
              
              
                618
              
              
                747
              
              
                909
              
              
                132
              
              
                636
              
              
                1
              
              
                0
              
              
                0
              
              
                652
              
              
                322
              
              
                240
              
              
                978
              
              
                826
              
              
                846
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                149
              
              
                667
              
              
                173
              
              
                220
              
              
                235
              
              
                492
              
              
                709
              
              
                863
              
              
                0
              
              
                868
              
              
                708
              
              
                961
              
              
                651
              
              
                653
              
              
                101
              
              
                826
              
              
                846
              
              
                1
              
            
            
              
                79
              
              
                179
              
              
                475
              
              
                357
              
              
                216
              
              
                855
              
              
                529
              
              
                772
              
              
                1
              
              
                934
              
              
                966
              
              
                590
              
              
                358
              
              
                694
              
              
                31
              
              
                473
              
              
                939
              
              
                166
              
            
            
              
                102
              
              
                241
              
              
                513
              
              
                394
              
              
                647
              
              
                103
              
              
                683
              
              
                1004
              
              
                863
              
              
                889
              
              
                260
              
              
                809
              
              
                560
              
              
                425
              
              
                535
              
              
                552
              
              
                671
              
              
                763
              
            
            
              
                367
              
              
                1
              
              
                403
              
              
                54
              
              
                361
              
              
                305
              
              
                276
              
              
                600
              
              
                689
              
              
                695
              
              
                924
              
              
                851
              
              
                289
              
              
                210
              
              
                802
              
              
                321
              
              
                522
              
              
                278
              
            
            
              
                944
              
              
                384
              
              
                763
              
              
                956
              
              
                737
              
              
                859
              
              
                925
              
              
                416
              
              
                814
              
              
                792
              
              
                963
              
              
                415
              
              
                643
              
              
                539
              
              
                438
              
              
                887
              
              
                102
              
              
                363
              
            
            
              
                37
              
              
                730
              
              
                416
              
              
                831
              
              
                136
              
              
                971
              
              
                55
              
              
                398
              
              
                5
              
              
                545
              
              
                9
              
              
                378
              
              
                173
              
              
                902
              
              
                831
              
              
                16
              
              
                820
              
              
                909
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          14
        
        ]
      
    
  




Next, the linear-relation derivation section 34 connects a seventh-dimensional unity matrix to the matrix MR to construct




  
    
      
        
          M
          R
          ′
        
        =
        
          (
          
            
              
                856
              
              
                618
              
              
                747
              
              
                909
              
              
                132
              
              
                636
              
              
                1
              
              
                0
              
              
                0
              
              
                652
              
              
                322
              
              
                240
              
              
                978
              
              
                826
              
              
                846
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                149
              
              
                667
              
              
                173
              
              
                220
              
              
                235
              
              
                492
              
              
                709
              
              
                863
              
              
                0
              
              
                868
              
              
                708
              
              
                961
              
              
                651
              
              
                653
              
              
                101
              
              
                826
              
              
                846
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                79
              
              
                179
              
              
                475
              
              
                357
              
              
                216
              
              
                855
              
              
                529
              
              
                772
              
              
                1
              
              
                934
              
              
                966
              
              
                590
              
              
                358
              
              
                694
              
              
                31
              
              
                473
              
              
                939
              
              
                166
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                102
              
              
                241
              
              
                513
              
              
                394
              
              
                647
              
              
                103
              
              
                683
              
              
                1004
              
              
                863
              
              
                889
              
              
                260
              
              
                809
              
              
                560
              
              
                425
              
              
                535
              
              
                552
              
              
                671
              
              
                763
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                367
              
              
                1
              
              
                403
              
              
                54
              
              
                361
              
              
                305
              
              
                276
              
              
                600
              
              
                689
              
              
                695
              
              
                924
              
              
                851
              
              
                289
              
              
                210
              
              
                802
              
              
                321
              
              
                522
              
              
                278
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                944
              
              
                384
              
              
                763
              
              
                956
              
              
                737
              
              
                859
              
              
                925
              
              
                416
              
              
                814
              
              
                792
              
              
                963
              
              
                415
              
              
                643
              
              
                539
              
              
                438
              
              
                887
              
              
                102
              
              
                363
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                37
              
              
                730
              
              
                416
              
              
                831
              
              
                136
              
              
                971
              
              
                55
              
              
                398
              
              
                5
              
              
                545
              
              
                9
              
              
                378
              
              
                173
              
              
                902
              
              
                831
              
              
                16
              
              
                820
              
              
                909
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          15
        
        ]
      
    
  




Next, the linear-relation derivation section 34 triangulates a matrix M′R by adding a constant multiple of an i-th row to an (i+1)-th row (i=1,2,and 3) to a seventh row to obtain the following matrix m.




  
    
      
        m
        =
        
          (
          
            
              
                856
              
              
                618
              
              
                747
              
              
                909
              
              
                132
              
              
                636
              
              
                1
              
              
                0
              
              
                0
              
              
                652
              
              
                322
              
              
                240
              
              
                978
              
              
                826
              
              
                846
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                62
              
              
                485
              
              
                393
              
              
                47
              
              
                320
              
              
                677
              
              
                863
              
              
                0
              
              
                184
              
              
                494
              
              
                344
              
              
                634
              
              
                455
              
              
                272
              
              
                826
              
              
                814
              
              
                1
              
              
                977
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                252
              
              
                630
              
              
                861
              
              
                845
              
              
                645
              
              
                389
              
              
                1
              
              
                380
              
              
                422
              
              
                1006
              
              
                632
              
              
                736
              
              
                748
              
              
                221
              
              
                979
              
              
                217
              
              
                281
              
              
                51
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                982
              
              
                226
              
              
                146
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                449
              
              
                79
              
              
                320
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                544
              
              
                564
              
              
                195
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                79
              
              
                930
              
              
                1004
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          16
        
        ]
      
    
  




As well known, the vector that is composed of a nineteenth component and afterward of a fourth row to a seventh row of the matrix m is a vector {(m1,1,m1,2, . . . ,m1,7), (m2,1,m2,2, . . . ,m2,7), . . . } representing a linearly-independent linear dependence relation Σi7mjivi=0(j=1,2 . . . ) of all of the seven 18-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 that were input. The linear-relation derivation section 34 outputs a vector m1=(982,226,146,1,0,0,0) that is composed of the nineteenth component and afterward of the fourth row of the matrix m, a vector m2=(449,79,320,0,1,0,0) that is composed of the nineteenth component and afterward of the fifth row of the matrix m, and a vector m3=(544,564,195,0,0,1,0) that is composed of the nineteenth component and afterward of the sixth row of the matrix m, and a vector m4=(79,930,1004,0,0,0,1) that is composed of the nineteenth component and afterward of the seventh row of the matrix m.
Now return to the explanation of the process of the first ideal reduction section 12 in the basis construction section 33. Next, this ideal reduction section 12 makes a reference to a table 37 for a Groebner basis construction of FIG. 7, and retrieves a record, of which the value of the order field is said value d=3, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(982,226,146,1,0,0,0), m2=(449,79,320,0,1,0,0), m3=(544,564,195,0,0,1,0), and m4=(79,930,1004,0,0,0,1). The value of the order field of a fourteenth record is 3, and a vector, of which the components that correspond to the component number lists 4, 5, 6, and 7 of the fourteenth record are all zero, does not lie in the vectors m1, m2, m3, and m4, whereby the fourteenth record is obtained as a retrieval result.
Furthermore, the value of the first vector type of the fourteenth record is (*,*,*,1,0,0,0)(A code * is interpreted as representing any number), which coincides with the vector m1=(982,226,146,1,0,0,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, and X3 of the algebraic curve parameter file A to generate a polynomial f1=982+226X+146Y+X2.
Similarly, the value of the second vector type of the fourteenth record is (*,*,*,0,1,0,0) (A code * is interpreted as representing any number), which coincides with the vector m2=(449,79,320,0,1,0,0), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, and X3 of the algebraic curve parameter file A to generate a polynomial f2=449+79X+320Y+XY.
Similarly, the value of the third vector type of the fourteen record is (*,*,*,0,0,1,0)(A code * is interpreted as representing any number), which coincides with the vector m3=(544,564,195,0,0,1,0), whereby the vector m3 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, and X3 of the algebraic curve parameter file A to generate a polynomial f3=544+564X+195Y+Y2.
Finally, the ideal reduction section 12 constructs a set J*={f1=982+226X+146Y+X2,f2=449+79X+320Y+XY, f3=544+564X+195Y+Y2} of the polynomial to output it. Above, the operation of the first ideal reduction section 12 is finished.
Next, a second ideal reduction section 13, which takes as an input the algebraic curve parameter file A 30 of FIG. 4, and the Groebner basis J*={982+226X+146Y+X2,449+79X+320Y+XY,544+564X+195Y2} that the first ideal reduction section 12 output, operates as follows according to a flow of the process of the functional block shown in FIG. 3. At first, in the ideal type classification section 31 of FIG. 3, the second ideal reduction section 13 makes a reference to the ideal type table 35 of FIG. 5, retrieves a record in which the ideal type described in the ideal type field accords with the type of the input ideal J* for obtaining a fourteenth record, and acquires a value N=31 of the ideal type number field and a value d=3 of the reduction order field of the fourteenth record.
Next, the ideal reduction section 13 confirms that said value d=3 is not zero, makes a reference to the monomial list table 36 in the polynomial vector generation section 32, retrieves a record of which the value of the order field is said d=3 for obtaining a fourth record, and acquires a list 1, X, Y, X2, XY, Y2, and X3 of the monomial described in the monomial list field of the fourth record.
Furthermore, the ideal reduction section 13 acquires a first element f=982+226X+146Y+X2, a second element g=449+79X+320Y+XY, and a third element h=544+564X+195Y+Y2 of J*, regards a coefficient list 0,7,0,0,0,0,0,0,0,1,1 of the algebraic curve parameter file A as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, X3, X2Y, XY2, X4, and Y3 of the algebraic curve parameter file A, and generates a defining polynomial F=Y3+X4+7X.
Next, for each of Mi(1<=i<=7) in said list 1, X, Y, X2, XY, Y2, and X3 of said monomial, the ideal reduction section 13 calculates a remainder equation ri of a product Mi·g of Mi and the polynomial g by the polynomials f and F, arranges its coefficients in order of the monomial order 1, X, Y, . . . of the algebraic curve parameter file A, and generates a vector w(i)1. Furthermore, the ideal reduction section 13 calculates a remainder equation si of a product Mi·h of Mi and the polynomial h by the polynomials f and F, arranges its coefficients in order of the monomial order 1, X, Y, . . . of the algebraic curve parameter file A, and generates a vector w(i)2, and connects the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi.
That is, at first, for a first monomial M1=1, divide 1·g=449+79X+320Y+XY by f=982+226X+146Y+X2 and F=Y3+X4+7X, :then g=0·f+0·F+449+79X+320Y+XY, whereby a remainder 449+79X+320Y+XY is obtained to generate a vector w(1)1=(449,79,320,1,0,0). Also, divide 1·h=544+564X+195Y+Y2 by f=982+226X+146Y+X2 and F=Y3+X4+7X: then h=0·f+0·F+544+564X+195Y+Y2, whereby a remainder 544+564X+195Y+Y2 is obtained to generate a vector w(1)2=(544,564,195,0,1,0). And, the vectors w(1)1 and w(1)2 are connected to obtain a vector v1=(449,79,320,1,0,0,544,564,195,0,1,0).
Next, for a second monomial M2=X, divide Xg=X(449+79X+320Y+XY) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then Xg=(79+Y)f+0·F+115+757X+601Y+94XY+863Y2, whereby a remainder 115+757X+601Y+94XY+863Y2 is obtained to generate a vector w(2)1=(115,757,601,94,863,0).
Also, divide Xh=X(544+564X+195Y+Y2) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then Xh=564f+0·F+93+214X+394Y+195XY+XY , whereby a remainder 93+214X+394Y+195XY+XY2 is obtained to generate a vector w(2)2=(93,214,394,195,0,1). And, the vectors w(2)1 and w(2)2 are connected to obtain a vector v2=(115,757,601,94,863,0,93,214,394,195,0,1).
Next, for a third monomial M3=Y, divide Yg=Y(449+79X+320Y+XY) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then Yg=0·f+0·F+449Y+79XY+320Y2+XY2, whereby a remainder 449Y+79XY+320Y2+XY2 is obtained to generate a vector w(3)1=(0,0,449,79,320,1).
Also, divide Yh=Y(544+564X+195Y+Y2) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then Yh=(356+226X+1008X2+146Y)f+1·F+531+305X+942Y+157XY+68Y2, whereby a remainder 531+305X+942Y+157XY+68Y2 is obtained to generate a vector w(3)2=(531,305,942,157,68,0). And, the vectors w(3)1 and w(3)2 are connected to obtain a vector v3=(0,0,449,79,320,1,531,305,942,157,68,0).
Next, for a fourth monomial M4=X2, divide X2g=X2(449+79X+320Y+XY) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then X2g=(757+79X+94Y+XY)f+0·F+259+563X+988Y+546XY+402Y2+863XY2, whereby a remainder 259+563X+988Y+546XY+402Y2+863XY2 is obtained to generate a vector w(4)1=(259,563,988,546,402,863).
Also, divide X2h=X2 (544+564X+195Y+Y2) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then X2h=(706+865X+146X2+68Y+Y2)f+863F+900+27X+669Y+611XY+189Y2+783XY2, whereby a remainder 900+27X+669Y+611XY+189Y2+783XY2 is obtained to generate a vector w(4)2=(900,27,669,611,189,783). And, the vectors w(4)1 and w(4)2 are connected to obtain a vector v4=(259,563,988,546,402,863,900,27,669,611,189,783).
Next, for a fifth monomial M5=XY, divide XYg=XY(449+79X+320Y+XY) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then XYg=(492+301X+146X2+961Y+Y2) f+863F+167+875X+529Y+648XY+981Y2+94XY2 whereby a remainder 167+875X+529Y+648XY+981Y2+94XY2 is obtained to generate a vector w(5)1=(167,875,529,648,981,94). Also, divide XYh=XY(544+564X+195Y+Y2) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then XYh=(305+356X+226X2+1008X3+157Y+146XY)f+XF+163+213X+213X+69Y+775XY+285Y2+68XY2, whereby a remainder 163+213X+69Y+775XY+285Y2+68XY2 is obtained to generate a vector w(5)2=(163,213,69,775,285,68). And, the vectors w(5)1 and w(5)2 are connected to obtain a vector v5=(167,875,529,648,981,94,163,213,69,775,285,68).
Next, for a sixth monomial M6=Y2, divide Y2g=Y2(449+79X+320Y+XY) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then Y2g=(208+28X+915X2+1008X3+908Y+146XY)f+(320+X)F+571+949X+202Y+482XY+60Y2+961XY2, whereby a remainder 571+949X+202Y+482XY+60Y2+961XY2 is obtained to generate a vector w(6)1=(571,949,202,482,60,961).
Also, divide Y2h=Y2 (544+564X+195Y+Y2) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then Y2h=(1001+233X+941X2+194Y+226XY+1008X2Y+146Y2)f+(68+Y)F+793+560X+352Y+881XY+378Y2+157XY2, whereby a remainder 793+560X+352Y+881XY+378Y2+157XY2 is obtained to generate a vector w(6)2=(793,560,352,881,378,157). And, the vectors w(6)1 and w(6)2 are connected to obtain a vector v6=(571,949,202,482,60,961,793,560,352,881,378,157).
Finally, for a seventh monomial M7=X3, divide X3g=X3(449+79X+320Y+XY) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then X3g=(370+198X+961X2+926Y+94XY+X2Y+863Y2) f+127F+909+548X+243Y+460XY+104Y2+101XY2, whereby a remainder 909+548X+243Y+460XY+104Y2+101XY2 is obtained to generate a vector w(7)1=(909,548,243,460,104,101).
Also, divide X3h=X3 (544+564X+195Y+Y2) by f=982+226X+146Y+X2 and F=Y3+X4+7X: then X3h=(834+283X+157X2+146X3+52Y+68XY+783Y2+XY2)f+(708+863X)F+320+866X+720Y+225XY+432Y2+815XY2, whereby a remainder 320+866X+720Y+225XY+432Y2+815XY2 is obtained to generate a vector w(7)2=(320,866,720,225,432,815). And, the vectors w(7)1 and w(7)2 are connected to obtain a vector v7=(909,548,243,460,104,101,320,866,720,225,432,815). Above, the process of the second ideal reduction section 13 reduction section 13 in the polynomial vector generation section 32 is finished.
Next, in the basis construction section 33, the second ideal reduction section 13 inputs seven 12-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 generated in the polynomial vector generation section 32 into the linear-relation derivation section 34, and obtains a plurality of seven-dimensional vectors m1,m2, . . . as an output. The linear-relation derivation section 34 derives a linear relation of the vectors, which were input, employing a discharging method. The discharging method belongs to a known art, whereby as to an operation of the linear-relation derivation section 34, only its outline is shown below.
The linear-relation derivation section 34 firstly arranges the seven 12-dimensional vectors v1, v2, v3, v4, v5, v6, and v7, which were input, in order for constructing a 7×12 matrix



  
    
      
    
    ⁢
    
      [
      
        EQ
        .
        
          
        
        ⁢
        17
      
      ]
    
  




  
    
      M
      R
    
    =
    
      (
      
        
          
            449
          
          
            79
          
          
            320
          
          
            1
          
          
            0
          
          
            0
          
          
            544
          
          
            564
          
          
            195
          
          
            0
          
          
            1
          
          
            0
          
        
        
          
            115
          
          
            757
          
          
            601
          
          
            94
          
          
            863
          
          
            0
          
          
            93
          
          
            214
          
          
            394
          
          
            195
          
          
            0
          
          
            1
          
        
        
          
            0
          
          
            0
          
          
            449
          
          
            79
          
          
            320
          
          
            1
          
          
            531
          
          
            305
          
          
            942
          
          
            157
          
          
            68
          
          
            0
          
        
        
          
            259
          
          
            563
          
          
            988
          
          
            546
          
          
            402
          
          
            863
          
          
            900
          
          
            27
          
          
            669
          
          
            611
          
          
            189
          
          
            783
          
        
        
          
            167
          
          
            875
          
          
            529
          
          
            648
          
          
            981
          
          
            94
          
          
            163
          
          
            213
          
          
            69
          
          
            775
          
          
            285
          
          
            68
          
        
        
          
            571
          
          
            949
          
          
            202
          
          
            482
          
          
            60
          
          
            961
          
          
            793
          
          
            560
          
          
            352
          
          
            881
          
          
            378
          
          
            157
          
        
        
          
            909
          
          
            548
          
          
            243
          
          
            460
          
          
            104
          
          
            101
          
          
            320
          
          
            866
          
          
            720
          
          
            225
          
          
            432
          
          
            815
          
        
      
      )
    
  



Next, the linear-relation derivation section 34 connects a seventh-dimensional unity matrix to the matrix MR to construct




  
    
      
        
          M
          R
          ′
        
        =
        
          (
          
            
              
                449
              
              
                79
              
              
                320
              
              
                1
              
              
                0
              
              
                0
              
              
                544
              
              
                564
              
              
                195
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                115
              
              
                757
              
              
                601
              
              
                94
              
              
                863
              
              
                0
              
              
                93
              
              
                214
              
              
                394
              
              
                195
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                449
              
              
                79
              
              
                320
              
              
                1
              
              
                531
              
              
                305
              
              
                942
              
              
                157
              
              
                68
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                259
              
              
                563
              
              
                988
              
              
                546
              
              
                402
              
              
                863
              
              
                900
              
              
                27
              
              
                669
              
              
                611
              
              
                189
              
              
                783
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                167
              
              
                875
              
              
                529
              
              
                648
              
              
                981
              
              
                94
              
              
                163
              
              
                213
              
              
                69
              
              
                775
              
              
                285
              
              
                68
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                571
              
              
                949
              
              
                202
              
              
                482
              
              
                60
              
              
                961
              
              
                793
              
              
                560
              
              
                352
              
              
                881
              
              
                378
              
              
                157
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                909
              
              
                548
              
              
                243
              
              
                460
              
              
                104
              
              
                101
              
              
                320
              
              
                866
              
              
                720
              
              
                225
              
              
                432
              
              
                815
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          18
        
        ]
      
    
  




Next, the linear-relation derivation section 34 triangulates a matrix M′R by adding a constant multiple of an i-th row to an (i+1)-th row (i=1, 2, and 3) to a seventh row to obtain the following a matrix m.




  
    
      
        m
        =
        
          (
          
            
              
                449
              
              
                79
              
              
                320
              
              
                1
              
              
                0
              
              
                0
              
              
                544
              
              
                564
              
              
                195
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                548
              
              
                955
              
              
                896
              
              
                863
              
              
                0
              
              
                493
              
              
                510
              
              
                389
              
              
                195
              
              
                802
              
              
                1
              
              
                802
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                449
              
              
                79
              
              
                320
              
              
                1
              
              
                531
              
              
                305
              
              
                942
              
              
                157
              
              
                68
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                982
              
              
                226
              
              
                146
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                53
              
              
                941
              
              
                915
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                394
              
              
                852
              
              
                48
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                382
              
              
                194
              
              
                908
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          19
        
        ]
      
    
  




As well known, the vector that is composed of a thirteenth component and afterward of a fourth row to a seventh row of the matrix m is a vector {(m1,1,m1,2, . . . ,m1,n), (m2,1,m2,2, . . . ,m2,n), . . . } representing a linearly-independent linear dependence relation Σi7mjivi=0(j=1,2, . . . ) of all of the seven 12-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 that were input. The linear-relation derivation section 34 outputs a vector m1=(982,226,146,1,0,0,0) that is composed of the thirteenth component and afterward of the fourth row of the matrix m, a vector m2=(53,941,915,0,1,0,0) that is composed of the thirteenth component and afterward of the fifth row of the matrix m, and a vector m3=(394,852,48,0,0,1,0) that is composed of the thirteenth component and afterward of the sixth row of the matrix m, and a vector m4=(382,194,908,0,0,0,1) that is composed of the thirteenth component and afterward of the seventh row of the matrix m.
Now return to the explanation of the process of the second ideal reduction section 13 in the basis construction section 33. Next, the second ideal reduction section 13 makes a reference to a table 37 for a Groebner basis construction of FIG. 7, and retrieves a record, of which the value of the order field is said value d=3, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(982,226,146,1,0,0,0), m2=(53,941,915,0,1,0,0), m3=(394,852,48,0,0,1,0), and m4=(382,194,908,0,0,0,1). The value of the order field of a fourteenth record is 3, and a vector, of which the component that correspond to the component number lists 4, 5, 6, and 7 of the fourteenth record are all zero, does not lie in the vectors m1, m2, m3, and m4, whereby the fourteenth record is obtained as a retrieval result.
Furthermore, the value of the first vector type of the fourteenth record is (*,*,*,1,0,0,0)(A code * is interpreted as representing any number), which coincides with the vector m1=(982,226,146,1,0,0,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, and X3 of the algebraic curve parameter file A to generate a polynomial f1=982+226X+146Y+X2.
Similarly, the value of the second vector type of the fourteenth record is (*,*,*,0,1,0,0) (A code * is interpreted as representing any number), which coincides with the vector m2=(53,941,915,0,1,0,0), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, and X3 of the algebraic curve parameter file A to generate a polynomial f2=53+941X+915Y+XY.
Similarly, the value of the third vector type of the fourteen record is (*,*,*,0,0,1,0) (A code * is interpreted as representing any number), which coincides with the vector m3=(394,852,48,0,0,1,0), whereby the vector m3 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, Y, X2, XY, Y2, and X3 of the algebraic curve parameter file A to generate a polynomial f3=394+852X+48Y+Y2. Finally, the ideal reduction section 13 constructs a set J**={f1=982+226X+146Y+X2, f2=53+941X+915Y+XY,f3=394+852X+48Y+Y2} of the polynomial output it. Above, the operation of the second ideal reduction section 13 is finished.
Finally, in the Jacobian group element adder of FIG. 1, the Groebner basis J**={982+226X+146Y+X2, 53+941X+915Y+XY,394+852X+48Y+Y2}, which the second ideal reduction section 13 output, is output from an output apparatus.
Next, the embodiment of the case will be shown in which the C27 curve was employed. In this embodiment, the algebraic curve parameter file of FIG. 8 is employed as an algebraic curve parameter file, the ideal type table of FIG. 9 as an ideal type table, the monomial list table of FIG. 10 as an monomial list table, and the table for a Groebner basis construction of FIG. 11 as a table for a Groebner basis construction respectively.
In the Jacobian group element adder of FIG. 1, suppose Groebner bases

I1={689+623X+130X2+X3,568+590X+971X2+Y}

and

I2={689+623X+130X2+X3, 568+590X+971X2+Y}

were input of the ideal of the coordinate ring of the algebraic curve designated by the algebraic curve parameter file A, which represents an element of the Jacobian group of the C27 curve designated by the algebraic curve parameter file A 16 and the algebraic curve parameter file A of FIG. 8.

At first, an ideal composition section 11, which takes the algebraic curve parameter file A of FIG. 8, and the above-mentioned Groebner bases I1 and I2 as an input, operates as follows according to a flow of the process of the functional block shown in FIG. 2. At first, the ideal composition section 11 makes a reference to the ideal type table of FIG. 9 in the ideal type classification section 21 of FIG. 2, retrieves a record in which the ideal type described in the ideal type field accords with the type of the input ideal I1 for obtaining an eleventh record, and acquires a value N1=31 of the ideal type number field and a value d1=3 of the order field of the eleventh record. Similarly, the ideal composition section 11 retrieves a record in which the ideal type accords with the type of the input ideal I2 for obtaining the eleventh record, and acquires a value N2=31 of the ideal type number field and a value d2=3 of the order field of the eleventh record.
Next, the ideal composition section 11 calculates the sum d3=d1+d2=6 of said values d1=3 and d2=3 of said order field in the monomial vector generation section 22, makes a reference to the monomial list table, retrieves a record of which the value of the order field is said d3=6 for obtaining a first record, and acquires a list 1, X, X2, X3, Y, X4, XY, X5, X2Y, and X6 of the monomial described in the monomial list field of the first record. I1 and I2 are equivalent, whereby a remainder to be attained by dividing Mi by I1 for each of Mi(1<=i<=10) in said list 1, X, X2, X3, Y, X4, XY, X5, X2Y, and X6 of said monomial is calculated to obtain a polynomial a(i)1+a(i)2X+a(i)3X2, to arrange its coefficients in order of the monomial order 1, X, X2, . . . of the algebraic curve parameter file A, and to generate a vector w(i)1=(a(i)1,a(i)2,a(i)3).
Furthermore, the ideal composition section 11 regards a coefficient list 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, and 1 described in the algebraic curve parameter file A of FIG. 8 as a coefficient row of each monomial of the monomial order 1, X, X2, X3, Y, X4, XY, X5, X2Y, X6, X3Y, X7, and Y2 described in the algebraic curve parameter file A of FIG. 8, constructs a defining polynomial F=Y2+X7+7X, when a differential of a polynomial M with respect to its X is expressed by DX(M), and a differential of a polynomial M with respect to its Y is expressed by DY(M), calculates a remainder to be attained by dividing a polynomial DX(Mi)DY(F)−DY(Mi)DX(F) by I1, obtains a polynomial b(i)1+b(i)2X+b(i)3X2, arranges its coefficients in order of the monomial order 1, X, X2, . . . of the algebraic curve parameter file A, generates a vector w(i)2=(b(i)1,b(i)2,b(i)3), and connect the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi=(a(i)1,a(i)2,a(i)3,b(i)1,b(i)2,b(i)3). That is, divide M1=1 by I1: then

1=0·(689+623X+130X2+X3)+0·(568+590X+971X2+Y)+1,

whereby, 1 is obtained as a remainder to generate a vector w(1)1=(1,0,0). Furthermore, divide DX(1)DY(F)−DY(1)DX(F)=0 by I1: then 0, whereby 0 is obtained as a remainder to generate a vector w(1)2=(0,0,0). w(1)1 and w(1)2 are connected to generate a vector v1=(1,0,0,0,0,0).

Next, divide M2=X by I1: then X=0·(689+623X+130X2+X3)+0·(568+590X+971X2+Y)+X, whereby, X is obtained as a remainder to generate a vector w(2)1=(0,1,0). Furthermore, divide DX(X)DY(F)−DY(X)DX(F)=DY(F)=2Y by I1: then 2Y=0·(689+623X+130X2+X3)+2(568+590X+971X2+Y)+882+838X+76X2,
whereby 882+838X+76X2 is obtained as a remainder to generate a vector w(2)2=(882,838,76). w(2)1 and w(2)2 are connected to generate a vector v2=(0,1,0,882,838,76)
Next, divide M3=X2 by I1: then X2=0·(689+623X+130X2+X3)+0·(568+590X+971X2+Y)+X2, whereby, X2 is obtained as a remainder to generate a vector w(3)1=(0,0,1). Furthermore, divide DX(X2)DY(F)−DY(X2)DX(F)=4XY by I1: then 4XY=152(689+623X+130X2+X3)+4X(568+590X+971X2+Y)+208+905X+78X2, whereby 208+905X+78X2 is obtained as a remainder to generate a vector w(3)2=(208,905,78). w(3)1 and w(3)2 are connected to generate a vector v3=(0,0,1,208,905,78).
Next, divide M4=X3 by I1: then X3=1·(689+623X+130X2+X3)+0·(568+590X+971X2+Y)+320+386X+879X2, whereby, 320+386X+879X2 is obtained as a remainder to generate a vector w(4)1=(320,386,879). Furthermore, divide DX(X3)DY(F)−DY(X3)DX(F)=6X2Y by I1: then 6X2Y=(117+228X)(689+623X+130X2+X3)+6X2(568+590X+971X2+Y)+107+69X+778X2, whereby 107+69X+778X2 is obtained as a remainder to generate a vector w(4)2=(107,69,778). w(4)1 and w(4)2 are connected to generate a vector v4=(320,386,879,107,69,778).
Next, divide M5=Y by I1: then Y=0·(689+623X+130X2+X3)+1·(568+590X+971X2+Y)+441+419X+38X2, whereby, 441+419X+38X2 is obtained as a remainder to generate a vector w(5)1=(441,419,38). Furthermore, divide DX(Y)DY(F)−DY(Y)DX(F)=−DX(F)=1002+1002X6 by I1, then 1002+1002X6=(865+78X+910X2+1002X3)(689+623X+130X2+X3)+0·(568+590X+971X2+Y)+327+655X+1004X2, whereby 327+655X+1004X2 is obtained as a remainder to generate a vector w(5)2=(327,655,1004). w(5)1 and w(5)2 are connected to generate a vector v5=(441,419,38,327,655,1004).
Next, divide M6=X4 by I1: then X4=(879+X)(689+623X+130X2+X3)+0·(568+590X+971X2+Y)+778+590X+133X2, whereby, 778+590X+133X2 is obtained as a remainder to generate a vector w(6)1=(778,590,133). Furthermore, divide DX(X4)DY(F)−DY(X4) DX(F)=8X3Y by I1: then 8X3Y=(200+840X+8Y)(689+623X+130X2+X3)+(542+61X+978X2) (568+590X+971X2+Y)+322+653X+781X2, whereby 322+653X+781X2 is obtained as a remainder to generate a vector w(6)2=(322,653,781). w(6)1 and w(6)2 are connected to generate a vector v6=(778,590,133,322,653,781).
Next, divide M7=XY by I1: then XY=38(689+623X+130X2+X3)+X(568+590X+971X2+Y)+52+983X+524X2, whereby, 52+983X+524X2 is obtained as a remainder to generate a vector w(7)1=(52,983,524). Furthermore, divide DX(XY)DY(F)−DY(XY)DX(F)=1002X+1002X7+2Y2 by I1, then 1002X+1002X7+2Y2=(24+726X+78X2+910X3+1002X4) (689+623X+130X2+X3)+(882+838X+76X2+2Y)(568+590X+971X2+Y)+105+954X+813X2, whereby 105+954X+813X2 is obtained as a remainder to generate a vector w(7)2=(105,954,813). w(7)1 and w(7)2 are connected to generate a vector v7=(52,983,524,105,954,813).
Next, divide M8=X5 by I1: then X5=(133+879X+X2)(689+623X+130X2+X3)+0·(568+590X+971X2+Y)+182+657X+453X2, whereby, 182+657X+453X2 is obtained as a remainder to generate a vector w(8)1=(182,657,453). Furthermore, divide DX(X5)DY(F)−DY(X5)DX(F)=10X4Y by I1: then 10X4Y=(912+90X+718Y+10XY)(689+623X+130X2+X3)+(717+855X+321X2)(568+590X+971X2+Y)+619+878X+281X2, whereby 619+878X+281X2 is obtained as a remainder to generate a vector w(8)2=(619,878,281). w(8)1 and w(8)2 are connected to generate a vector v8=(182,657,453,619,878,281).
Next, divide M9=X2Y by I1: then X2Y=(524+38X)(689+623X+130X2+X3)+X2 (568+590X+971X2+Y)+186+516X+466X2, whereby, 186+516X+466X2 is obtained as a remainder to generate a vector w(9)1=(186,516,466) Furthermore, divide DX(X2Y)DY(F)−DY(X2Y)DX(F)=1002X2+1002X8+4XY2 by I1: then 1002X2+1002X8+4XY2=(892+941X+865X2+78X3+910X4+1002X5+152Y) (689+623X+130X2+X3)+(208+905X+78X2+4XY)(568+590X+971X2+Y)+811+600X+123X2, whereby 811+600X+123X2 is obtained as a remainder to generate a vector w(9)2=(811,600,123). w(9)1 and w(9)2 are connected to generate a vector v9=(186,516,466,811,600,123).
Next, divide M10=X6 by I1: then X6=(453+133X+879X2+X3)(689+623X+130X2+X3)+0·(568+590X+971X2+Y)+673+483X+289X2, whereby, 673+483X+289X2 is obtained as a remainder to generate a vector w(10)1=(673,483,289). Furthermore, divide DX(X6)DY(F)−DY(X6)DX(F)=12X5Y by I1: then 12X5Y=(985+732X+587Y+458XY+12X2Y)(689+623X+130X2+X3)+(166+821X+391X2)(568+590X+971X2+Y)+950+741X+201X2, whereby 950+741X+201X2 is obtained as a remainder to generate a vector w(10)2=(950,741,201). w(10)1 and w(10)2 are connected to generate a vector v10=(673,483,289,950,741,201). Above, the process of the ideal composition section 11 in the monomial vector generation section 22 is finished.
Next, in the basis construction section 23, the ideal composition section 11 inputs ten six-dimensional vectors v1, v2, v3, v4, v5, v6, v7, v6, v9, and, v10 generated in the monomial vector generation section 22 into the linear-relation derivation section 24, and obtains a plurality of 10-dimensional vectors m1,m2, . . . as an output. The linear-relation derivation section 24 derives a linear relation of the vectors, which were input, employing the discharging method. The discharging method belongs to a known art, whereby, as to an operation of the linear-relation derivation section 24, only its outline is shown below. The linear-relation derivation section 24 firstly arranges the ten six-dimensional vectors v1, v2, v3, v4, v5, v6, v7, v8, v9, and, v10 which were input, in order for constructing a 10×6 matrix




  
    
      
        
          M
          C
        
        =
        
          (
          
            
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                1
              
              
                0
              
              
                882
              
              
                838
              
              
                76
              
            
            
              
                0
              
              
                0
              
              
                1
              
              
                208
              
              
                905
              
              
                78
              
            
            
              
                320
              
              
                386
              
              
                879
              
              
                107
              
              
                69
              
              
                778
              
            
            
              
                441
              
              
                419
              
              
                38
              
              
                327
              
              
                655
              
              
                1004
              
            
            
              
                778
              
              
                590
              
              
                133
              
              
                322
              
              
                653
              
              
                781
              
            
            
              
                52
              
              
                983
              
              
                524
              
              
                105
              
              
                954
              
              
                813
              
            
            
              
                182
              
              
                657
              
              
                453
              
              
                619
              
              
                878
              
              
                281
              
            
            
              
                186
              
              
                516
              
              
                466
              
              
                811
              
              
                600
              
              
                123
              
            
            
              
                673
              
              
                483
              
              
                289
              
              
                950
              
              
                741
              
              
                201
              
            
          
          )
        
      
    
    
      
        [
        
          E
          ⁢
          
            
          
          ⁢
          
            Q
            .
            
              
            
            ⁢
            20
          
        
        ]
      
    
  




Next, the linear-relation derivation section 24 connects a 10-dimensional unity matrix to the matrix MC to obtain



  
    
      
    
    ⁢
    
      [
      
        E
        ⁢
        
          
        
        ⁢
        
          Q
          .
          
            
          
          ⁢
          21
        
      
      ]
    
  




  
    
      M
      C
      ′
    
    =
    
      (
      
        
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            1
          
          
            0
          
          
            882
          
          
            838
          
          
            76
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            208
          
          
            905
          
          
            78
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            320
          
          
            386
          
          
            879
          
          
            107
          
          
            69
          
          
            778
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            441
          
          
            419
          
          
            38
          
          
            327
          
          
            655
          
          
            1004
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            778
          
          
            590
          
          
            133
          
          
            322
          
          
            653
          
          
            781
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            52
          
          
            983
          
          
            524
          
          
            105
          
          
            954
          
          
            813
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            182
          
          
            657
          
          
            453
          
          
            619
          
          
            878
          
          
            281
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
        
        
          
            186
          
          
            516
          
          
            466
          
          
            811
          
          
            600
          
          
            123
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
        
        
          
            673
          
          
            483
          
          
            289
          
          
            950
          
          
            741
          
          
            201
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
        
      
      )
    
  



Next, the linear-relation derivation section 24 triangulates a matrix M′C by adding a constant multiple of an i-th row to an (i+1)-th row (i=1,2, . . . , 6) to a tenth row to obtain the following a matrix m.



  
    
      
    
    ⁢
    
      [
      
        EQ
        .
        
          
        
        ⁢
        22
      
      ]
    
  




  
    
      
    
    ⁢
    
      m
      =
      
        (
        
          
            
              1
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              1
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              1
            
            
              0
            
            
              882
            
            
              838
            
            
              76
            
            
              0
            
            
              1
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              1
            
            
              208
            
            
              905
            
            
              78
            
            
              0
            
            
              0
            
            
              1
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              494
            
            
              87
            
            
              753
            
            
              689
            
            
              623
            
            
              130
            
            
              1
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              477
            
            
              924
            
            
              591
            
            
              170
            
            
              804
            
            
              22
            
            
              1
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              475
            
            
              742
            
            
              22
            
            
              242
            
            
              149
            
            
              314
            
            
              1
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              699
            
            
              601
            
            
              688
            
            
              281
            
            
              217
            
            
              287
            
            
              1
            
            
              0
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              193
            
            
              959
            
            
              364
            
            
              180
            
            
              550
            
            
              43
            
            
              0
            
            
              1
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              780
            
            
              667
            
            
              96
            
            
              50
            
            
              897
            
            
              327
            
            
              0
            
            
              0
            
            
              1
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              0
            
            
              761
            
            
              727
            
            
              417
            
            
              523
            
            
              278
            
            
              912
            
            
              0
            
            
              0
            
            
              0
            
            
              1
            
          
        
        ⁢
        
          
        
        )
      
    
  



As well known, the vector that is composed of a seventh component and afterward of a seventh row to a tenth row of the matrix m is a vector {(m1,1,m1,2, . . . ,m1,n), m2,1,m2,2, . . . ,m2,n), . . . } representing a linearly-independent linear dependence relation Σi10mjivi=0(j=1,2, . . . ) of all of the ten six-dimensional vectors v1, v2, v3, v4, v5, v6, v7, v8, v9, and, v10 that were input. The linear-relation derivation section 24 outputs a vector m1=(699,601,688,281,217,287,1,0,0,0) that is composed of the seventh component and afterward of the seventh row of the matrix m, a vector m2=(193,959,364,180,550,43,0,1,0,0) that is composed of the seventh component and afterward of the eighth row of the matrix m, and a vector m3=(780,667,96,50,897,327,0,0,1,0) that is composed of the seventh component and afterward of the ninth row of the matrix m, and a vector m4=(761,727,417,523,278,912,0,0,0,1) that is composed of the seventh component and afterward of the tenth row of the matrix m. Now return to the explanation of the process of the ideal composition section 11 in the basis construction section 23.
Next, the ideal composition section 11 makes a reference to the table for a Groebner basis construction of FIG. 11, and retrieves a record, of which the value of the order field is said value d3=6, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(699,601,688,281,217,287,1,0,0,0), m2=(193,959,364,180,550,43,0,1,0,0), m3=(780,667,96,50,897,327,0,0,1,0), and m4=(761,727,417,523,278,912,0,0,0,1). The value of the order field of the first record is 6, and a vector, of which the components correspond to the component number lists 7, 8, 9, and 10 of a first record are all zero, does not lie in the vectors m1, m2, m3, and m4, whereby the first record is obtained as a retrieval result.
Furthermore, the value of the first vector type of the first record is (*,*,*,*,*,*,1,0,0,0)(A code * is interpreted as representing any number), which coincides with the vector m1=(699,601,688,281,217,287,1,0,0,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, X3, Y, X4, XY, X5, X2Y, and X6 of the algebraic curve parameter file A to generate a polynomial f1=699+601X+688X2+281X3+217Y+287X4+XY.
Similarly, the value of the second vector type of the first record is (*,*,*,*,*,*,0,1,0,0) (A code * is interpreted as representing any number), which coincides with the vector m2=(193,959,364,180,550,43,0,1,0,0), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, X3, Y, X4, XY, X5, X2Y, and X6 of the algebraic curve parameter file A to generate a polynomial f2=193+959X+364X2+180X3+550Y+43X4+X5. The value of third vector type of the first record is null, whereby it is neglected. Finally, the ideal composition section 11 constructs a set J={f1,f2}={699+601X+688X2+281X3+217Y+287X4+XY,193+959X+364X2+180X3+550Y+43X4+X5} of the polynomial to output it. Above, the operation of the ideal composition section 11 is finished.
Next, the first ideal reduction section 12, which takes as an input the algebraic curve parameter file A of FIG. 8, and the Groebner basis J={699+601X+688X2+281X3+217Y+287X4+XY, 193+959X+364X2+180X3+550Y+43X4X5} that the ideal composition section 11 output, operates as follows according to a flow of the process of the functional block shown in FIG. 3.
At first, in the ideal type classification section 31 of FIG. 3, the ideal reduction section 12 makes a reference to the ideal type table of FIG. 9, retrieves a record in which the ideal type described in the ideal type field accords with the type of the input ideal J for obtaining a first record, and acquires a value N=61 of the ideal type number field and a value d=3 of the reduction order field of the first record. Next, the ideal reduction section 12 confirms that said value d=3 is not zero, makes a reference to the monomial list table of FIG. 10 in the polynomial vector generation section 32, retrieves a record of which the value of the order field is said d=3 for obtaining a fourth record, and acquires a list 1, X, X2, X3, Y, X4, and XY of the monomial described in the monomial list field of the fourth record.
Furthermore, the ideal reduction section 12 acquires a first element f=699+601X+688X2+281X3+217Y+284X4+XY of J, and a second element g=193+959X+364X2+180X3+550Y+43X4+X5(A third element does not lie in J, whereby a third polynomial h is not employed), regards a coefficient list 0,7,0,0,0,0,0,0,0,0,0,1,1 of the algebraic curve parameter file A as a column of the coefficient of each monomial of the monomial order 1, X, X2, X3, Y, X4, XY, X5, X2Y, X6, X3Y, X7 and Y2 of the algebraic curve parameter file A, and generates a defining polynomial F=Y2+X7+7X.
Next, for each of Mi(1<=i<=7) in said list 1, X, X2, X3, Y, X4 and XY of said monomial, the ideal reduction section 12 calculates a remainder equation ri of a product Mi·g of Mi and the polynomial g by the polynomials f and F, arranges its coefficients in order of the monomial order 1, X, X2, X3, Y, X4, XY, X5, X2Y, X6, X3Y, and X7 of the algebraic curve parameter file A, and generates a vector vi. That is, at first, for a first monomial M1=1, divide 1·g=193+959X+364X2+180X3+550Y+43X4+X5 by f=699+601X+688X2+281X3+217Y+287X4+XY and F=Y2+X7+7X: then g=0·f+0·F+193+959X+364X2+180X3+550Y+43X4+X5, whereby a remainder 193+959X+364X2+180X3+550Y+43X4+X5 is obtained to generate a vector v1=(193,959,364,180,550,43,0,1,0,0,0,0).
Next, for a second monomial M2=X, divide Xg=X(193+959X+364X2+180X3+550Y+43X4+X5) by f=699+601X+688X2+281X3+217Y+287X4+XY and F=Y2+X7+7X: then Xg=550f+0·F+988+595X+934X2+191X3+743X4+43X5+X6+721Y, whereby a remainder 988+595X+934X2+191X3+743X4+43X5+X6+721Y is obtained to generate a vector v2=(988,595,934,191,721,743,0,43,0,1,0,0).
Next, for a third monomial M3=X2, divide X2g=X2(193+959X+364X2+180X3+550Y+43X4+X5) by f=699+601X+688X2+281X3+217Y+287X4+XY and F=Y2+X7+7X: then X2g=(721+550X)f+0·F+521+528Y+975X2+133X3+109X4+743X5+43X6+X7+947Y, whereby a remainder 521+528X+975X2+133X3+109X4+743X5+43X6+X7+947Y is obtained to generate a vector v3=(521,528,975,133,947,109,0,743,0,43,0,1).
Next, for a fourth monomial M4=X3, divide X3g=X3(193+959X+364X2+180X3+550Y+43X4+X5) by f=699+601X+688X2+281X3+217Y+287X4+XY and F=Y2+X7+7X: then X3g=(200+969X+101X2+287X3+1008Y)f+(217+X)F+451+78X+481X2+791X3+389X4+924X5+527X6+195X7+686Y, whereby a remainder 451+78X+481X2+791X3+389X4+924X5+527X6+195X7+686Y is obtained to generate a vector v4=(451,78,481,791,686,389,0,924,0,527,0,195).
Next, for a fifth monomial M5=Y, divide Yg=Y(193+959X+364X2+180X3+550Y+43X4+X5) by f=699+601X+688X2+281X3+217Y+287X4+XY and F=Y2+X7+7X: then Yg=(884+712X+316X2+195X3+X4+287Y)f+(829+722X)F+601+459X+217X2+14X3+965X4+924X5+130X6+438X7+253Y, whereby a remainder 601+459X+217X2+14X3+965X4+924X5+130X6+438X7+253Y is obtained to generate a vector v5=(601,459,217,14,253,965,0,924,0,130,0,438).
Next, for a sixth monomial M6=X4, divide X4g=X4(193+959X+364X2+180X3+550Y+43X4+X5) by f=699+601X+688X2+281X3+217Y+287X4+XY and F=Y2+X7+7X: then X4g=(317+128X+188X2+571X3+287X4+814Y+1008XY)f+(946+412X+X2) F+397+954X+514X2+891X3+255X4+901X5+173X6+906X7+922Y, whereby a remainder 397+954X+514X2+891X3+255X4+901X5+173X6+906X7+922Y is obtained to generate a vector v6=(397,954,514,891,922,255,0,901,0,173,0,906).
Finally, for a seventh monomial M7=XY, divide XYg=XY(193+959X+364X2+180X3+550Y+43X4+X5) by f=699+601X+688X2+281X3+217Y+287X4+XY and F=Y2+X7+7X: then XYg=(992+536X+805X2+906X3+195X4+X5+571Y+287XY)f+(200+258X+722X2)F+784+420X+871X2+113X3+933X4+749X5+153X6+112X7+88Y, whereby a remainder 784+420X+871X2+113X3+933X4+749X5+153X6+112X7+88 is obtained to generate a vector v7=(784,420,871,113,88,933,0,749,0,153,0,112). Above, the process of the second ideal reduction section 12 in the polynomial vector generation section 32 is finished.
Next, in the basis construction section 33, the second ideal reduction section 12 inputs seven 12-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 generated in the polynomial vector generation section 32 into the linear-relation derivation section 34, and obtains a plurality of seven-dimensional vectors m1, m2, . . . as an output.
The linear-relation derivation section 34 derives a linear relation of the vectors, which were input, employing the discharging method. The discharging method belongs to a known art, whereby, as to an operation of the linear-relation derivation section 34, only its outline is shown below. The linear-relation derivation section 34 firstly arranges the seven 12-dimensional vectors v1, v2, v3, v4, v5, v6, and v7, which were input, in order for constructing a 7×12 matrix




  
    
      
        
          M
          R
        
        =
        
          (
          
            
              
                193
              
              
                959
              
              
                364
              
              
                180
              
              
                550
              
              
                43
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                988
              
              
                595
              
              
                934
              
              
                191
              
              
                721
              
              
                743
              
              
                0
              
              
                43
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                521
              
              
                528
              
              
                975
              
              
                133
              
              
                947
              
              
                109
              
              
                0
              
              
                743
              
              
                0
              
              
                43
              
              
                0
              
              
                1
              
            
            
              
                451
              
              
                78
              
              
                481
              
              
                791
              
              
                686
              
              
                389
              
              
                0
              
              
                924
              
              
                0
              
              
                527
              
              
                0
              
              
                195
              
            
            
              
                601
              
              
                459
              
              
                217
              
              
                14
              
              
                253
              
              
                965
              
              
                0
              
              
                924
              
              
                0
              
              
                130
              
              
                0
              
              
                438
              
            
            
              
                397
              
              
                954
              
              
                514
              
              
                891
              
              
                922
              
              
                255
              
              
                0
              
              
                901
              
              
                0
              
              
                173
              
              
                0
              
              
                906
              
            
            
              
                784
              
              
                420
              
              
                871
              
              
                113
              
              
                88
              
              
                933
              
              
                0
              
              
                749
              
              
                0
              
              
                153
              
              
                0
              
              
                112
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          23
        
        ]
      
    
  




Next, the linear-relation derivation section 34 connects a seven-dimensional unity matrix to the matrix MR to construct




  
    
      
        
          M
          R
          ′
        
        =
        
          (
          
            
              
                193
              
              
                959
              
              
                364
              
              
                180
              
              
                550
              
              
                43
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                988
              
              
                595
              
              
                934
              
              
                191
              
              
                721
              
              
                743
              
              
                0
              
              
                43
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                521
              
              
                528
              
              
                975
              
              
                133
              
              
                947
              
              
                109
              
              
                0
              
              
                743
              
              
                0
              
              
                43
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                451
              
              
                78
              
              
                481
              
              
                791
              
              
                686
              
              
                389
              
              
                0
              
              
                924
              
              
                0
              
              
                527
              
              
                0
              
              
                195
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                601
              
              
                459
              
              
                217
              
              
                14
              
              
                253
              
              
                965
              
              
                0
              
              
                924
              
              
                0
              
              
                130
              
              
                0
              
              
                438
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                397
              
              
                954
              
              
                514
              
              
                891
              
              
                922
              
              
                255
              
              
                0
              
              
                901
              
              
                0
              
              
                173
              
              
                0
              
              
                906
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                784
              
              
                420
              
              
                871
              
              
                113
              
              
                88
              
              
                933
              
              
                0
              
              
                749
              
              
                0
              
              
                153
              
              
                0
              
              
                112
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          24
        
        ]
      
    
  




Next, the linear-relation derivation section 34 triangulates a matrix M′R by adding a constant multiple of an i-th row to an (i+1)-th row (i=1,2,3) to a seventh row to obtain the following a matrix m.




  
    
      
        m
        =
        
          (
          
            
              
                193
              
              
                959
              
              
                364
              
              
                180
              
              
                550
              
              
                43
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                485
              
              
                524
              
              
                587
              
              
                922
              
              
                434
              
              
                0
              
              
                247
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                204
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                362
              
              
                736
              
              
                914
              
              
                919
              
              
                0
              
              
                822
              
              
                0
              
              
                725
              
              
                0
              
              
                1
              
              
                14
              
              
                682
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                804
              
              
                795
              
              
                814
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                522
              
              
                542
              
              
                571
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                385
              
              
                443
              
              
                103
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                12
              
              
                627
              
              
                897
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          25
        
        ]
      
    
  




As well known, the vector that is composed of a thirteenth component and afterward of a fourth row to a seventh row of the matrix m is a vector {(m1,1,m1,2, . . . ,m1,7), (m2,1,m2,2, . . . ,m2,7), . . . } representing a linearly-independent linear dependence relation Σi=17mjivi=0(j=1,2, . . . ) of all of the seven 12-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 that were input. The linear-relation derivation section 34 outputs a vector m1=(804,795,814,1,0,0,0) that is composed of the thirteen component and afterward of the fourth row of the matrix m, a vector m2=(522,542,571,0,1,0,0) that is composed of the thirteenth component and afterward of the fifth row of the matrix m, and a vector m3=(385,443,103,0,0,1,0) that is composed of the thirteenth component and afterward of the sixth row of the matrix m, and a vector m4=(12,627,897,0,0,0,1) that is composed of the thirteen component and afterward of the seventh row of the matrix m.
Now return to the explanation of the process of the first ideal reduction section 12 in the basis construction section 33. Next, this second ideal reduction section 12 makes a reference to the table for a Groebner basis construction of FIG. 11, retrieves a record of which the value of the order field is said value d=3, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(804,795,814,1,0,0,0), m2=(522,542,571,0,1,0,0), m3=(385,443,103,0,0,1,0), and m4=(12,627,897,0,0,0,1). The value of the order field of an eleventh record is 3, and a vector, of which the components that correspond to the component number lists 4, 5, 6, and 7 of the eleventh record are all zero, does not lie in the vectors m1, m2, m3, and m4, whereby the eleventh record is obtained as a retrieval result.
Furthermore, the value of the first vector type of the eleventh record is (*,*,*,1,0,0,0) (A code * is interpreted as representing any number), which coincides with the vector m1=(804,795,814,1,0,0,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, X3, Y, X4, and XY of the algebraic curve parameter file A to generate a polynomial f1=804+795X+814X2+X3.
Similarly, the value of the second vector type of the eleventh record is (*,*,*,0,1,0,0) (A code * is interpreted as representing any number), which coincides with the vector m2=(522,542,571,0,1,0,0), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, X3, Y, X4, and XY of the algebraic curve parameter file A to generate a polynomial f2=522+542X+571X2+Y. The value of the third vector type of the eleventh record is null, whereby it is neglected. Finally, the ideal reduction section 12 constructs a set J*={f1,f2}={804+795X+814X2+X3,522+542X+571X2+Y} of the polynomial to output it. Above, the operation of the first ideal reduction section 12 is finished.
Next, the second ideal reduction section 13, which takes as an input the algebraic curve parameter file A of FIG. 8, and the Groebner basis J*={f1,f2}={804+795X+814X2+X3,522+542X+571X2+Y} that the first ideal reduction section 12 output, operates as follows according to a flow of the process of the functional block shown in FIG. 3. At first, the ideal reduction section 13 makes a reference to the ideal type table of FIG. 9 in the ideal type classification section 31 of FIG. 3, retrieves a record in which the ideal type described in the ideal type field accords with the type of the input ideal J* for obtaining an eleventh record, and acquires a value N=31 of the ideal type number field and a value d=3 of the reduction order field of the eleventh record.
Next, the ideal reduction section 13 confirms that said value d=3 is not zero, makes a reference to the monomial list table of FIG. 10 in the polynomial vector generation section 32, retrieves a record of which the value of the order field is said d=3 for obtaining a fourth record, and acquires a list 1, X, X2, X3, Y, X4, and XY of the monomial described in the monomial list field of the fourth record. Furthermore, the ideal reduction section 13 acquires a first element f=804+795X+814X2+X3, and a second element g=522+542X+571X2+Y of J* (A third element does not lie in J*, whereby a third polynomial h is not employed), regards a coefficient list 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, and 1 of the algebraic curve parameter file A as a column of the coefficient of each monomial of the monomial order 1, X, X2, X3, Y, X4, XY, X5, X2Y, X6, X3Y, X7 and Y2 of the algebraic curve parameter file A, and generates a defining polynomial F=Y2+X7+7X.
Next, for each of Mi(1<=i<=7) in said list 1, X, X2, X3, Y, X4 and XY of said monomial, the ideal reduction section 13 calculates a remainder equation ri of a product Mi·g of Mi and the polynomial g by the polynomials f and F, arranges its coefficients in order of the monomial order 1, X, X2, X3, Y, X4, XY, X5, X2Y, X6, X3Y, and X7 of the algebraic curve parameter file A, and generates a vector vi. That is, at first, for a first monomial M1=1, divide 1·g=522+542X+571X2+Y by f=804+795X+814X2+X3 and F=Y2+X7+7X: then g=0·f+0·F+522+542X+571X2+Y, whereby a remainder 522+542X+571X2+Y is obtained to generate a vector v1=(522,542,571,0,1,0,0,0,0).
Next, for a second monomial M2=X, divide Xg=X(522+542X+571X2+Y) by f=804+795X+814X2+X3 and F=Y2+X7+7X: then Xg=571f+0·F+11+627X+897X2+XY, whereby a remainder 11+627X+897X2+XY is obtained to generate a vector v2=(11,627,897,0,0,0,1,0,0).
Next, for a third monomial M3=X2, divide X2g=X2(522+542X+571X2+Y) by f=804+795X+814X2+X3 and F=Y2+X7+7X: then X2g=(897+571X)f+0·F+247+259X+985X2+X2Y, whereby a remainder 247+259X+985X2+X2Y is obtained to generate a vector v3=(247,259,985,0,0,0,0,0,1).
Next, for a fourth monomial M4=X3, divide X3g=X3(522+542X+571X2+Y) by f=804+795X+814X2+X3 and F=Y2+X7+7X: then X3g=(985+897X+571X2+Y)f+0·F+125+156X+624X2+205Y+214XY+195X2Y, whereby a remainder 125+156X+624X2+205Y+214XY+195X2Y is obtained to generate a vector v4=(125,156,624,0,205,0,214,0,195).
Next, for a fifth monomial M5=Y, divide Yg=Y(522+542X+571X2+Y) by f=804+795X+814X2+X3 and F=Y2+X7+7X: then Yg=(486+348X+103X2+814X3+1008X4)f+1·F+748+780X+665X2+522Y+542XY+571X2Y, whereby a remainder 748+780X+665X2+522Y+542XY+571X2Y is obtained to generate a vector v5=(748,780,665,0,522,0,542,0,571).
Next, for a sixth monomial M6=X4, divide X4g=X4(522+542X+571X2+Y) by f=804+795X+814X2+X3 and F=Y2+X7+7X: then X4g=(624+985X+897X2+571X3+195Y+XY)f+0·F+786+473X+756X2+624Y+566XY+906X2Y, whereby a remainder 786+473X+756X2+624Y+566XY+906X2Y is obtained to generate a vector v6=(786,473,756,0,624,0,566,0,906).
Finally, for a seventh monomial M7=XY, divide XYg=XY(522+542X+571X2+Y by f=804+795X+814X2+X3 and F=Y2+X7+7X: then XYg=(665+486X+348X2+103X3+814X4+1008X5+571Y) f+XF+110+789X+294X2+11Y+627XY+897X2Y, whereby a remainder 110+789X+294X2+11Y+627XY+897X2Y is obtained to generate a vector v7=(110,789,294,0,11,0,627,0,897). Above, the process of the second ideal reduction section 13 in the polynomial vector generation section 32 is finished.
Next, in the basis construction section 33, this ideal reduction section 13 inputs seven nine-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 generated in the polynomial vector generation section 32 into the linear-relation derivation section 34, and obtains a plurality of seven-dimensional vectors m1, m2, . . . as an output. The linear-relation derivation section 34 derives a linear relation of the vectors, which were input, employing the discharging method. The discharging method belongs to a known art, whereby, as to the operation of the linear-relation derivation section 34, only its outline is shown below.
The linear-relation derivation section 34 firstly arranges the seven nine-dimensional vectors v1, v2, v3, v4, v5, v6, and v7, which were input, in order for constructing a 7×9 matrix




  
    
      
        
          M
          R
        
        =
        
          (
          
            
              
                522
              
              
                542
              
              
                571
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                11
              
              
                627
              
              
                897
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                247
              
              
                259
              
              
                985
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
            
              
                125
              
              
                156
              
              
                624
              
              
                0
              
              
                205
              
              
                0
              
              
                214
              
              
                0
              
              
                195
              
            
            
              
                784
              
              
                780
              
              
                665
              
              
                0
              
              
                522
              
              
                0
              
              
                542
              
              
                0
              
              
                571
              
            
            
              
                786
              
              
                473
              
              
                756
              
              
                0
              
              
                624
              
              
                0
              
              
                566
              
              
                0
              
              
                906
              
            
            
              
                110
              
              
                789
              
              
                294
              
              
                0
              
              
                11
              
              
                0
              
              
                627
              
              
                0
              
              
                897
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          26
        
        ]
      
    
  




Next, the linear-relation derivation section 34 connects a seven-dimensional unity matrix to the matrix MR to construct



  
    
      
    
    ⁢
    
      [
      
        EQ
        .
        
          
        
        ⁢
        27
      
      ]
    
  




  
    
      M
      R
      ′
    
    =
    
      (
      
        
          
            522
          
          
            542
          
          
            571
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            11
          
          
            627
          
          
            897
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            247
          
          
            259
          
          
            985
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            125
          
          
            156
          
          
            624
          
          
            0
          
          
            205
          
          
            0
          
          
            214
          
          
            0
          
          
            195
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            748
          
          
            780
          
          
            665
          
          
            0
          
          
            522
          
          
            0
          
          
            542
          
          
            0
          
          
            571
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
        
        
          
            786
          
          
            473
          
          
            756
          
          
            0
          
          
            624
          
          
            0
          
          
            566
          
          
            0
          
          
            906
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
        
        
          
            110
          
          
            789
          
          
            294
          
          
            0
          
          
            11
          
          
            0
          
          
            627
          
          
            0
          
          
            897
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
        
      
      ⁢
      
        
      
      )
    
  



Next, the linear-relation derivation section 34 triangulates a matrix M′R by adding a constant multiple of an i-th row to an (i+1)-th row (i=1,2,3) to a seventh row to obtain the following matrix m.



  
    
      
    
    ⁢
    
      [
      
        EQ
        .
        
          
        
        ⁢
        28
      
      ]
    
  




  
    m
    =
    
      (
      
        
          
            522
          
          
            542
          
          
            571
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            171
          
          
            48
          
          
            0
          
          
            230
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
          
            230
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            976
          
          
            0
          
          
            385
          
          
            0
          
          
            53
          
          
            0
          
          
            1
          
          
            385
          
          
            53
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            804
          
          
            795
          
          
            814
          
          
            1
          
          
            0
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            487
          
          
            467
          
          
            438
          
          
            0
          
          
            1
          
          
            0
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            385
          
          
            443
          
          
            103
          
          
            0
          
          
            0
          
          
            1
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            0
          
          
            998
          
          
            382
          
          
            112
          
          
            0
          
          
            0
          
          
            0
          
          
            1
          
        
      
      )
    
  



As well known, the vector that is composed of a tenth component and afterward of a fourth row to a seventh row of the matrix m is a vector {(m1,1,m1,2, . . . ,m1,n), (m2,1,m2,2, . . . , m2,n), . . . } representing a linearly-independent linear dependence relation Σi7mjivi=0(j=1,2, . . . ) of all of the seven 12-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 that were input. The linear-relation derivation section 34 outputs a vector m1=(804,795,814,1,0,0,0) that is composed of the tenth component and afterward of the fourth row of the matrix m, a vector m2=(487,467,438,0,1,0,0) that is composed of the tenth component and afterward of the fifth row of the matrix m, and a vector m3=(385,443,103,0,0,1,0) that is composed of the tenth component and afterward of the sixth row of the matrix m, and a vector m4=(998,382,112,0,0,0,1) that is composed of the tenth component and afterward of the seventh row of the matrix m.
Now return to the explanation of the process of the second ideal reduction section 13 in the basis construction section 33. Next, this ideal reduction section 13 makes a reference to the table for a Groebner basis construction of FIG. 11, retrieves a record, of which the value of the order field is said value d=3, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(804,795,814,1,0,0,0), m2=(487,467,438,0,1,0,0), m3=(385,443,103,0,0,1,0), and m4=(998,382,112,0,0,0,1). The value of the order field of an eleventh record is 3, and a vector, of which the component number lists 4, 5, 6, and 7 of the eleventh record are all zero, does not lie in the vectors m1, m2, m3, and m4, whereby the eleventh record is obtained as a retrieval result.
Furthermore, the value of the first vector type of the eleventh record is (*,*,*,1,0,0,0) (A code * is interpreted as representing any number), which coincides with the vector m1=(804,795,814,1,0,0,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, X3, Y, X4, and XY of the algebraic curve parameter file A to generate a polynomial f1=804+795X+814X2+X3.
Similarly, the value of the second vector type of the eleventh record is (*,*,*,0,1,0,0) (A code * is interpreted as representing any number), which coincides with the vector m2=(487,467,438,0,1,0,0), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, X3, Y, X4, and XY of the algebraic curve parameter file A to generate a polynomial f2=487+467X+438X2+Y. The value of the third vector type of the eleventh record is null, whereby it is neglected.
Finally, the ideal reduction section 13 constructs a set J**={f1,f2}={804+795X+814X2+X3, 487+467X+438X2+Y} of the polynomial to output it. Above, the operation of the second ideal reduction section 13 is finished. Finally, in the Jacobian group adder of FIG. 1, the Groebner basis J**={804+795X+814X2+X3,487+467X+438X2+Y}, which the ideal reduction section 13 output, is output from the output apparatus.
Next, the embodiment of the case will be shown in which the C25 curve was employed. In this embodiment, the algebraic curve parameter file of FIG. 12 is employed as an algebraic curve parameter file, the ideal type table of FIG. 13 as an ideal type table, the monomial list table of FIG. 14 as an monomial list table, and the table for a Groebner basis construction of FIG. 15 as a table for a Groebner basis construction respectively.
In the Jacobian group element adder of FIG. 1, suppose Groebner bases

I1={729+88X+X2,475+124X+Y}

and

I2={180+422X+X2,989+423X+Y}

were input of the ideal of the coordinate ring of the algebraic curve designated by the algebraic curve parameter file A, which represents an element of the Jacobian group of the C25 curve designated by the algebraic curve parameter file A 16 and the algebraic curve parameter file A of FIG. 12.

At first, the ideal composition section 11, which takes the algebraic curve parameter file A of FIG. 12, and the above-mentioned Groebner bases I1 and I2 as an input, operates as follows according to a flow of the process of the functional block shown in FIG. 2. The ideal composition section 11 firstly makes a reference to the ideal type table of FIG. 13 in the ideal type classification section 21 of FIG. 2, retrieves a record in which the ideal type described in the ideal type field accords with the type of the input ideal I1 for obtaining a sixth record, and acquires a value N1=21 of the ideal type number field and a value d1=2 of the order field of the sixth record. Similarly, the ideal composition section 11 retrieves a record in which the ideal type accords with the type of the input ideal I2 for obtaining the sixth record, and acquires a value N2=21 of the ideal type number field and a value d2=2 of the order field of the sixth record.
Next, the ideal composition section 11 calculates the sum d3=d1+d2=4 of said values d1=2 and d2=2 of said order field in the monomial vector generation section 22, makes a reference to the monomial list table of FIG. 14, retrieves a record of which the value of the order field is said d3=4 for obtaining the first record, and acquires a list of the monomial 1, X, X2, Y, X3, XY, and X4 described in the monomial list field of the first record. I1 and I2 are different, whereby a remainder to be attained by dividing Mi by I1 for each of Mi(1<=i<=7) in said list 1, X, X2, Y, X3, XY, and X4 of said monomial is calculated to obtained a polynomial a(i)1+a(i)2X, to arrange its coefficients in order of the monomial order 1, X, . . . of the algebraic curve parameter file A, and to generate a vector w(i)1=(a(i)1,a(i)2).
Furthermore, the ideal composition section 11 calculates a remainder to be attained by dividing Mi by I2, obtains a polynomial b(i)1+b(i)2X, arranges its coefficients in order of the monomial order 1, X, . . . of the algebraic curve parameter file A, generates a vector w(i)2=(b(i)1,b(i)2), and connects the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi=(a(i)1,a(i)2,b(i)1,b(i)2). That is, divide M1=1 by I1: then 1=0·(729+88X+X2)+0·(475+124X+Y)+1, whereby 1 is obtained as a remainder to generate a vector w(1)1=(1,0). Furthermore, divide M1=1 by I2: then 1=0·(180+422X+X2)+0·(989+423X+Y)+1, whereby 1 is obtained as a remainder to generate a vector w(1)2=(1,0). w(1)1 and w(1)2 are connected to generate a vector v1=(1,0,1,0).
Next, divide M2=X by I1: then X=0·(729+88X+X2)+0·(475+124X+Y)+X, whereby, X is obtained as a remainder to generate a vector w(2)1=(0,1). Furthermore, divide M2=X by I2: then X=0·(180+422X+X2)+0·(989+423X+Y)+X, whereby X is obtained as a remainder to generate a vector w(2)2=(0,1). w(2)1 and w(2)2 are connected to generate a vector v2=(0,1,0,1).
Next, divide M3=X2 by I1: then X2=1·(729+88X+X2)+0·(475+124X+Y)+280+921X, whereby, 280+921X is obtained as a remainder to generate a vector w(3)1=(280,921). Furthermore, divide M3=X2 by I2: then X2=1·(180+422X+X2)+0·(989+423X+Y)+829+587X, whereby 829+587X is obtained as a remainder to generate a vector w(3)2=(829,587). w(3)1 and w(3)2 are connected to generate a vector v3=(280,921,829,587).
Next, divide M4=Y by I1: then Y=0·(729+88X+X2)+1·(475+124X+Y)+534+885X, whereby 534+885X is obtained as a remainder to generate a vector w(4)1=(534,885). Furthermore, divide M4=Y by I2: then Y=0·(180+422X+X2)+1·(989+423X+Y)+20+586X, whereby 20+586X is obtained as a remainder to generate a vector w(4)2=(20,586). w(4)1 and w(4)2 are connected to generate a vector v4=(534,885,20,586).
Next, divide M5=X3 by I1: then X3=(921+X)(729+88X+X2)+0·(475+124X+Y)+585+961X, whereby 585+961X is obtained as a remainder to generate a vector w(5)1=(585,961).
Furthermore, divide M5=X3 by I2: then X3=(587+X)(180+422X+X2)+0·(989+423X+Y)+285+320X, whereby 285+320X is obtained as a remainder to generate a vector w(5)2=(285,320). w(5)1 and w(5)2 are connected to generate a vector v5=(585,961,285,320). Next, divide M6=XY by I1: then XY=885(729+88X+X2)+X·(475+124X+Y)+595+347X, whereby 595+347X is obtained as a remainder to generate a vector w(6)1=(595,347).
Furthermore, divide M6=XY by I2: then XY=586(180+422X+X2)+X(989+423X+Y)+465+942X, whereby 465+942X is obtained as a remainder to generate a vector w(6)2=(465,942). w(6)1 and w(6)2 are connected to generate a vector v6=(595,347,465,942).
Finally, divide M7=X4 by I1: then X4=(961+921X+X2)(729+88X+X2)+0·(475+124X+Y)+686+773X, whereby, 686+773X is obtained as a remainder to generate a vector w(7)1=(686,773). Furthermore, divide M7=X4 by I2: then X4=(320+587X+X2)(180+422X+X2)+0·(989+423X+Y)+922+451X, whereby 922+451X is obtained as a remainder to generate a vector w(7)2=(922,451). w(7)1 and w(7)2 are connected to generate a vector v7=(686,773,922,451). Above, the process of the ideal composition section 11 in the monomial vector generation section 22 is finished.
Next, in the basis construction section 23, the ideal composition section 11 inputs seven four-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 generated in the monomial vector generation section 22 into the linear-relation derivation section 24, and obtains a plurality of seven-dimensional vectors m1, m2, . . . as an output. The linear-relation derivation section 24 derives a linear relation of the vectors, which were input, employing the discharging method. The discharging method belongs to a known art, whereby, as to the operation of the linear-relation derivation section 24, only its outline is shown below. The linear-relation derivation section 24 firstly arranges the seven four-dimensional vectors v1, v2, v3, v4, v5, v6, and v7, which were input, in order for constructing a 7×4 matrix




  
    
      
        
          M
          C
        
        =
        
          (
          
            
              
                1
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                1
              
              
                0
              
              
                1
              
            
            
              
                280
              
              
                921
              
              
                829
              
              
                587
              
            
            
              
                534
              
              
                885
              
              
                20
              
              
                586
              
            
            
              
                585
              
              
                961
              
              
                285
              
              
                320
              
            
            
              
                595
              
              
                347
              
              
                465
              
              
                942
              
            
            
              
                686
              
              
                773
              
              
                922
              
              
                451
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          29
        
        ]
      
    
  




Next, the linear-relation derivation section 24 connects a seven-dimensional unity matrix to the matrix MC to obtain




  
    
      
        
          M
          C
          ′
        
        =
        
          (
          
            
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                280
              
              
                921
              
              
                829
              
              
                587
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                534
              
              
                885
              
              
                20
              
              
                586
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                585
              
              
                961
              
              
                285
              
              
                320
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                595
              
              
                347
              
              
                465
              
              
                942
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                686
              
              
                773
              
              
                922
              
              
                451
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          30
        
        ]
      
    
  




Next, the linear-relation derivation section 24 triangulates a matrix M′C by adding a constant multiple of an i-th row to an (i+1)-th row (i=1,2, . . . ,4) to a seventh row to obtain the following a matrix m.




  
    
      
        m
        =
        
          (
          
            
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                549
              
              
                675
              
              
                729
              
              
                88
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                548
              
              
                744
              
              
                789
              
              
                363
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                444
              
              
                709
              
              
                900
              
              
                42
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                969
              
              
                716
              
              
                940
              
              
                619
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                635
              
              
                230
              
              
                807
              
              
                778
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          31
        
        ]
      
    
  




As well known, the vector that is composed of a fifth component and afterward of a fifth row to a seventh row of the matrix m is a vector {(m1,1,m1,2, . . . ,m1,7), (m2,1,m2,2, . . . ,m2,7), . . . } representing a linearly-independent linear dependence relation Σi=17mjivi=0(j=1,2, . . . ) of all of the seven four-dimensional vectors v1, v2, v3, v4, v5, v6, and v7 that were input.
The linear-relation derivation section 24 outputs a vector m1=(444,709,900,42,1,0,0) that is composed of the fifth component and afterward of the fifth row of the matrix m, a vector m2=(969,716,940,619,0,1,0) that is composed of the fifth component and afterward of the sixth row of the matrix m, and a vector m3=(635,230,807,778,0,0,1) that is composed of the fifth component and afterward of the seventh row of the matrix m.
Now return to the explanation of the process of the ideal composition section 11 in the basis construction section 23. Next, the ideal composition section 11 makes a reference to the table for a Groebner basis construction of FIG. 15, retrieves a record, of which the value of the order field is said value d3=4, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(444,709,900,42,1,0,0), m2=(969,716,940,619,0,1,0), and m3=(635,230,807,778,0,0,1). The value of the order field of a first record is 4, and a vector, of which the components that correspond to the component number lists, 5, 6, and 7 of the first record are all zero, does not lie in the vectors m1, m2, and m3, whereby the first record is obtained as a retrieval result.
Furthermore, the value of the first vector type of the first record is (*,*,*,*,1,0,0)(A code * is interpreted as representing any number), which coincides with the vector m1=(444,709,900,42,1,0,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, Y, X3, XY, and X4 of the algebraic curve parameter file A to generate a polynomial f1=444+709X+900X2+42Y+X3.
Similarly, the value of the second vector type of the first record is (*,*,*,*,0,1,0)(A code * is interpreted as representing any number), which coincides with the vector m2=(969,716,940,619,0,1,0), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, Y, X3, XY, and X4 of the algebraic curve parameter file A to generate a polynomial f2=969+716X+940X2+619Y+XY. The value of the third vector type of the first record is null, whereby it is neglected. Finally, the ideal composition section 11 constructs a set J={f1,f2}={444+709X+900X2+42Y+X3,969+716X+940X2+619Y+XY} of the polynomial to output it. Above, the operation of the ideal composition section 11 is finished.
Next, the first ideal reduction section 12, which takes as an input the algebraic curve parameter file A of FIG. 12, and the Groebner bases J={444+709X+900X2+42Y+X3,969+716X+940X2+619Y+XY} that the ideal composition section 11 output, operates as follows according to a flow of the process of the functional block shown in FIG. 3. At first, the first ideal reduction section 12 makes a reference to the ideal type table of FIG. 12 in the ideal type classification section 31 of FIG. 3, retrieves a record in which the ideal type described in the ideal type field accords with the type of the input ideal J for obtaining a first record, and acquires a value N=41 of the ideal type number field and a value d=2 of the reduction order field of the first record.
Next, the ideal reduction section 12 confirms that said value d=2 is not zero, makes a reference to the monomial list table of FIG. 14 in the polynomial vector generation section 32, retrieves a record of which the value of the order field is said d=2 for obtaining a third record, and acquires a list 1, X, X2, and Y of the monomial described in the monomial list field of the third record. Furthermore, the ideal reduction section 12 acquires a first element f=444+709X+900X2+42Y+X3, and a second element g=969+716X+940X2+619Y+XY of J (A third element does not lie in J, whereby a third polynomial h is not employed), regards a coefficient list 0, 7, 0, 0, 0, 0, 0, 0, 1, and 1 of the algebraic curve parameter file A as a column of the coefficient of each monomial of the monomial order 1, X, X2, Y, X3, XY, X4, X2Y, X5, and Y2 of the algebraic curve parameter file A, and generates a defining polynomial F=Y2+X5+7X.
Next, for each of Mi(1<=i<=4) in said list 1, X, X2, and Y of said monomial, the ideal reduction section 12 calculates a remainder equation ri of a product Mi·g of Mi and the polynomial g by the polynomials f and F, arranges its coefficients in order of the monomial order 1, X, X2, Y, X3, XY, X4, and X2Y of the algebraic curve parameter file A, and generates a vector vi. That is, at first, for a first monomial M1=1, divide 1·g=969+716X+940X2+619Y+XY by f=444+709X+900X2+42Y+X3 and F=Y2+X5+7X: then g=0·f+0·F+969+716X+940X2+619Y+XY, whereby a remainder 969+716X+940X2+619Y+XY is obtained to generate a vector v1=(969,716,940,619,0,1,0,0).
Next, a second monomial M2=X, divide Xg=X(969+716X+940X2+619Y+XY) by f=444+709X+900X2+42Y+X3 and F=Y2+X5+7X: then Xg=940f+0·F+366+449X+258X2+880Y+619XY+X2Y, whereby a remainder 366+449X+258X2+880Y+619XY+X2Y is obtained to generate a vector v2=(366,449,258,880,0,619,0,1).
Next, a third monomial M3=X2, divide X2g=X2(969+716X+940X2+619Y+XY) by f=444+709X+900X2+42Y+X3 and F=Y2+X5+7X: then X2g=(297+473X+42X2+Y) f+967F+311+462X+199X2+199Y+614XY+982X2Y, whereby a remainder 311+462X+199X2+199Y+614XY+982X2Y is obtained to generate a vector v3=(311,462,199,199,0,614,0,982).
Finally, a fourth monomial M4=Y, divide Yg=Y(969+716X+940X2+619Y+XY) by f=444+709X+900X2+42Y+X3 and F=Y2+X5+7X: then Yg=(994+625X+27X2+1008X3+42Y)f+(873+X)F+606+463X+322X2+104Y+183XY+348X2Y, whereby a remainder 606+463X+322X2+104Y+183XY+348X2Y is obtained to generate a vector v4=(606,463,322,104,0,183,0,348). Above, the process of the ideal reduction section 12 in the polynomial vector generation section 32 is finished.
Next, in the basis construction section 33, the first ideal reduction section 12 inputs four eight-dimensional vectors v1, v2, v3, and v4 generated in the polynomial vector generation section 32 into the linear-relation derivation section 34, and obtains a plurality of four-dimensional vectors m1, m2, . . . as an output. The linear-relation derivation section 34 derives a linear relation of the vectors, which were input, employing the discharging method. The discharging method belongs to a known art, whereby, as to the operation of the linear-relation derivation section 34, only its outline is shown below.
The linear-relation derivation section 34 firstly arranges the four eight-dimensional vectors v1, v2, v3, and, v4, which were input, in order for constructing a 4×8 matrix




  
    
      
        
          M
          R
        
        =
        
          (
          
            
              
                969
              
              
                716
              
              
                940
              
              
                619
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                366
              
              
                449
              
              
                258
              
              
                880
              
              
                0
              
              
                619
              
              
                0
              
              
                1
              
            
            
              
                311
              
              
                462
              
              
                199
              
              
                199
              
              
                0
              
              
                614
              
              
                0
              
              
                982
              
            
            
              
                606
              
              
                463
              
              
                322
              
              
                104
              
              
                0
              
              
                183
              
              
                0
              
              
                348
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          32
        
        ]
      
    
  




Next, the linear-relation derivation section 34 connects a four-dimensional unity matrix to the matrix MR to construct




  
    
      
        
          M
          R
          ′
        
        =
        
          (
          
            
              
                969
              
              
                716
              
              
                940
              
              
                619
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                366
              
              
                449
              
              
                258
              
              
                880
              
              
                0
              
              
                619
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                311
              
              
                462
              
              
                199
              
              
                199
              
              
                0
              
              
                614
              
              
                0
              
              
                982
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                606
              
              
                463
              
              
                322
              
              
                104
              
              
                0
              
              
                183
              
              
                0
              
              
                348
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          33
        
        ]
      
    
  




Next, the linear-relation derivation section 34 triangulates a matrix M′R by adding a constant multiple of an i-th row to an (i+1)-th row (i=1,2) to a fourth row to obtain the following matrix m.




  
    
      
        m
        =
        
          (
          
            
              
                969
              
              
                716
              
              
                940
              
              
                619
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                341
              
              
                787
              
              
                848
              
              
                0
              
              
                275
              
              
                0
              
              
                1
              
              
                665
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                835
              
              
                27
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                312
              
              
                661
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          34
        
        ]
      
    
  




As well known, the vector that is composed of a ninth component and afterward of a third row and a fourth row of the matrix m is a vector {(m1,1,m1,2, . . . ,m1,4), (m2,1,m2,2, . . . ,m2,4),. . . } representing a linearly-independent linear dependence relation Σi=14mjivi=0(j=1,2, . . . ) of all of the four eight-dimensional vectors v1, v2, v3, and v4 that were input. The linear-relation derivation section 34 outputs a vector m1=(835,27,1,0) that is composed of the ninth component and afterward of the third row of the matrix m, and a vector m2=(312,661,0,1) that is composed of the ninth component and afterward of the fourth row of the matrix m.
Now return to the explanation of the process of the first ideal reduction section 12 in the basis construction section 33. Next, the ideal reduction section 12 makes a reference to the table for a Groebner basis construction of FIG. 15, and retrieves a record, of which the value of the order field is said value d=2, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(835,27,1,0), and m2=(312,661,0,1). The value of the order field of a sixth record is 2, and a vector, of which the components that correspond to the component number lists 3 and 4 of the sixth record are all zero, does not lie in the vectors m1 and m2, whereby the sixth record is obtained as a retrieval result.
Furthermore, the value of the first vector type of the sixth record is (*,*,1,0)(A code * is interpreted as representing any number), which coincides with the vector m1=(835,27,1,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, and Y of the algebraic curve parameter file A to generate a polynomial f1=835+27X+X2. Similarly, the value of the second vector type of the sixth record is (*,*,0,1)(A code * is interpreted as representing any number), which coincides with the vector m2=(312,661,0,1), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2,and Y of the algebraic curve parameter file A to generate a polynomial f2=312+661X+Y. The value of the third vector type of the sixth record is null, whereby it is neglected. Finally, the ideal reduction section 12 constructs a set J*={f1,f2}={835+27X+X2,312+661X+Y} of the polynomial to output it. Above, the operation of the first ideal reduction section 12 is finished.
Next, the second ideal reduction section 13, which takes as an input the algebraic curve parameter file A of FIG. 12, and the Groebner basis J*={f1,f2}={835+27X+X2,312+661X+Y} that the first ideal reduction section 12 output, operates as follows according to a flow of the process of the functional block shown in FIG. 3. At first, the second ideal reduction section 13 makes a reference to the ideal type table of FIG. 13 in the ideal type classification section 31 of FIG. 3, retrieves a record in which the ideal type described in the ideal type field accords with the type of the input ideal J* for obtaining a sixth record, and acquires a value N=21 of the ideal type number field and a value d=2 of the reduction order field of the sixth record.
Next, the ideal reduction section 13 confirms that said value d=2 is not zero, makes a reference to the monomial list table of FIG. 14 in the polynomial vector generation section 32, retrieves a record of which the value of the order field is said d=2 for obtaining a third record, and acquires a list 1, X, X2, and Y of the monomial described in the monomial list field of the third record. Furthermore, the ideal reduction section 13 acquires a first element f=835+27X+X2, and a second element g=312+661X+Y of J* (A third element does not lie in J*, whereby a third polynomial h is not employed), regards a coefficient list 0, 7, 0, 0, 0, 0, 0, 0, 1, and 1 of the algebraic curve parameter file A as a column of the coefficient of each monomial of the monomial order 1, X, X2, Y, X3, XY, X4, X2Y, X5, and Y2 of the algebraic curve parameter file A, and generates a defining polynomial F=Y2+X5+7X.
Next, for each of Mi(1<=i<=4) in said list 1, X, X2 and Y of said monomial, the ideal reduction section 13 calculates a remainder equation ri of a product Mi·g of Mi and the polynomial g by the polynomials f and F, arranges its coefficients in order of the monomial order 1, X, X2, Y, X3, XY, X4, and X2Y of the algebraic curve parameter file A, and generates a vector vi. That is, at first, for a first monomial M1=1, divide 1·g=312+661X+Y by f=835+27X+X2 and F=Y2+X5+7X: then g=0·f+0·F+312+661X+Y, whereby a remainder 312+661X+Y is obtained to generate a vector v1=(312,661,0,1,0,0).
Next, a second monomial M2=X, divide Xg=X(312+661X+Y) by f=835+27X+X2 and F=Y2+X5+7X: then Xg=661f+0·F+997+627X+XY, whereby a remainder 997+627X+XY is obtained to generate a vector v2=(997,627,0,0,0,1). Next, a third monomial M3=X2, divide X2g=X2(312+661X+Y) by f=835+27X+X2 and F=Y2+X5+7X: then X2g=(627+661X+Y)f+0·F+126+212X+174Y+982XY, whereby a remainder 126+212X+174Y+982XY is obtained to generate a vector v3=(126,212,0,174,0,982).
Finally, a fourth monomial M4=Y, divide Yg=Y(312+661X+Y) by f=835+27X+X2 and F=Y2+X5+7X: then Yg=(827+106X+27X2+1008X3)f+1·F+620+144X+312Y+661XY, whereby a remainder 620+144X+312Y+661XY is obtained to generate a vector v4=(620,144,0,312,0,661). Above, the process of the second ideal reduction section 13 in the polynomial vector generation section 32 is finished.
Next, in the basis construction section 33, this second ideal reduction section 13 inputs four six-dimensional vectors v1, v2, v3, and v4 generated in the polynomial vector generation section 32 into the linear-relation derivation section 34, and obtains a plurality of four-dimensional vectors m1, m2, . . . as an output. The linear-relation derivation section 34 derives a linear relation of the vectors, which were input, employing the discharging method. The discharging method belongs to a known art, whereby, as to the operation of the linear-relation derivation section 34, only its outline is shown below.
The linear-relation derivation section 34 firstly arranges the four six-dimensional vectors v1, v2, v3, and, v4, which were input, in order for constructing a 4×6 matrix




  
    
      
        
          M
          R
        
        =
        
          (
          
            
              
                312
              
              
                661
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                997
              
              
                627
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
            
              
                126
              
              
                212
              
              
                0
              
              
                174
              
              
                0
              
              
                982
              
            
            
              
                620
              
              
                144
              
              
                0
              
              
                312
              
              
                0
              
              
                661
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          35
        
        ]
      
    
  




Next, the linear-relation derivation section 34 connects a four-dimensional unity matrix to the matrix MR to construct




  
    
      
        
          M
          R
          ′
        
        =
        
          (
          
            
              
                312
              
              
                661
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                997
              
              
                627
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                126
              
              
                212
              
              
                0
              
              
                174
              
              
                0
              
              
                982
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
            
            
              
                620
              
              
                144
              
              
                0
              
              
                312
              
              
                0
              
              
                661
              
              
                0
              
              
                0
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          36
        
        ]
      
    
  




Next, the linear-relation derivation section 34 triangulates a matrix M′R by adding a constant multiple of an i-th row to an (i+1)-th row (i=1,2) to a fourth row to obtain the following matrix m.




  
    
      
        m
        =
        
          (
          
            
              
                312
              
              
                661
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                1
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                536
              
              
                0
              
              
                815
              
              
                0
              
              
                1
              
              
                815
              
              
                1
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                835
              
              
                27
              
              
                1
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                697
              
              
                348
              
              
                0
              
              
                1
              
            
          
          )
        
      
    
    
      
        [
        
          EQ
          .
          
            
          
          ⁢
          37
        
        ]
      
    
  




As well known, the vector that is composed of a seventh component and afterward of a third row and a fourth row of the matrix m is a vector {(m1,1,m1,2, . . . ,m1,4), (m2,1,m2,2, . . . ,m2,4), . . . } representing a linearly-independent linear dependence relation Σi=14mjivi=0(j=1,2, . . . ) of all of the four six-dimensional vectors v1, v2, v3, and v4 that were input.
The linear-relation derivation section 34 outputs a vector m1=(835,27,1,0) that is composed of the seventh component and afterward of the third row of the matrix m, and a vector m2=(697,348,0,1) that is composed of the seventh component and afterward of the fourth row of the matrix m. Now return to the explanation of the process of the ideal reduction section 13 in the basis construction section 33. Next, the ideal reduction section 13 makes a reference to the table for a Groebner basis construction of FIG. 15, retrieves a record, of which the value of the order field is said value d=2, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1=(835,27,1,0), and m2=(697,348,0,1). The value of the order field of a sixth record is 2, and a vector, of which the component number lists 3 and 4 of the sixth record are all zero, does not lie in the vectors m1, and m2, whereby the sixth record is obtained as a retrieval result.
Furthermore, the value of the first vector type of the sixth record is (*,*,1,0)(A code * is interpreted as representing any number), which coincides with the vector m1=(835,27,1,0), whereby the vector m1 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2, and Y of the algebraic curve parameter file A to generate a polynomial f1=835+27X+X2. Similarly, the value of the second vector type of the sixth record is (*,*,0,1)(A code * is interpreted as representing any number), which coincides with the vector m2=(697,348,0,1), whereby the vector m2 is regarded as a column of the coefficient of each monomial of the monomial order 1, X, X2,and Y of the algebraic curve parameter file A to generate a polynomial f2=697+348X+Y. The value of the third vector type of the sixth record is null, whereby it is neglected. Finally, the ideal reduction section 13 constructs a set J**={f1,f2}={835+27X+X2,697+348X+Y} of the polynomial to output it. Above, the operation of the ideal reduction section 13 is finished. Finally, in the Jacobian group adder of FIG. 1, the Groebner basis J**={835+27X+X2,697+348X+Y}, which the second ideal reduction section 13 output, is output from the output apparatus.
The effect exists: employment of the present invention allows the addition in the Jacobian group of the Cab curve to be calculated at a high speed, and practicality of the Cab curve to be enhanced.
The present invention has been described with reference to the preferred embodiments. However, it will be appreciated by those skilled in the relevant field that a number of other embodiments, differing from those specifically described, will also fall within the spirit and scope of the present invention. Accordingly, it will be understood that the invention is not intended to be limited to the embodiments described in the specification. The scope of the invention is only limited by attached claims.
The entire disclosure of Japanese Patent Application No. 2002-240034 filed on Aug. 21, 2002 including specification, claims, drawing and summary are incorporated herein by reference in its entirety.

## Claims

1. 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


Y3+α0X4+α1XY2+α2X2Y+α3X3+α4Y2+α5XY+α6X2+α7Y+α8X+α9


or


Y2+α0X5+α1X2Y+α2X4+α3XY+α4X3+α5Y+α6X2+α7X+α8


or


Y2+α0X7+α1X3Y+α2X6+α3X2Y+α4X5+α5XY+α6X4+α7Y+α8X3+α9X2+α10X+α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 I1 and I2 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 I1 generates, and the ideal that the Groebner basis I2 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.

2. The Jacobian group element adder according to claim 1, wherein said ideal composition means has:
linear-relation derivation means for, for a plurality of vectors v1, v2, . . . , and vn that were input, outputting a plurality of vectors {m1=(m1,1,m1,2, . . . ,m1,n),m2=(m2,1,m2,2, . . . ,m2,n), . . . } representing linear dependence relations Σimj,ivi=0(j=1,2, . . . ) of all of them employing a discharging method;
an ideal type table that is composed of a record number field, an ideal type number field, an order field, and an ideal type field;
a monomial list table that is composed of the record number field, the order field, and a monomial list field;
a table for a Groebner basis construction that is composed of the record number field, the order field, a component number list field, a first vector type field, a second vector type field, and a third vector type field;
ideal type classification means for acquiring said algebraic curve parameter file to make a reference to said ideal type table for each of Groebner bases I1 and I2 that were input, to retrieve a record in which the ideal type described in the ideal type field accords with the type of an input ideal Ii(i=1,2), and to acquire a value Ni of the ideal type number field and a value di of the order field of the retrieved record;
monomial vector generation means for calculating a sum d3=d1+d2 of said values d1 and d2 of said order field to make a reference to said monomial list table for retrieving a record R of which a value of the order field is said d3, to acquire a list M1, M2, . . . of the monomial described in said monomial list field of said record R, when I1 and I2 are different, to calculate a remainder equation r1 of dividing each said monomial Mi by I1, to generate a vector w(i)1 that is composed of coefficients of the remainder equation ri according to the monomial order described in said algebraic curve parameter file, furthermore to calculate a remainder equation si of dividing Mi by I2, to generate a vector w(i)2 that is composed of coefficients of the remainder equation si according to the monomial order described in an algebraic curve parameter file A, to connect the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi, also, when I1 and I2 are equal, to calculate a remainder equation ri of dividing each said monomial Mi by I1, to generate a vector w(i)1 that is composed of coefficients of the remainder equation ri according to the monomial order described in said algebraic curve parameter file, furthermore to construct a defining polynomial F employing the coefficient list and the monomial order described in said algebraic curve parameter file, when a differential of a polynomial M with regard to by its X is expressed by DX(M), and a differential of the polynomial M with regard to by its Y is expressed by DY(M), to calculate a remainder equation si of dividing a polynomial DX(Mi)DY(F)−DY(Mi)DX(F) by I1, to generate a vector w(i)2 that is composed of coefficients of the remainder equation si according to the monomial order described in said algebraic curve parameter file, and to connect the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi; and
basis construction means for inputting said plurality of said vectors v1, v2, . . . into said linear-relation derivation means, to acquire a plurality of vectors m1, m2, . . . as an output, to make an reference to said table for a Groebner basis construction for retrieving a record R2, of which a value of the order field is said value d3, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1, m2, . . . , to select a vector m that accords with a first vector type of said record R2 from among said plurality of said vectors m1, m2, . . . , to generate a polynomial f1 of which the coefficient is a value of a component of the vector m according to the monomial order described in said algebraic curve parameter file, hereinafter, similarly, to generate a polynomial f2 employing a vector that accords with a second vector type, and also a polynomial f3 employing a vector that accords with a third vector type, to obtain a set J={f1,f2,f3} of the polynomial, and to output it as said Groebner basis J.

3. The Jacobian group element adder according to one of claim 1 and claim 2, wherein each of said first and said second ideal reduction means has:
linear-relation derivation means for, for a plurality of vectors v1, v2, . . . , and vn that were input, outputting a plurality of vectors {m1=(m1,1,m1,2, . . . ,m1,n),m2=(m2,1,m2,2, . . . ,m2,n), . . . } representing linear dependence relations Σimj,ivi=0(j=1,2, . . . ) of all of them employing a discharging method;
an ideal type table that is composed of the record number field, the ideal type number field, a reduction order field, and the ideal type field;
a monomial list table that is composed of the record number field, the order field, and the monomial list field;
a table for a Groebner basis construction that is composed of the record number field, the order field, the component number list field, the first vector type field, the second vector type field, and the third vector type field;
ideal type classification means for acquiring said algebraic curve parameter file to make a reference to said ideal type table, to retrieve a record in which the ideal type described in the ideal type field accords with the type of an input ideal J, to acquires a value N of the ideal type number field and a value d of the reduction order field of the retrieved record;
polynomial vector generation means for, when said d is zero, outputting the input ideal J as said Groebner basis J*, when said d is not zero, to make a reference to said monomial list table for retrieving a record R of which a value of the order field is said d, to acquire a list M1, M2, . . . of the monomial described in the monomial list field of said record R, to construct a defining polynomial F employing the coefficient list and the monomial order described in said algebraic curve parameter file, to acquire a first polynomial f, a second polynomial g, and a third polynomial h of the input ideal J, to calculate a remainder equation ri of a product Mi·g of each said monomial Mi and the polynomial g by the polynomials f and F, to generate a vector w(i)1 that is composed of coefficients of the remainder equation ri according to the monomial order described in said algebraic curve parameter file, furthermore to calculate a remainder equation si of a product Mi·h of each said monomial Mi and the polynomial h by the polynomials f and F, to generate a vector w(i)2 that is composed of coefficients of the remainder equation si according to the monomial order described in said algebraic curve parameter file, and to connect the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi;
and basis construction means for inputting said plurality of said vectors v1, v2, . . . into said linear-relation derivation means, to obtain a plurality of vectors m1, m2, . . . as an output, to make a reference to said table for a Groebner basis construction for retrieving a record R2 of which a value of the order field is said value d, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1, m2, . . . , to select a vector m that accords with a first vector type of said record R2 from among said plurality of said vectors m1, m2, . . . , to generate a polynomial f1 of which a coefficient is a value of the component of the vector m according to the monomial order described in said algebraic curve parameter file, hereinafter, similarly, to generate a polynomial f2 employing the vector that accords with a second vector type, and also a polynomial f3 employing the vector that accords with a third vector type, to obtain a set {f1,f2,f3} of the polynomial, and to output it as said Groebner basis J* or J**.

4. A record medium having a program recorded for causing an information processing unit configuring 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


Y3+α0X4+α1XY2+α2X2Y+α3X3+α4Y2+α5XY+α6X2+α7Y+α8X+α9


or


Y2+α0X5+α1X2Y+α2X4+α3XY+α4X3+α5Y+α6X2+α7X+α8


or


Y2+α0X7+α1X3Y+α2X6+α3X2Y+α4X5+α5XY+α6X4+α7Y+α8X3+α9X2+α10X+α11 to perform:

a process of 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;
a process of inputting Groebner bases I1 and I2 of ideals of the coordinate ring of the algebraic curve designated by said algebraic curve parameter file, said Groebner bases representing an element of said Jacobian group;
an ideal composition process of, in the coordinate ring of the algebraic curve designated by said algebraic curve parameter file, performing arithmetic of producing a Groebner basis J of an ideal which is a product of the ideal that the Groebner basis I1 generates, and an ideal that the Groebner basis I2 generates;
a first ideal reduction process of, 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
a second ideal reduction process of, 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, said record medium being readable by said information processing unit.

5. The record medium according to claim 4, said record medium having a program recorded for causing said information processing unit to further perform in said ideal composition process:
a linear-relation derivation process of, for a plurality of vectors v1, v2, . . . , and vn that were input, outputting a plurality of vectors {m1=(m1,1,m2,1, . . . ,m1,n),m2=(m2,1,m2,2, . . . ,m2,n), . . . } representing linear dependence relations Σimj,ivi=0(j=1,2, . . . ) of all of them employing a discharging method;
an ideal type classification process of acquiring said algebraic curve parameter file to make a reference to an ideal type table, which is composed of a record number field, an ideal type number field, an order field, and an ideal type field, for each of Groebner bases I1 and I2 that were input, to retrieve a record in which the ideal type described in the ideal type field accords with the type of an input ideal Ii(i=1,2), and to acquire a value Ni of the ideal type number field and a value di of the order field of the retrieved record;
a monomial vector generation process of calculating a sum d3=d1+d2 of said values d1 and d2 of said order field to make a reference to a monomial list table, which is composed of the record number field, the order field, and a monomial list field, for retrieving a record R of which a value of the order field is said d3, to acquire a list M1, M2, . . . of the monomial described in said monomial list field of said record R, when I1 and I2 are different, to calculate a remainder equation ri of dividing each said monomial Mi by I1, to generate a vector w(i)1 that is composed of coefficients of the remainder equation ri according to the monomial order described in said algebraic curve parameter file, furthermore to calculate a remainder equation si of dividing Mi by I2, to generate a vector w(i)2 that is composed of coefficients of the remainder equation si according to the monomial order described in an algebraic curve parameter file A, to connect the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi, also, when I1 and I2 are equal, to calculate a remainder equation ri of dividing each said monomial Mi by I1, to generate a vector w(i)1 that is composed of coefficients of the remainder equation ri according to the monomial order described in said algebraic curve parameter file, furthermore to construct a defining polynomial F employing the coefficient list and the monomial order described in said algebraic curve parameter file, when a differential of a polynomial M with regard to by its X is expressed by DX(M), and a differential of the polynomial M with regard to by its Y is expressed by DY(M), to calculate a remainder equation si of dividing a polynomial DX(Mi)DY(F)−DY(Mi)DX(F) by I1, to generate a vector w(i)2 that is composed of coefficients of the remainder equation si according to the monomial order described in said algebraic curve parameter file, and to connect the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi; and
a basis construction process of obtaining a plurality of vectors m1, m2, . . . output in said linear-relation derivation process, to make an reference to a table for a Groebner basis construction, which is composed of the record number field, the order field, a component number list field, a first vector type field, a second vector type field, and a third vector type field, for retrieving a record R2, of which a value of the order field is said value d3, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1, m2, . . . , to select a vector m that accords with a first vector type of said record R2 from among said plurality of said vectors m1, m2, . . . , to generate a polynomial f1 of which the coefficient is a value of a component of the vector m according to the monomial order described in said algebraic curve parameter file, hereinafter, similarly, to generate a polynomial f2 employing a vector that accords with a second vector type, and also a polynomial f3 employing a vector that accords with a third vector type, to obtain a set J={f1,f2,f3} of the polynomial, and to output it as said Groebner basis J.

6. The record medium according to one of claim 4 and claim 5, said record medium having a program recorded for causing said information processing to further perform in each of said first and second ideal reduction processes:
a linear-relation derivation process of, for a plurality of vectors v1, v2, . . . , and vn that were input, outputting a plurality of vectors {m1=(m1,1,m1,2, . . . ,m1,n),m2=(m2,1,m2,2, . . . ,m2,n), . . . } representing linear dependence relations Σimj,ivi=0(j=1,2, . . . ) of all of them employing a discharging method;
an ideal type classification process of acquiring said algebraic curve parameter file to make a reference to a ideal type table, which is composed of the record number field, the ideal type number field, a reduction order field, and the ideal type field, to retrieve a record in which the ideal type described in the ideal type field accords with the type of an input ideal J, and to acquire a value N of the ideal type number field and a value d of the reduction order field of the retrieved record;
a polynomial vector generation process of, when said d is zero, outputting the input ideal J as said Groebner basis J*, when said d is not zero, to make a reference to a monomial list table, which is composed of the record number field, the order field, and the monomial list field, for retrieving a record R of which a value of the order field is said d, to acquire a list M1, M2, . . . of the monomial described in the monomial list field of said record R, to construct a defining polynomial F employing the coefficient list and the monomial order described in said algebraic curve parameter file, to acquire a first polynomial f, a second polynomial g, and a third polynomial h of the input ideal J, to calculate a remainder equation ri of a product Mi·g of each said monomial Mi and said polynomial g by the polynomials f and F, to generate a vector w(i)1 that is composed of coefficients of the remainder equation ri according to the monomial order described in said algebraic curve parameter file, furthermore to calculate a remainder equation si of a product Mi·h of each said monomial Mi and the polynomial h by the polynomials f and F, to generate a vector w(i)2 that is composed of coefficients of the remainder equation si according to the monomial order described in said algebraic curve parameter file, and to connect the above-mentioned two vectors w(i)1 and w(i)2 for generating a vector vi; and
a basis construction process of obtaining a plurality of vectors m1, m2, . . . output in said linear-relation derivation process to make a reference to a table for a Groebner basis construction, which is composed of the record number field, the order field, the component number list field, the first vector type field, the second vector type field, and the third vector type field, for retrieving a record R2 of which a value of the order field is said value d, and in which a vector of which the components that correspond to all component numbers described in the component number list field are all zero does not lie in said plurality of said vectors m1, m2, . . . , to select a vector m that accords with a first vector type of said record R2 from among said plurality of said vectors m1, m2, . . . , to generate a polynomial f1 of which a coefficient is a value of the component of the vector m according to the monomial order described in said algebraic curve parameter file, hereinafter, similarly, to generate a polynomial f2 employing the vector that accords with a second vector type, and also a polynomial f3 employing the vector that accords with a third vector type, to obtain a set {f1,f2,f3} of the polynomial, and to output it as said Groebner basis J* or J**.