JP2000321979A - Polynomial arithmetic unit, elliptic curve order calculator, elliptic curve generator, and elliptic curve cryptosystem - Google Patents

Abstract

(57) [Summary] The present invention provides a high-speed polynomial arithmetic device,
Accordingly, an elliptic curve generation device capable of generating a secure elliptic curve at high speed is provided. SOLUTION: A polynomial on a finite field GF (q) (q = p ^ n, p: prime number)
One-variable polynomial residue ring modulo r (X) R = GF (q) [X] / (r (X))
In the above, a polynomial X, f (X) belonging to R is input, and a polynomial X ^ q, f (X) ^ ((q-1) / 2) belonging to R is output. For X, X ^ p, X ^ (2p), X ^
A first power calculator for calculating (3p), ..., X ^ ((d-1) p), and f
A second power calculator for calculating (X) ^ ((q-1) / 2),
The power-of-two calculation means uses a result output from the first power-of-power calculation means.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an encryption technique and an error correction technique as information security techniques, and in particular, to an encryption technique and a digital signature technique realized by using an elliptic curve, and realized by using an elliptic curve. It relates to error correction technology.

[0002]

2. Description of the Related Art The secret communication system is a system for performing communication without leaking communication contents to a person other than a specific communication partner.
The digital signature scheme is a communication scheme that shows the validity of communication contents to a communication partner or proves that the person is the person. This signature scheme uses an encryption scheme called public key encryption. Public key cryptography is a method for easily managing different encryption keys for each communication partner when there are many communication partners.
It is a fundamental technology that is indispensable for communicating with many communication partners. In brief, this is a scheme in which the encryption key and the decryption key are different, and the decryption key is kept secret but the encryption key is made public. There is a discrete logarithm problem that is used as a basis for the security of this public key cryptosystem. The discrete logarithm problem typically includes a problem defined on a finite field and a problem defined on an elliptic curve. This is Neal Koblitz, "A Course in Number
theory and Cryptography ", Springer-Verlag, 1987. The discrete logarithm problem on an elliptic curve is described below.

(Discrete Logarithm Problem on Elliptic Curve) Let E (GF (q)) be an elliptic curve E defined on a finite field GF (q) (q = p ^ n). The base G that can be broken is the base point. At this time, if there is an integer x such that Y = xG for the element Y given E, find x.

[0004] Various decoding methods have been proposed for the discrete logarithm problem on an elliptic curve, and it is necessary to construct an elliptic curve that is safe for them. Elliptic curves that are safe for all existing decryption methods are elliptic curves over the finite field GF (q), whose order is not q-1, q, q + 1 and whose prime factors are large. It is. At this time, the computation time required for decryption is the exponential time related to the largest prime factor of the order. See pages 155 to 156). Therefore, the use of an elliptic curve having a prime order maximizes encryption security. The security of the elliptic curve can be confirmed by examining the order of the elliptic curve.

As a conventional construction method of an elliptic curve, there are (1) a construction method using a CM method, and (2) a construction method using an order calculation algorithm. In (1), the configuration of the elliptic curve is simple, but the elliptic curve cannot be configured at random. This is A.Miyaji, "On Ord
inary Elliptic Curve Cryptosystems ", ASIACRYPT'91, S
pringer-Verlag, 1991, pp. 460-469.
In (2), an elliptic curve can be randomly constructed, but the construction time is long.

