Arithmetic operation method and arithmetic operation device

An arithmetic operation method for scalar multiplication wherein, denoting a m-th extension field of a finite field Fp of characteristic p as Fpm, the total number of rational points as #E(Fpm), and point at infinity as O, an elliptic curve over a finite field Fp is represented as the following expression,

• E(x,y)=x3+ax+b−y2=0,a,bεp [E3]
• an arbitrary rational point A satisfies the following expression,
• [#E(pm)]A= [E4]
• and a scalar part [n] is performed σ-adic expansion represented as
• [
• n
• ]
• ⁢
• A
• =
• ∑
• i
• =
• 0
• s
• ⁢
• {
• ψ
• i
• ⁡
• (
• [
• n
• i
• ]
• ⁢
• A
• )
• }
• ,
• [
• E5
• ]
• the arithmetic operation method for scalar multiplication characterized by comprising the steps of:
• configuring an electronic computer to perform the functions of:
• putting together, with respect to i,
• a term of map φ with predetermined degree and a term of map φ having a degree higher than the predetermined degree by one degree or plural terms of map φ having a degree higher than the predetermined degree by more than one degree into a tuple,
• dividing map F into a plurality of tuples, and specifying a coefficient of minimum degree by factoring each term in each tuple;
• setting for each column temporary data having an index which indicates whether or not a value is present at the same column in φ-adic representation in each tuple in the case where an addition of the element A is performed with the coefficient being in φ-adic representation;
• and
• specifying each [ni]A in φ-adic representation which constitutes said each coefficient by results of additions between the temporary data.

An arithmetic operation method wherein, in the case where there exists a plurality of different elements Y and each of the elements Y is represented by tuples in which a plurality of different elements X are combined with an operator, said each element Y is calculated by an electronic computer, the arithmetic operation method comprising the steps of:

• configuring the electronic computer to perform the functions of:
• associating each element X with said each element Y by setting said each element X, wherein each element Y is represented by tuples in which a plurality of different elements X are combined with an operator, the operator being multiplication for exponentiation and addition for scalar multiplication;
• setting temporary data, including indices, a number of indices being based on a number of tuples, and each of the indices indicates whether or not a value is present in each tuple corresponding to each of the plurality of different elements Y, wherein said each element Y has an identical element X for each said element X and representing said each element Y by the temporary data combined with the operator;
• in the case where there is a combination of temporary data which is common in plurality of elements Y in temporary data contained in said each element Y,
• setting new temporary data by combining the common temporary data;
• and
• calculating each element Y consisting of said each tuple using the new temporary data.

An arithmetic operation device for exponentiation wherein an exponentiation An of an element A in an extension field Fpm of characteristic p and extension degree m, using exponent n in p-adic representation

• n
• =
• ∑
• i
• =
• 0
• s
• ⁢
• n
• i
• ⁢
• p
• i
• ,
• 0
• ≤
• n
• i
• ≤
• p
• ,
• s
• =
• ⌊
• log
• p
• ⁢
• n
• ⌋
• [
• E11
• ]
• is represented by the Frobenius map as
• A
• n
• =
• ∏
• i
• =
• 0
• s
• ⁢
• φ
• i
• ⁡
• (
• A
• n
• i
• )
• [
• E12
• ]
• and there is put together, with respect to the exponent n, a term of p having predetermined degree and a term of p having degree higher than the degree by one degree or a plurality of terms of p having degree higher than the degree by more than one degree into a tuple, dividing the exponent n into a plurality of tuples, factoring out each term in each tuple with minimum degree, specifying coefficient of the minimum degree, the device comprising:
• a memory part which is configured to store a value of temporary data which, in the case where exponentiation of the element A with an exponent of the coefficient is performed, by setting for each column temporary data having an index which indicates whether a value is present at the same column in each tuple, is specified using a multiplier in a column at which a value is present in the temporary data;
• and
• a memory part which is configured to store a result of multiplication between the said predetermined temporary data as a result of exponentiation with an exponent of the coefficient in each tuple.

An arithmetic operation device for scalar multiplication wherein, denoting a m-th extension field of a finite field Fp of characteristic p as Fpm, the total number of rational points as #E(Fpm), and point at infinity as O, an elliptic curve over a finite field Fp is represented as the following expression,

• E(x,y)=x3+ax+b−y2=0,a,bεp [E13]
• an arbitrary rational point A satisfies the following expression,
• [#E(pm)]A= [E14]
• and a scalar part [n] is performed φ-adic expansion represented as
• [
• n
• ]
• ⁢
• A
• =
• ∑
• i
• =
• 0
• s
• ⁢
• {
• ψ
• i
• ⁡
• (
• [
• n
• i
• ]
• ⁢
• A
• )
• }
• ,
• [
• E15
• ]
• the arithmetic operation device having an arithmetic operation circuit for scalar multiplication being configured for:
• putting together, with respect to i, a term of map φ with predetermined degree and a term of map φ having a degree higher than the predetermined degree by one degree or plural terms of map φ having a degree higher than the predetermined degree by more than one degree into a tuple;
• dividing map F into a plurality of tuples;
• specifying a coefficient of minimum degree by factoring out each term in each tuple;
• setting for each column temporary data having an index which indicates whether or not a value is present at the same column in φ-adic representation in each tuple in the case where an addition of the element A is performed with the coefficient being in φ-adic representation;
• and
• specifying each [ni]A in φ-adic representation which constitutes said each coefficient by results of additions between the temporary data.