(57)【要約】      （修正有）【課題】小さいコストで代数的トーラスの元に対する冪乗演算ができる演算装置を提供する。【解決手段】演算装置は、入力部と、冪乗部とを備える。入力部は、有限体をＭ次（Ｍは２以上の整数）の多項式で拡大したＭ次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力する。冪乗部は、代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表されたＭ次拡大体の元に対してＮ乗（Ｎは２以上の整数）するための演算式に基づいて、入力した代数的トーラスの元に対してＮ乗演算する。【選択図】図１
2014219597.tif 000002
【特許請求の範囲】
【請求項１】
有限体をＭ次（Ｍは２以上の整数）の多項式で拡大したＭ次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力する入力部と、
前記代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された前記Ｍ次拡大体の元に対してＮ乗（Ｎは２以上の整数）するための演算式に基づいて、入力した前記代数的トーラスの元に対してＮ乗演算する冪乗部と、
を備える演算装置。
【請求項２】
前記入力部は、有限体を二次多項式で拡大した二次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力し、
前記冪乗部は、前記代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された前記二次拡大体の元に対して二乗するための演算式に基づいて、入力した前記代数的トーラスの元に対して二乗演算する
請求項１に記載の演算装置。
【請求項３】
ｉを変数、ｂを前記有限体に含まれる元とした場合、前記二次多項式は、ｉ２−ｂであり、
前記二次拡大体の元をｇ、前記有限体の元の位数をｑとした場合、前記代数的トーラスの元の成立条件を表す式は、ｇｑ＋１＝１である
請求項２に記載の演算装置。
【請求項４】
入力した前記代数的トーラスの元の０次項の係数をｇ０、１次項の係数をｇ１とした場合、前記冪乗部は、下記式（１）を演算する
【数１】
2014219597.tif 000081
請求項３に記載の演算装置。
【請求項５】
前記入力部は、有限体を三次多項式で拡大した三次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力し、
前記冪乗部は、前記代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された前記三次拡大体の元に対して三乗するための演算式に基づいて、入力した前記代数的トーラスの元に対して三乗演算する
請求項１に記載の演算装置。
【請求項６】
ｔを変数、ｓを前記有限体に含まれる値とした場合、前記三次多項式は、ｔ３−ｓであり、
前記三次拡大体の元をｇ、前記有限体の元の位数をｑとした場合、前記代数的トーラスの元の成立条件を表す式は、ｇｑ＾２＋ｑ＋１＝１である
請求項５に記載の演算装置。
【請求項７】
入力した前記代数的トーラスの元の０次項の係数をｇ０、１次項の係数をｇ１、２次項の係数をｇ２とした場合、前記冪乗部は、下記式（２）を演算する
【数２】
2014219597.tif 000082
請求項６に記載の演算装置。
【請求項８】
前記入力部は、有限体を十次多項式で拡大した十次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力し、
前記冪乗部は、前記代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された前記十次拡大体の元に対して三乗するための演算式に基づいて、入力した前記代数的トーラスの元に対して三乗演算する
請求項１に記載の演算装置。
【請求項９】
ｖを変数とした場合、前記十次多項式は、ｖ１０＋ｖ９＋ｖ８＋ｖ７＋ｖ６＋ｖ５＋ｖ４＋ｖ３＋ｖ２＋ｖ＋１であり、
前記十次拡大体の元をｇ、前記有限体の元の位数をｑとした場合、前記代数的トーラスの元の成立条件を表す式は、ｇｑ＾４−ｑ＾３＋ｑ＾２−ｑ＋１＝１である
請求項８に記載の演算装置。
【請求項１０】
コンピュータにより、有限体をＭ次（Ｍは２以上の整数）の多項式で拡大したＭ次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力する入力ステップと、
コンピュータにより、前記代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された前記Ｍ次拡大体の元に対してＮ乗（Ｎは２以上の整数）するための演算式に基づいて、入力した前記代数的トーラスの元に対してＮ乗演算する冪乗ステップと、
を含む演算方法。
【請求項１１】
有限体をＭ次（Ｍは２以上の整数）の多項式で拡大したＭ次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力する入力ステップと、
前記代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された前記Ｍ次拡大体の元に対してＮ乗（Ｎは２以上の整数）するための演算式に基づいて、入力した前記代数的トーラスの元に対してＮ乗演算を実行する冪乗ステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、有限体の元の冪乗を演算する演算装置、演算方法およびプログラムに関する。
【背景技術】
【０００２】
公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる集合を用いることにより、公開鍵サイズおよび暗号文サイズ等を圧縮する方法が提案されている。また、ペアリングを用いた暗号プロトコルが提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】K.Rubin  and  A.Silverberg，  “Torus-Based  Cryptography”,  CRYPTO  2003,  LNCS  2729,  349-365,  2003.
【非特許文献２】D.Boneh,  B.Lynn  and  H.Shacham.  “Short  signatures  from  the  Weil  pairing”,  Asiacrypt  2001,  LNCS  2248,  514-532,  2001.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、代数的トーラスを用いた暗号化処理およびペアリング暗号処理では、代数的トーラスの元に対する冪乗演算が行われる。このため、代数的トーラスの元に対する冪乗演算の演算コストを小さくすることが望まれる。
【課題を解決するための手段】
【０００５】
実施形態の演算装置は、入力部と、冪乗部とを備える。入力部は、有限体をＭ次（Ｍは２以上の整数）の多項式で拡大したＭ次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力する。冪乗部は、代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表されたＭ次拡大体の元に対してＮ乗（Ｎは２以上の整数）するための演算式に基づいて、入力した代数的トーラスの元に対してＮ乗演算する。
【図面の簡単な説明】
【０００６】
【図１】第１実施形態にかかる演算装置の構成図。
【図２】第２実施形態にかかる演算装置の構成図。
【図３】第３実施形態にかかる演算装置の構成図。
【図４】演算装置のハードウェア構成図。
【発明を実施するための形態】
【０００７】
以下、本実施形態にかかる演算装置を説明する。本実施形態にかかる演算装置は、一例として、代数的トーラス暗号およびペアリング暗号等の処理に用いられる。
【０００８】
（第１実施形態）
図１は、第１実施形態にかかる演算装置１０の構成を示す。演算装置１０は、代数的トーラスの元の二乗を計算して出力する。
【０００９】
演算装置１０は、入力部１１と、冪乗部１２とを備える。入力部１１は、有限体を二次多項式で拡大した二次拡大体の元から選択された代数的トーラスの元を入力する。
【００１０】
ここで、代数的トーラスの元は、基礎体を拡大した拡大体の元のうちの部分体に含まれない元である。代数的トーラスの元の乗算は、有限体の乗算と同様の操作により実行される。
【００１１】
また、入力部１１は、代数的トーラスの元をベクトル表現の形式で入力する。具体的には、二次拡大体の元ｇは、ｇ＝ｇ０＋ｇ１×ｉといった変数ｉの１次式で表すことができる。入力部１１は、このように表した場合における、０次項の係数ｇ０および１次項の係数ｇ１を入力する。すなわち、例えば、入力部１１は、代数的トーラスの元を多項式の係数の形式で入力する。
【００１２】
冪乗部１２は、予め設定された演算式で、入力した代数的トーラスの元に対して二乗演算をする。そして、冪乗部１２は、二乗演算結果をベクトル表現の形式で出力する。本例においては、冪乗部１２は、二乗演算結果ｇ２を変数ｉの１次式で表した場合における、０次項の係数ｇｘ０および１次項の係数ｇｘ１を出力する。
【００１３】
ここで、冪乗部１２は、代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された二次拡大体の元に対して二乗するための演算式に基づいて、入力した代数的トーラスの元に対して二乗演算する。
【００１４】
具体的には、ｉを変数、ｂを有限体に含まれる元とし、有限体を拡大するための二次多項式をｉ２−ｂとする場合、冪乗部１２は、下記の式（１）の演算式を実行して、入力された代数的トーラスの元の二乗ｇ２を計算する。
【数１】
2014219597.tif 000003
【００１５】
演算装置１０は、このような演算式を用いることにより、通常の演算式を用いる場合よりも小さいコストで二乗演算をすることができる。
【００１６】
式（１）の演算式は、すなわち、二次拡大体の元に対して二乗するための演算式、ベクトル表現の形式で表された二次拡大体の元に対する二乗の演算式に、代数的トーラスの元の成立条件を表す式に二次拡大体の元を表す式およびフロベニウス（Ｆｒｏｂｅｎｉｕｓ）共役元を表す式を代入して導き出した０次項の式を加えることにより、導き出される。以下、具体的に冪乗部１２がこのような式（１）の演算式を用いて、代数的トーラスの元の二乗演算が可能な理由を説明する。
【００１７】
基礎体Ｆｑを二次拡大するための多項式を式（１１）とする。ｉは、変数を表し、ｂは基礎体Ｆｑから選択された任意の元である。また、ｑは、基礎体Ｆｑの位数を表す。
【数２】
2014219597.tif 000004
【００１８】
この場合、基礎体Ｆｑの二次拡大体Ｆｑ＾２は、式（１２）で表される。なお、“Ｘ＾Ｙ”は、ＸのＹ乗を表す。
【数３】
2014219597.tif 000005
【００１９】
また、二次拡大体Ｆｑ＾２の元ｇは、式（１３）で表される。また、二次拡大体Ｆｑ＾２のフロベニウス共役元ｇｑ式は、式（１４）で表される。
【数４】
2014219597.tif 000006
【００２０】
ここで、代数的トーラスの元は、二次拡大体Ｆｑ＾２のうち部分体に含まれない元である。このことから、式（１１）で拡大された二次拡大体Ｆｑ＾２の代数的トーラスの元は、式（１５）且つ式（１６）を満たす。すなわち、式（１５）および式（１６）は、代数的トーラスの元の成立条件を表す式である。
【数５】
2014219597.tif 000007
【００２１】
式（１６）は、式（１７）に変形される。
【数６】
2014219597.tif 000008
【００２２】
式（１７）に二次拡大体Ｆｑ＾２の元ｇを表す式（１３）およびフロベニウス共役元ｇｑを表す式（１４）を代入する。そうすると、式（１７）は、式（１８）となる。
【数７】
2014219597.tif 000009
【００２３】
式（１８）を展開すると、式（１９）となる。
【数８】
2014219597.tif 000010
【００２４】
式（１１）の多項式の解からｉ２＝ｂといえるので、式（１９）は式（２０）に変形される。
【数９】
2014219597.tif 000011
【００２５】
式（２０）の右辺の値を左辺に移行させると、式（２１）となる。
【数１０】
2014219597.tif 000012
【００２６】
このように、代数的トーラスの元の成立条件を表す式に二次拡大体Ｆｑ＾２の元ｇおよびフロベニウス共役元ｇｑを表す式を代入することにより、式（２１）のような変数ｉの０次項の式を導き出すことができる。
【００２７】
一方、ベクトル表現の形式で表された二次拡大体Ｆｑ＾２の元ｇに対する二乗の演算式は、式（２２）のように表される。
【数１１】
2014219597.tif 000013
【００２８】
式（１１）の多項式の解からｉ２＝ｂといえるので、式（２２）は式（２３）に変形される。
【数１２】
2014219597.tif 000014
【００２９】
式（２１）の左辺の式を、式（２３）の０次項に加えると、式（２４）となる。
【数１３】
2014219597.tif 000015
【００３０】
式（２４）を整理すると、式（２５）となる。
【数１４】
2014219597.tif 000016
【００３１】
式（２５）の式は、式（１）と一致する。従って、ｉ２−ｂで拡大した二次拡大体の代数的トーラスの元に対して二乗演算する場合には、式（１）により演算することが可能であるといえる。
【００３２】
基礎体内での元の二乗演算のコストをＳ、基礎体内での元の乗算のコストをＭ、基礎体内の元と定数との乗算のコストをｍ、加算のコストを０としたとする。この場合、通常の二乗の演算式である式（２３）の演算コストは、Ｍ＋２Ｓ＋ｍである。これに対して、式（１）の演算コストは、Ｍ＋Ｓである。
【００３３】
このように、第１実施形態にかかる演算装置１０によれば、式（１）を用いることにより、通常の演算式を用いる場合よりも小さいコストで二乗演算をすることができる。
【００３４】
（第２実施形態）
図２は、第２実施形態にかかる演算装置２０の構成を示す。演算装置２０は、代数的トーラスの元の三乗を計算して出力する。
【００３５】
演算装置２０は、入力部２１と、冪乗部２２とを備える。入力部２１は、有限体を三次多項式で拡大した三次拡大体の元から選択された代数的トーラスの元を入力する。
【００３６】
また、入力部２１は、代数的トーラスの元をベクトル表現の形式で入力する。具体的には、三次拡大体の元ｇは、ｇ＝ｇ０＋ｇ１×ｔ＋ｇ２×ｔ２といった変数ｔの２次式で表すことができる。入力部２１は、このように表した場合における、０次項の係数ｇ０、１次項の係数ｇ１および２次項の係数ｇ２を入力する。すなわち、例えば、入力部２１は、代数的トーラスの元を多項式の係数の形式で入力する。
【００３７】
冪乗部２２は、予め設定された演算式で、入力した代数的トーラスの元に対して三乗演算をする。そして、冪乗部２２は、三乗演算結果をベクトル表現の形式で出力する。本例においては、冪乗部２２は、三乗演算結果ｇ３を変数ｔの２次式で表した場合における、０次項の係数ｇｘ０、１次項の係数ｇｘ１および２次項の係数ｇｘ２を出力する。
【００３８】
ここで、冪乗部２２は、代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された三次拡大体の元に対して三乗するための演算式に基づいて、入力した代数的トーラスの元に対して三乗演算する。
【００３９】
具体的には、ｔを変数、ｓを有限体に含まれる元とし、有限体を拡大するための三次多項式をｔ３−ｓとする場合、冪乗部２２は、下記の式（２）の演算式を実行して、入力された代数的トーラスの元の三乗ｇ３を計算する。
【数１５】
2014219597.tif 000017
【００４０】
演算装置２０は、このような演算式を用いることにより、通常の演算式を用いる場合よりも小さいコストで三乗演算をすることができる。
【００４１】
式（２）の演算式は、すなわち、三次拡大体の元に対して三乗するための演算式は、ベクトル表現の形式で表された三次拡大体の元に対する三乗の演算式に、代数的トーラスの元の成立条件を表す式に三次拡大体の元およびフロベニウス共役元を表す式を代入して導き出した０次項の式を加えることにより、導き出される。以下、具体的に冪乗部２２がこのような式（２）の演算式を用いて、代数的トーラスの元の三乗演算が可能な理由を説明する。
【００４２】
基礎体Ｆｑを三次拡大するための多項式を式（３１）とする。ｔは、変数を表し、ｓは基礎体Ｆｑから選択された任意の元である。
【数１６】
2014219597.tif 000018
【００４３】
この場合、基礎体Ｆｑの三次拡大体Ｆｑ＾３は、式（３２）で表される。
【数１７】
2014219597.tif 000019
【００４４】
また、三次拡大体Ｆｑ＾３の元ｇは、式（３３）で表される。また、三次拡大体Ｆｑ＾３のフロベニウス共役元ｇｑ、ｇｑ＾２は、式（３４）および式（３５）で表される。
【数１８】
2014219597.tif 000020
【００４５】
なお、ｓ１は式（３６）に示す通りである。また、ｓ２は式（３７）に示す通りである。
【数１９】
2014219597.tif 000021
【００４６】
ここで、代数的トーラスの元は、三次拡大体Ｆｑ＾３のうち部分体に含まれない元である。このことから、式（３１）で拡大された三次拡大体Ｆｑ＾３の代数的トーラスの元は、式（３８）且つ式（３９）を満たす。すなわち、式（３８）および式（３９）は、代数的トーラスの元の成立条件を表す式である。
【数２０】
2014219597.tif 000022
【００４７】
（ｑ３−１）を因数分解すると、式（４０）となる。
【数２１】
2014219597.tif 000023
【００４８】
式（３８）の条件から（ｑ−１）は０とはならない。従って、式（３９）の条件は、式（４１）のように変形できる。
【数２２】
2014219597.tif 000024
【００４９】
式（４１）は、式（４２）に変形される。
【数２３】
2014219597.tif 000025
【００５０】
式（４２）に三次拡大体Ｆｑ＾３の元ｇを表す式（３３）およびフロベニウス共役元ｇｑ、ｇｑ＾２を表す式（３４）、式（３５）を代入する。そうすると、式（４２）は、式（４３）となる。
【数２４】
2014219597.tif 000026
【００５１】
式（４３）の左辺の左側の２つの括弧内を展開すると、式（４４）となる。
【数２５】
2014219597.tif 000027
【００５２】
ところで、ｓ１・ｓ２は、式（４５）に示されるように、有限体の性質から１となる。
【数２６】
2014219597.tif 000028
【００５３】
また、ｓは基礎体Ｆｑから選択された任意の元であるのでｓｑ−１＝１である。ｓ（ｑ−１）／３−１≠１とすると、式（４６）に示すように、ｓ１＋ｓ２は−１となる。
【数２７】
2014219597.tif 000029
【００５４】
式（４４）に式（４５）および式（４６）を代入すると、式（４７）に変形される。
【数２８】
2014219597.tif 000030
【００５５】
式（３１）の多項式の解からｔ３＝ｓといえるので、式（４７）は式（４８）に変形される。
【数２９】
2014219597.tif 000031
【００５６】
式（４８）の右辺の値を左辺に移行させると、式（４９）となる。
【数３０】
2014219597.tif 000032
【００５７】
このように、代数的トーラスの元の成立条件を表す式に三次拡大体Ｆｑ＾３の元ｇを表す式およびフロベニウス共役元ｇｑ、ｇｑ＾２を表す式を代入することにより、式（４９）のような変数ｔの０次項の式を導き出すことができる。
【００５８】
一方、ベクトル表現の形式で表された三次拡大体Ｆｑ＾３の元に対する三乗ｇ３の演算式は、式（５０）のように表される。
【数３１】
2014219597.tif 000033
【００５９】
式（４９）の左辺の式を、式（５０）の０次項に減ずると、式（５１）となる。
【数３２】
2014219597.tif 000034
ただし、ｈ１およびｈ２は式（５２）、式（５３）の通りである。
【数３３】
2014219597.tif 000035
式（５１）の式は、式（２）と一致する。従って、ｉ３−ｓで拡大した三次拡大体の代数的トーラスの元に対して三乗演算する場合には、式（２）により演算することが可能であるといえる。
【００６０】
基礎体内での元の三乗演算のコストをＳ、基礎体内での元の乗算のコストをＭ、基礎体内の元と定数との乗算のコストをｍ、加算のコストを０としたとする。この場合、通常の三乗の演算式である式（５０）の演算コストは、６Ｍ＋６Ｓ＋４ｍとなる。これに対して、式（２）の演算コストは、７Ｍ＋２Ｓ＋３ｍである。通常、Ｓ／Ｍはほぼ０．８程度である。Ｓ＝０．８Ｍとすると、６Ｍ＋６Ｓ＋４ｍ＝１０．８Ｍ＋４ｍ、７Ｍ＋２Ｓ＋３ｍ＝８．６Ｍ＋３ｍである。
【００６１】
このように第２実施形態にかかる演算装置２０によれば、式（２）を用いることにより、通常の演算式を用いる場合よりも小さいコストで三乗演算をすることができる。
【００６２】
（第３実施形態）
図３は、第３実施形態にかかる演算装置３０の構成を示す。演算装置３０は、代数的トーラスの元の三乗を計算して出力する。
【００６３】
演算装置３０は、入力部３１と、冪乗部３２とを備える。入力部３１は、有限体を十次多項式で拡大した十次拡大体の元から選択された代数的トーラスの元を入力する。
【００６４】
また、入力部３１は、代数的トーラスの元をベクトル表現の形式で入力する。具体的には、十次拡大体の元ｇは、ｇ０からｇ９までの１０個の多項式の係数で表すことができる。入力部３１は、このように表した場合における、各係数ｇ０〜ｇ９を入力する。
【００６５】
冪乗部３２は、予め設定された演算式で、入力した代数的トーラスの元に対して三乗演算をする。そして、冪乗部３２は、三乗演算結果をベクトル表現の形式で出力する。本例においては、冪乗部３２は、三乗演算結果ｇ３をｇｘ０からｇｘ９までの多項式の１０個の多項式の係数の形式で出力する。
【００６６】
ここで、冪乗部３２は、代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表された十次拡大体の元に対して三乗するための演算式に基づいて、入力した代数的トーラスの元に対して三乗演算する。
【００６７】
演算装置３０は、このような演算式を用いることにより、通常の演算式を用いる場合よりも小さいコストで三乗演算をすることができる。
【００６８】
十次拡大体の元に対して三乗するための演算式は、ベクトル表現の形式で表された十次拡大体の元に対する三乗の演算式に、代数的トーラスの元の成立条件を表す式に十次拡大体の元およびフロベニウス共役元を表す式を代入して導き出した式により整理することにより導き出される。以下、具体的に冪乗部３２が用いる三乗の演算式について説明する。
【００６９】
基礎体Ｆｑを十次拡大するための多項式を１０次の円分多項式とする。すなわち、十次拡大体Ｆｑ＾１０は、式（６０）に示される多項式により、基礎体Ｆｑを拡大して生成される。なお、ｖは、変数を表す。
【数３４】
2014219597.tif 000036
【００７０】
また、十次拡大体Ｆｑ＾１０の元ｇは、式（６１）の正規基底で表される。また、十次拡大体Ｆｑ＾１０の一部のフロベニウス共役元ｇｑ、ｇｑ＾２、ｇｑ＾３、ｇｑ＾４は、式（６２）、式（６３）、式（６４）および式（６５）の正規基底で表される。
【数３５】
2014219597.tif 000037
【００７１】
なお、ｑ  ｍｏｄ  １１＝２のとき、ｖｑ＝ｖ２、ｖ（ｑ＾２）＝ｖ４、ｖ（ｑ＾３）＝ｖ８、ｖ（ｑ＾４）＝ｖ５、ｖ（ｑ＾５）＝ｖ１０、ｖ（ｑ＾６）＝ｖ９、ｖ（ｑ＾７）＝ｖ７、ｖ（ｑ＾８）＝ｖ３、ｖ（ｑ＾９）＝ｖ６を満たすｑを用いた。
【００７２】
ここで、代数的トーラスの元は、十次拡大体Ｆｑ＾１０のうち部分体に含まれない元である。十次拡大体Ｆｑ＾１０の元のうち代数的トーラスの元を満たす成立条件を表す式は、ｇｑ＾４−ｑ＾３＋ｑ＾２−ｑ＋１＝１となる。この式は式（６６）のよう変形される。
【数３６】
2014219597.tif 000038
【００７３】
式（６６）に、十次拡大体Ｆｑ＾１０の元を表した式およびフロベニウス共役元を表した式を代入する。そうすると、以下の１０組の条件式が導き出される。
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，１）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，１）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，２）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，２）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，４）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，４）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，８）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，８）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，５）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，５）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，１０）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，１０）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，９）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，９）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，７）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，７）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，３）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，３）
ｃｏｅｆｆ（ｌｅｆｔ，ｖ，６）＝ｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，６）
【００７４】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，１）は下式の通りである。
【数３７】
2014219597.tif 000039
【００７５】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，２）は下式の通りである。
【数３８】
2014219597.tif 000040
【００７６】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，４）は下式の通りである。
【数３９】
2014219597.tif 000041
【００７７】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，８）は下式の通りである。
【数４０】
2014219597.tif 000042
【００７８】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，５）は下式の通りである。
【数４１】
2014219597.tif 000043
【００７９】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，１０）は下式の通りである。
【数４２】
2014219597.tif 000044
【００８０】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，９）は下式の通りである。
【数４３】
2014219597.tif 000045
【００８１】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，７）は下式の通りである。
【数４４】
2014219597.tif 000046
【００８２】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，３）は下式の通りである。
【数４５】
2014219597.tif 000047
【００８３】
左辺側のｃｏｅｆｆ（ｌｅｆｔ，ｖ，６）は下式の通りである。
【数４６】
2014219597.tif 000048
【００８４】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，１）は下式の通りである。
【数４７】
2014219597.tif 000049
【００８５】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，２）は下式の通りである。
【数４８】
2014219597.tif 000050
【００８６】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，４）は下式の通りである。
【数４９】
2014219597.tif 000051
【００８７】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，８）は下式の通りである。
【数５０】
2014219597.tif 000052
【００８８】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，５）は下式の通りである。
【数５１】
2014219597.tif 000053
【００８９】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，１０）は下式の通りである。
【数５２】
2014219597.tif 000054
【００９０】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，９）は下式の通りである。
【数５３】
2014219597.tif 000055
【００９１】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，７）は下式の通りである。
【数５４】
2014219597.tif 000056
【００９２】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，３）は下式の通りである。
【数５５】
2014219597.tif 000057
【００９３】
右辺側のｃｏｅｆｆ（ｒｉｇｈｔ，ｖ，６）は下式の通りである。
【数５６】
2014219597.tif 000058
【００９４】
一方、ベクトル表現の形式で表された十次拡大体Ｆｑ＾１０の元に対する、通常の三乗ｇ３の演算式は、式（６７）のように表される。
ｖ３＝ｃｏｅｆｆ（ｃｕｂｅ，ｖ，１）×ｖ
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，２）×ｖ２
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，４）×ｖ４
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，８）×ｖ８
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，５）×ｖ５
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，１０）×ｖ１０
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，９）×ｖ９
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，７）×ｖ７
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，３）×ｖ３
＋ｃｏｅｆｆ（ｃｕｂｅ，ｖ，６）×ｖ６      …（６７）
【００９５】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，１）は下式の通りである。
【数５７】
2014219597.tif 000059
【００９６】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，２）は下式の通りである。
【数５８】
2014219597.tif 000060
【００９７】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，４）は下式の通りである。
【数５９】
2014219597.tif 000061
【００９８】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，８）は下式の通りである。
【数６０】
2014219597.tif 000062
【００９９】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，５）は下式の通りである。
【数６１】
2014219597.tif 000063
【０１００】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，１０）は下式の通りである。
【数６２】
2014219597.tif 000064
【０１０１】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，９）は下式の通りである。
【数６３】
2014219597.tif 000065
【０１０２】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，７）は下式の通りである。
【数６４】
2014219597.tif 000066
【０１０３】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，３）は下式の通りである。
【数６５】
2014219597.tif 000067
【０１０４】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，６）は下式の通りである。
【数６６】
2014219597.tif 000068
【０１０５】
ここで、１０組の条件式から式（６８）のｚｅｒｏを算出する。
【数６７】
2014219597.tif 000069
【０１０６】
式（６８）のｚｅｒｏは、以下のように展開される。
【数６８】
2014219597.tif 000070
【０１０７】
通常の三乗の演算式である式（６７）のそれぞれの係数に、式（６８）のｚｅｒｏを加算する。そうすると、十次拡大体Ｆｑ＾１０の元に対する三乗ｇ３の演算式は、以下の式（６９）のように表される。
【０１０８】
ｖ３＝（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，１）＋ｚｅｒｏ）×ｖ
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，２）＋ｚｅｒｏ）×ｖ２
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，４）＋ｚｅｒｏ）×ｖ４
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，８）＋ｚｅｒｏ）×ｖ８
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，５）＋ｚｅｒｏ）×ｖ５
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，１０）＋ｚｅｒｏ）×ｖ１０
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，９）＋ｚｅｒｏ）×ｖ９
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，７）＋ｚｅｒｏ）×ｖ７
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，３）＋ｚｅｒｏ）×ｖ３
＋（ｃｏｅｆｆ（ｃｕｂｅ，ｖ，６）＋ｚｅｒｏ）×ｖ６      …（６９）
【０１０９】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，１）＋ｚｅｒｏは下式の通りである。
【数６９】
2014219597.tif 000071
【０１１０】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，２）＋ｚｅｒｏは下式の通りである。
【数７０】
2014219597.tif 000072
【０１１１】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，４）＋ｚｅｒｏは下式の通りである。
【数７１】
2014219597.tif 000073
【０１１２】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，８）＋ｚｅｒｏは下式の通りである。
【数７２】
2014219597.tif 000074
【０１１３】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，５）＋ｚｅｒｏは下式の通りである。
【数７３】
2014219597.tif 000075
【０１１４】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，１０）＋ｚｅｒｏは下式の通りである。
【数７４】
2014219597.tif 000076
【０１１５】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，９）＋ｚｅｒｏは下式の通りである。
【数７５】
2014219597.tif 000077
【０１１６】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，７）＋ｚｅｒｏは下式の通りである。
【数７６】
2014219597.tif 000078
【０１１７】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，３）＋ｚｅｒｏは下式の通りである。
【数７７】
2014219597.tif 000079
【０１１８】
ｃｏｅｆｆ（ｃｕｂｅ，ｖ，６）＋ｚｅｒｏは下式の通りである。
【数７８】
2014219597.tif 000080
【０１１９】
冪乗部３２は、以上の式（６９）の演算式を実行して、入力された代数的トーラスの元の三乗ｇ３を計算する。これにより、第３実施形態にかかる演算装置３０によれば、通常の演算式を用いる場合よりも小さいコストで三乗演算をすることができる。
【０１２０】
（他の形態）
なお、以上第１〜第３の実施形態を説明したが、拡大体の次数は二次、三次および十次に限られない。すなわち、入力部は、有限体をＭ次（Ｍは２以上の整数）の多項式で拡大したＭ次拡大体の元から選択された代数的トーラスの元を、ベクトル表現の形式で入力してもよい。
【０１２１】
さらに、冪乗の乗数も二乗および三乗に限られない。すなわち、冪乗部は、ベクトル表現の形式で表されたＭ次拡大体の元に対するＮ乗（Ｎは２以上の整数）の演算をしてもよい。この場合、冪乗部は、代数的トーラスの元の成立条件を満たす場合にベクトル表現の形式で表されたＭ次拡大体の元に対してＮ乗（Ｎは２以上の整数）するための演算式に基づいて、入力した代数的トーラスの元に対してＮ乗演算する。このＭ次拡大体の元に対してＮ乗をするための演算式は、ベクトル表現の形式で表されたＭ次拡大体の元に対するＮ乗の演算式に、代数的トーラスの元の成立条件を表す式にＭ次拡大体の元およびフロベニウス共役元を表す式を代入して導き出した式により整理することにより導き出される。
【０１２２】
次に、第１、第２および第３の実施形態にかかる演算装置のハードウェア構成について図４を用いて説明する。図４は、第１、第２および第３の実施形態にかかる演算装置のハードウェア構成を示す説明図である。
【０１２３】
第１、第２および第３の実施形態にかかる演算装置は、ＣＰＵ（Central  Processing  Unit）５１などの制御装置と、ＲＯＭ（Read  Only  Memory）５２やＲＡＭ（Random  Access  Memory）５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、各部を接続するバス６１を備えている。
【０１２４】
実施形態にかかる演算装置で実行される演算プログラムは、ＲＯＭ５２等に予め組み込まれて提供される。
【０１２５】
実施形態にかかる演算装置で実行される演算プログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact  Disk  Read  Only  Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact  Disk  Recordable）、ＤＶＤ（Digital  Versatile  Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供されるように構成してもよい。
【０１２６】
さらに、実施形態にかかる演算装置で実行される演算プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、実施形態にかかる演算装置で実行される演算プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１２７】
実施形態にかかる演算装置で実行される演算プログラムは、コンピュータを上述した演算装置の各部（入力部および冪乗部）として機能させうる。このコンピュータは、ＣＰＵ５１がコンピュータ読取可能な記憶媒体から演算プログラムを主記憶装置上に読み出して実行することができる。
【０１２８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１２９】
１０  演算装置
１１  入力部
１２  冪乗部
５１  ＣＰＵ
５２  ＲＯＭ
５３  ＲＡＭ
５４  通信部
６１  バス
【図１】
2014219597.tif 000083
【図２】
2014219597.tif 000084
【図３】
2014219597.tif 000085
【図４】
2014219597.tif 000086