(Conventional Example 1) FIG. 4 is a block diagram showing an elliptic curve generator using the order calculation algorithm of Conventional Example 1. (N. Koblitz, "Ellitpic Curve Implementation of Z
ero-Knowledge Blobs ", J. Cryptology, vol. 4, No. 3, 1991,
(See pages 207 to 213). The elliptic curve generation device of Conventional Example 1 includes a random number generation unit 101, an elliptic curve setting unit 102, and an elliptic curve order calculation unit 103. Hereinafter, the operation of Conventional Example 1 will be described. step1: random number generator 101 generates random numbers. step2: Elliptic curve setting unit 102 Sets an elliptic curve for the random numbers generated in step1. step3: Elliptic curve order calculation unit 103 calculates the order of the elliptic curve in step2. step4: Elliptic curve condition determination section 104 The elliptic curve of step2 is determined under given conditions. Only when the given condition is satisfied, the elliptic curve parameters are output. If not, return to step1.

As described above, the configuration method using the order calculation algorithm requires a long calculation time. The place where the most calculation time is required in Conventional Example 1 is the elliptic curve order calculation unit in step 3. One of the algorithms for calculating the order of an elliptic curve
There is Schoof's algorithm. Although this algorithm is composed of polynomial time, it is not a practical calculation time. Sc
hoof's algorithm has been improved as an SEA algorithm by Elkies and Atkin.

(Conventional Example 2) FIG. 5 is a block diagram showing a configuration of an elliptic curve order calculating apparatus based on the SEA algorithm of Conventional Example 2, which is described in R. Lercier, F. Morain, "Counting the number of poi.
nts on elliptic curves over finite fields: strateg
ies performances ", EUROCRYPT'95, Springer-Verlag, 199
It is on pages 5,79-94. The elliptic curve order calculating device of Conventional Example 2 includes an initial value setting unit 201, an elliptic curve order information calculating unit 202, a calculation end determining unit 203, and an elliptic curve order determining unit 204. Hereinafter, the operation of Conventional Example 2 will be described.

Let p be a prime number and q = p ^ n, and the elliptic curve E on GF (q)
Is set as y ^ 2 = x ^ 3 + ax + b. Here, x ^ a indicates x to the power of a. The order to be obtained is m, and t satisfies m = q + 1-t. f (x) = x ^ 3 + ax + b. step1: Initial value setting unit 201 l: = 2. step2: Obtain the elliptic curve order information calculation unit 202 t mod l. At this time, the following is obtained according to the number of linear factors of the factorization in the polynomial ring GF (q) [T] of one variable T of Modular polynomial Φl (T). Modular polynomials are described in R. Schoof, "Counting points on elliptic curve ov
er finite fields ", Journal de Theorie des Nombres d
e Bordeux 7, 1995, pp. 219-254.

Step2-1. When the number of primary factors is 2, t mod l is obtained. Furthermore, by the Isogeny cycle method,
Find t mod l ^ n (n = 2,3, ...). Isogeny cycke method
JMCouveignes, F.Morain, "Schoof's algorithm and iso
geny cycles ", ANTS-I, Lecture Notes in Compute Scien
ce 877, Springer-Verlag, 1994, pages 43-58.

Step 2-2. When the number of primary factors is 1 or l + 1, t mod l is obtained. Furthermore, by the Isogeny cycle method,
Find t mod l ^ n (n = 2,3, ...). At this time, Isogeny cy
Determine whether the cle method is applicable.

Step 2-3. When the number of primary factors is 0, possible values of t mod l are narrowed down from the set [0,1, ..., l-1]. step3: calculation end determination unit 203 l1 ^ (n1) × l2 ^ (n2) × ... × lk ^ (nk) <4 × q ^ (1/2) (l1, l2, ..., lk is a prime number, and returns to step 2 as lk = l) and l: = (the next prime number after l). Otherwise, proceed to the next step 4. step4: Elliptic curve order determination unit 204 The order is determined and output by the match & sort algorithm. The match & sort algorithm is described in R. Lercier, "Algorith
mique des courbes elliptiques dans les corps fini
s ", These, Ecole Polytechnique-LIX, 1997.

The determination in step 3 assumes that t mod lk ^ (nk) is obtained for the small prime lk in step 2. ste
In p2-1 and step2-2, t mod l ^ n (n = 1, 2, 3,...) is obtained, which can be obtained by calculating eigenvalues of a mapping called Frobenius mapping. Specifically, k of the following equation is obtained by using l equal points (X, Y) on the elliptic curve E.

(X ^ q, Y ^ q) = k (X, Y) where k (X, Y) is a k-fold point on the elliptic curve of the point (X, Y),
Y ^ 2 = f (X) = X ^ 3 + aX + b. In the above formula, X is a variable,
A polynomial that is a GF (q) coefficient is calculated by an elliptic curve operation on a one-variable polynomial residue ring for X modulo a certain polynomial.
To find k in the above equation, X ^ q and Y ^ q = Y × Y ^ (q-1) on the left side of the above equation
Need to ask. Therefore, X ^ q and Y ^ (q-1) = f (X) ^
Calculate ((q-1) / 2). These calculations take the most time. It is known that X ^ q is obtained using the following algorithm.

(Conventional Example 3) FIG. 6 is a block diagram showing a configuration of a polynomial operation device of Conventional Example 3. The polynomial operation device of the third conventional example includes a first power calculator 301 and a second power calculator 302. Hereinafter, the operation of Conventional Example 3 will be described.

A polynomial as a modulus is r (X), and its order is d. step1: The first power calculator 301 X ^ p, X ^ (2p), X ^ (3p), ..., X ^ ((d-1) p) mod r (X) are obtained. step2: The second power calculation unit 302 calculates X ^ (p ^ 2), X ^ (p ^ 3), ..., X ^ (p ^ n).

Step 2 utilizes the fact that (g (X)) ^ p = g (X ^ p) for a polynomial g (X) which is a GF (q) coefficient (by DEKnuth, Nakagawa Keisuke Translation, "
Semi-Numerical Algorithm / Arithmetic Operation ", KNUTH 4th Volume, Science, 26
See pages 6 to 267). From this property, X, X ^ of g (X)
X ^ p, X ^ (2p), ..., X where 2, ..., X ^ (d-1) are obtained by the first power calculator
By replacing it with ^ ((d-1) p), (g (X) ^ p) is obtained.

As described above, there is an algorithm for obtaining X ^ q, but since no effective algorithm for obtaining Y ^ (q-1) has been published, calculation using only conventional power multiplication is performed. However, since the power multiplication requires a large amount of calculation, there is a problem that the calculation amount of the SEA algorithm increases.

[0019]

In an elliptic curve cryptosystem, it is important to generate secure elliptic curve parameters. For this purpose, an elliptic curve generator is used.

In an elliptic curve generator using an order calculation algorithm, the execution time of the order calculation unit is long. SEA algorithm (prior art
In 2), there is a disadvantage that the amount of calculation of the power multiplication on the polynomial remainder ring is large.

The present invention has been made in view of the above-mentioned problems in the prior art, and shortens the calculation time of the order multiplication of an elliptic curve by shortening the calculation time of the power multiplication on a polynomial ring. Accordingly, an object of the present invention is to provide a secure public key encryption and signature scheme.

[0022]

According to the first aspect of the present invention, there is provided an extended field GF (q) (q = p ^ n) of a finite field GF (p) given in advance.
In the above one-variable polynomial remainder ring R = GF (q) [X] / (r (X)) modulo the given polynomial r (X) (degree d), the polynomials X, f ( X) as input and polynomials X ^ q, f (X) ^ belonging to R
A polynomial operation device that outputs ((q-1) / 2), wherein for the polynomial X, X ^ p, X ^ (2p), X ^ (3p), ..., X ^ (( d-1)
p), and a second power calculation means for calculating f (X) ^ ((q-1) / 2), wherein the second power calculation means comprises the first power calculation means. It is characterized by using the result output from the 1 power calculation means (where p ^ n indicates p raised to the nth power).

According to a second aspect of the present invention, in the first aspect, the second power calculating means performs an intermediate calculation for calculating f (X) ^ ((p-1) / 2) and then performs the first power calculation. Using the result output from the power calculator, f (X) ^ ((p ^ 2-1) / 2) = (f (X) ^ ((p-1) / 2)) ^ p × f ( X) ^
((p-1) / 2), f (X) ^ ((p ^ 3-1) / 2) = (f (X) ^ ((p ^ 2-1) / 2)) ^ p ×
f (X) ^ ((p-1) / 2), ..., f (X) ^ ((p ^ n-1) / 2) = (f (X) ^ ((p ^ (n
-1) -1) / 2) ^ p × f (X) ^ ((p-1) / 2).

According to a third aspect of the present invention, an elliptic curve on an extended field GF (q) (q = p ^ n) of a given finite field GF (p) is input and the order of the elliptic curve is output. An elliptic curve order calculating device, comprising: an initial value setting unit for setting a predetermined initial value; an elliptic curve order information calculating unit for obtaining order information; and an elliptic curve order information calculating unit. An elliptic curve order determining unit that determines an order of the elliptic curve using information output from the elliptic curve order information calculating unit; The unit includes the polynomial operation device according to claim 1.

According to a fourth aspect of the present invention, an elliptic curve on an extended field GF (q) (q = p ^ n) of a predetermined finite field GF (p) is input and the order of the elliptic curve is output. An elliptic curve order calculating device, comprising: an initial value setting unit for setting a predetermined initial value; an elliptic curve order information calculating unit for obtaining order information; and an elliptic curve order information calculating unit. An elliptic curve order determining unit that determines an order of the elliptic curve using information output from the elliptic curve order information calculating unit; The section includes the polynomial operation device according to claim 2.

According to a fifth aspect of the present invention, an elliptic curve defined on an extended field GF (q) (q = p ^ n) of a predetermined finite field GF (p) and satisfying a predetermined condition is output. An elliptic curve setting unit for setting an elliptic curve based on a previously given elliptic curve setting value, and an elliptic curve order calculation for calculating an order of the elliptic curve on the finite field Unit, comprising an elliptic curve condition determination unit that determines the elliptic curve set by the elliptic curve setting unit under the given condition, wherein the elliptic curve order calculation unit is the elliptic curve order according to claim 3. It has a computing device.

According to a sixth aspect of the present invention, an elliptic curve defined on an extended field GF (q) (q = p ^ n) of a given finite field GF (p) and satisfying a given condition is output. An elliptic curve setting unit for setting an elliptic curve based on a previously given elliptic curve setting value, and an elliptic curve order calculation for calculating an order of the elliptic curve on the finite field And an elliptic curve condition determining unit that determines the elliptic curve set by the elliptic curve setting unit under the given condition, wherein the elliptic curve order calculating unit is the elliptic curve order according to claim 4. It has a computing device.

The invention according to claim 7 uses an elliptic curve defined on an extension field GF (q) (q = p ^ n) of a given finite field GF (p) and satisfying a given condition. An elliptic curve cryptosystem, comprising: an elliptic curve setting unit that sets an elliptic curve based on a given elliptic curve setting value; and an elliptic curve order calculating unit that calculates an order of the elliptic curve on the finite field. And an elliptic curve condition determining unit that determines the elliptic curve set by the elliptic curve setting unit under the given condition, wherein the elliptic curve order calculating unit is configured to calculate the elliptic curve order according to claim 3. It is generated by an elliptic curve generation device having the device.

The invention according to claim 8 uses an elliptic curve defined on an extension field GF (q) (q = p ^ n) of a given finite field GF (p) and satisfying a given condition. An elliptic curve cryptosystem, comprising: an elliptic curve setting unit that sets an elliptic curve based on a given elliptic curve setting value; and an elliptic curve order calculating unit that calculates an order of the elliptic curve on the finite field. And an elliptic curve condition determining unit that determines the elliptic curve set by the elliptic curve setting unit under the given condition, wherein the elliptic curve order calculating unit is configured to calculate the elliptic curve order according to claim 4. It is generated by an elliptic curve generation device having the device.

[0030]

FIG. 1 is a block diagram showing a configuration of a polynomial operation device according to this embodiment.

This polynomial operation device realizes the exponentiation operation on the polynomial remainder ring of the SEA algorithm of the conventional example 2, and converts GF (q) (q = p ^ n, p: prime number) into a finite field, Let X be a variable and G
Modulo a given r (X) (order d) which is the F (q) coefficient 1
In a variable polynomial residue ring R = GF (q) [X] / (r (X)), input the polynomials X and f (X) belonging to R and input X ^ q and f (X) ^ ((q-1 ) / 2) is output.

The polynomial arithmetic unit 40 includes a first power calculating unit 401
, A second power calculator 403, and a fourth power calculator 404.

The first power calculation unit 401 receives X belonging to R as an input, and X ^ p, X ^ (2p), X ^ (3p), ..., X ^ ((d-1) p) And calculate
Output.

The second power calculator 402 calculates the X belonging to R and the X ^ p, X ^ (2p),..., X ^ ((d-1) output from the first power calculator 401. p)
And X ^ q is output.

The third exponentiation calculation unit 404 calculates f (X) belonging to R and the first
X ^ p, X ^ (2p), ..., X ^ ((d-1) output from the power calculator 401
Using p) as input, calculate f (X) ^ ((q-1) / 2).

FIG. 2 is a block diagram showing the configuration of the second power calculator 402. As shown in FIG.

The second exponentiation calculation unit 402 calculates X belonging to R and X ^ p, X ^ (2p),..., X ^ ((d-1) output from the first power exponentiation calculation unit 401. p)
Is a polynomial operation device that receives X as an input and outputs X ^ q.

The second power calculating unit 402 includes an initial value setting unit 4021
And a polynomial conversion unit 4022 and an end determination unit 4023.

The initial value setting unit 4021 determines that c = 1 (c is a counter),
Set g (X) = X ^ p.

The polynomial converter 4022 converts g (X) and X ^ p, X ^ (2p),..., X ^ ((d-1) p) output from the first power calculator 401. As an input, calculate (g (X)) ^ p and replace it with g (X).

The polynomial conversion unit 4022 performs the following calculation.

(G (X)) ^ p = g0 + g1X ^ p + g2X ^ (2p) + ... + g (d-1) X
^ ((d-1) p) where g (X) = g0 + g1X + g2X ^ 2 + ... + g (d-1) X ^ (d-1) (g0, g
1, ..., g (d-1) are assumed to be GF (q)).

The termination determining unit 4023 determines whether or not c = n.

The operation of the second power calculator 402 will be described below.

The initial value calculation unit 4021 has a counter c = 1, g (X) = X
^ p, and g (X) and the first power calculation unit 4
Input X ^ p, X ^ (2p), ..., X ^ ((d-1) p) output from 01. The polynomial conversion unit 4022 calculates (g (X)) ^ p and resets it to g (X). The end determination unit 4023 determines whether or not c = n, and if c = n, outputs g (X) and ends. Otherwise, c + 1 is changed to c, and the process returns to the polynomial conversion unit 4022.

FIG. 3 is a block diagram showing a configuration of the third power calculator 403. As shown in FIG.

The third exponentiation calculation unit 403 calculates f (X) belonging to R and the first
X ^ p, X ^ (2p), ..., X ^ ((d-1) output from the power calculator 401
This is a polynomial arithmetic unit that calculates f (X) ^ ((q-1) / 2) using p) as an input.

The third power calculator 403 includes an intermediate calculator 4031,
An initial value setting unit 4032, a polynomial conversion unit 4033, a polynomial multiplication unit 4034, and an end determination unit 4035 are provided.

The intermediate calculation unit 4031 calculates f (X) ^ ((p-1) / 2).

The initial value setting unit 4032 determines that c = 1, g (X) = f (X) ^ ((p
Set to -1) / 2).

The polynomial converter 4033 is the same as the polynomial converter 4022.

The polynomial multiplication unit 4034 calculates g (X) and f (X) ^ ((p-1) /
2) multiply.

The end determination unit 4035 determines whether c = n.

The operation of the third power calculator 403 will be described below.

The intermediate calculation unit 4031 calculates and outputs f (X) ^ ((p-1) / 2). The initial value calculation unit 4032 has a counter c = 1, g (X)
= f (X) ^ ((p-1) / 2), and the polynomial converter 4033 outputs g (X) and X ^ p, X ^ (2p), output from the first power calculator 401. ..., X ^ ((d
-1) Enter p). The polynomial conversion unit 4033 calculates (g (X)) ^ p and updates it to g (X). In the polynomial multiplication unit 4034, g (X) and
Multiply by f (X) ^ ((p-1) / 2) and change to g (X). The end determination unit 4035 determines whether or not c = n, and if c = n, outputs g (X) and ends. Otherwise, c + 1 is changed to c, and the process returns to the polynomial conversion unit 4033.

The operation of the polynomial arithmetic unit 40 will be described below.

When the present apparatus is started, first, the first power calculator 401 calculates X ^ p, X ^ (2p), X ^ (3p), ..., X ^ ((d-1) p ) Is calculated and output. The second power calculation unit 402 includes a first power calculation unit 401
X ^ p, X ^ (2p), X ^ (3p), ..., X ^ ((d-1) p) output from
X and q are input, X ^ q is calculated and output. Next, the third power calculation unit 403 outputs X ^ p, X ^ (2
p), X ^ (3p), ..., X ^ ((d-1) p) and X, and f (X) ^ ((q
-1) / 2) and outputs X ^ q and f (X) ^ ((q-1) / 2).

The amount of calculation in this example will be described. This embodiment is used in the SEA algorithm of Conventional Example 2. The following is a comparison with the conventional method.

The calculation amount of the polynomial multiplication is PMul. In the conventional method, f (X) ^ ((q-1) / 2) is obtained by simply raising a power. In this case, the calculation amount is 3/2 | q | × PMul (| q | is the number of bits of q). On the other hand, in the present embodiment, the calculation amount of the intermediate calculation unit 4031 is 3/2 | p | × PMul (| p | is p
The number of bits of the polynomial conversion unit 4033 is 1 × PM
ul, the calculation amount of the polynomial multiplication unit 4034 is 1 × PMul, and the polynomial conversion unit 4043 and the polynomial multiplication unit 4044 repeat n−1 times, so that the total calculation amount is (3/2 | p | + 2 × n-2) × PMul. |
For q | = 160, | p | = 32, n = 5, the conventional method uses f (X) ^
The calculation amount for calculating ((q−1) / 2) is 240 × PMul, and in the first embodiment, it is 56 × PMul. Therefore, f (X) ^ ((p-1)
The effect of a polynomial arithmetic device that can calculate (/ 2) at high speed is significant. Note that an order calculation device, an elliptic curve generation device, and an elliptic curve cryptosystem using this embodiment can be realized.

[0060]

As described above, the present invention has been made in view of the problems in the conventional example, and in the SEA algorithm, the calculation time of the exponentiation operation on the polynomial ring has been reduced.

As described above, it is possible to provide an elliptic curve generation device that enables a high-speed and secure encryption method and signature method, and its practical value is great.

[Brief description of the drawings]

FIG. 1 is a block diagram of a polynomial arithmetic device according to an embodiment of the present invention.

FIG. 2 is a block diagram showing a configuration of a second power calculator 402 according to the embodiment of the present invention.

FIG. 3 is a block diagram showing a configuration of a third power calculator 403 according to the embodiment of the present invention.

FIG. 4 is a block diagram of an elliptic curve generation device according to Conventional Example 1.

FIG. 5 is a block diagram of an elliptic curve order calculating apparatus using the SEA algorithm according to the second conventional example

FIG. 6 is a block diagram of a polynomial operation device of Conventional Example 3.

[Explanation of symbols]

Reference Signs List 10 Elliptic curve generator of Conventional Example 1 101 Random number generator 102 Elliptic curve setting unit 103 Elliptic curve order calculating unit 104 Elliptic curve condition determining unit 20 Elliptic curve order calculating device by SEA algorithm of Conventional Example 2 201 Initial value setting unit Reference Signs List 202 Elliptic curve order information calculation unit 203 Calculation end determination unit 204 Elliptic curve order determination unit 30 Polynomial operation device of Conventional Example 3 301 First power calculation unit 302 Second power calculation unit 40 According to the first embodiment of the present invention. Polynomial arithmetic unit 401 First power calculation unit 402 Second power calculation unit 4021 Initial value setting unit 4022 Polynomial conversion unit 4023 End determination unit 403 Third power calculation unit 4031 Intermediate calculation unit 4032 Initial value setting unit 4033 Polynomial conversion unit 4034 polynomial multiplication unit 4035 end judgment unit

Claims (8)

[Claims] 1. An extension field GF of a finite field GF (p) given in advance
(q) (q = p ^ n) one-variable polynomial remainder ring R = GF (q) [X] / (r (X)) modulo a given polynomial r (X) (degree d) At
A polynomial computing device that receives a polynomial X and f (X) belonging to R as inputs and outputs a polynomial X ^ q and f (X) ^ ((q-1) / 2) belonging to R, wherein the polynomial X X ^ p, X ^ (2p), X ^ (3p), ..., X ^
a first power calculating means for calculating ((d-1) p), and f (X) ^ ((q-1) /
A second power calculation means for calculating 2), wherein the second power calculation means uses a result output from the first power calculation means.
(However, p ^ n indicates p raised to the nth power). 2. The method according to claim 1, wherein the second exponentiation calculating means calculates f (X) ^ ((p−1) /
After performing the intermediate calculation for calculating 2), using the result output from the first power calculation means, f (X) ^ ((p ^ 2-1) / 2) = (f (X) ^ ((p-1) / 2)) ^ p × f (X) ^ ((p-1) / 2) f (X) ^ ((p ^ 3-1) / 2) = (f (X) ^ ((p ^ 2-1) / 2)) ^ p × f (X) ^ ((p-1) / 2) .... f (X) ^ ((p ^ n-1) / 2) = (f (X) ^ ((p ^ (n-1) -1) / 2) ^ p × f (X) ^ ((p-1) / 2) The polynomial arithmetic device according to claim 1. 3. An extension field GF of a finite field GF (p) given in advance
(q) An elliptic curve order calculation device that receives an elliptic curve on (q = p ^ n) and outputs the order of the elliptic curve, and sets an initial value given in advance. And an elliptic curve order information calculation unit that obtains order information, a calculation end determination unit that performs an end determination of the elliptic curve order information calculation unit, and information output from the elliptic curve order information calculation unit. An elliptic curve order determining unit that determines the order of the elliptic curve by using the elliptic curve order information calculation unit, wherein the elliptic curve order information includes the polynomial operation device according to claim 1. Computing device. 4. An extension field GF of a finite field GF (p) given in advance
(q) An elliptic curve order calculation device that receives an elliptic curve on (q = p ^ n) and outputs the order of the elliptic curve, and sets an initial value given in advance. And an elliptic curve order information calculation unit that obtains order information, a calculation end determination unit that performs an end determination of the elliptic curve order information calculation unit, and information output from the elliptic curve order information calculation unit. An elliptic curve order determining unit that determines the order of the elliptic curve using the elliptic curve order information calculating unit, wherein the elliptic curve order information includes the polynomial arithmetic device according to claim 2. Computing device. 5. An extension field GF of a finite field GF (p) given in advance
(q) An elliptic curve generator that outputs an elliptic curve defined on (q = p ^ n) that satisfies a predetermined condition, and sets an elliptic curve based on a predetermined elliptic curve set value. An elliptic curve setting unit, an elliptic curve order calculating unit for calculating the order of the elliptic curve on the finite field, and an elliptic curve determined by the elliptic curve setting unit under the given conditions. An elliptic curve generation device, comprising: a condition determination unit; and the elliptic curve order calculation unit includes the elliptic curve order calculation device according to claim 3. 6. An extension field GF of a finite field GF (p) given in advance
(q) (q = p ^ n) is an elliptic curve generator that outputs an elliptic curve that satisfies a given condition, based on a given elliptic curve set value, An elliptic curve setting unit for setting, an elliptic curve order calculating unit for calculating the order of the elliptic curve on the finite field, and an ellipse for determining the elliptic curve set by the elliptic curve setting unit under the given conditions. 5. An elliptic curve generation device, comprising: a curve condition determination unit; wherein the elliptic curve order calculation unit includes the elliptic curve order calculation device according to claim 4. 7. An extension field GF of a finite field GF (p) given in advance
(q) An elliptic curve cryptosystem using an elliptic curve defined on (q = p ^ n) that satisfies a predetermined condition, and sets an elliptic curve based on a predetermined elliptic curve set value. An elliptic curve setting unit, an elliptic curve order calculating unit for calculating the order of the elliptic curve on the finite field, and an elliptic curve determined by the elliptic curve setting unit under the given conditions. 4. An elliptic curve cryptosystem, comprising: a condition determining unit; and wherein the elliptic curve order calculating unit is generated by an elliptic curve generating device including the elliptic curve order calculating device according to claim 3. 8. An extension field GF of a given finite field GF (p)
(q) An elliptic curve cryptosystem using an elliptic curve defined on (q = p ^ n) that satisfies a predetermined condition, and sets an elliptic curve based on a predetermined elliptic curve set value. An elliptic curve setting unit, an elliptic curve order calculating unit for calculating the order of the elliptic curve on the finite field, and an elliptic curve determined by the elliptic curve setting unit under the given conditions. 5. An elliptic curve cryptosystem, comprising: a condition determining unit; and wherein the elliptic curve order calculating unit is generated by an elliptic curve generating device having the elliptic curve order calculating device according to claim 4.