Patent ID: 8300808

Claim:
An arithmetic operation method for exponentiation wherein an exponentiation A n of an element A in an extension field of F p m of characteristic p and extension degree m, using an exponent n in p-adic representation n = ∑ i = 0 s ⁢ n i ⁢ p i , 0 ≤ n i ≤ p , s = ⌊ log p ⁢ n ⌋ [ E1 ] is represented by the Frobenius map as A n = ∏ i = 0 s ⁢ φ i ⁡ ( A n i ) , [ E2 ] the arithmetic operation method for exponentiation comprising the steps of: configuring an electronic computer to perform the functions of: putting 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, specifying coefficient of the minimum degree by factoring out each term in each tuple with minimum degree, and setting for each column temporary data having an index which indicates whether a value is present at the same column in each tuple in the case where exponentiation of the element A with an exponent of the coefficient is performed with this coefficient being represented in p-adic notation; specifying a value of the temporary data using a multiplier in a column at which a value is present in the temporary data; and setting a result of multiplication between the predetermined temporary data as a result of exponentiation with an exponent of the coefficient in each tuple.