(57)【特許請求の範囲】
【請求項１】
有限体の乗法群の部分群の要素をトレース表現で表した複数の入力データと、前記入力データそれぞれの共役元を区別するための複数の第１付加データとを受付ける受付部と、
複数の前記入力データに対する予め定められた演算処理の演算結果の取りうる値を解とする方程式の係数を、複数の前記入力データに基づいて算出する係数算出部と、
算出された前記係数を有する方程式の複数の解を求める求解部と、
前記第１付加データに基づいて、複数の前記解から１の解を前記演算結果として選択する選択部と、
前記第１付加データに基づいて、選択された前記演算結果の共役元を区別するための第２付加データを決定する決定部と、
選択された前記演算結果と、前記第２付加データと、を出力する出力制御部と、
を備える演算装置。
【請求項２】
前記係数算出部は、複数の前記入力データに対する特性多項式の係数と、複数の前記入力データとを用いて、前記方程式の係数を算出する、
請求項１に記載の演算装置。
【請求項３】
前記第１付加データは、前記入力データと前記共役元との間の大きさの順序を表し、
前記選択部は、複数の前記解から、複数の前記第１付加データが表す順序の組み合わせに応じて定まる１の解を前記演算結果として選択する、
請求項１に記載の演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、演算装置に関する。
【背景技術】
【０００２】
事前の鍵共有なしに安全な通信を実現する公開鍵暗号技術では、暗号系サイズの増大が問題になっている。このような背景から、代数的トーラスを用いて公開鍵暗号における暗号系サイズを圧縮する方法が提案されている。代数的トーラスの元（げん）を表現する方法には、トレース表現、射影表現および拡大体表現がある。トレース表現ではベキ乗アルゴリズムは知られているが、乗算はできないと考えられていた。そこで、代数的トーラスを用いる公開鍵暗号において、鍵生成、暗号化および復号の各ステップで、入出力にはトレース表現が用いられ、演算には射影表現または拡大体表現が用いられていた。このため、演算の前または後に、各表現間の変換を行う（表現変換）必要があった。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Koray  Karabina,  “Factor-4  and  6  Compression  of  Cyclotomic  Subgroups”,J.  of  Mathematical  Cryptology,  Vol.  4,  No.1,  pp.1-42,  2010.
【非特許文献２】米村智子,  村谷博文  and  花谷嘉一,  ”代数的トーラス上の暗号系〜トレース表現に関する新しい伸長写像〜”,  SCIS2012,  2012.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術では、変換前の表現および変換後の表現の組み合わせによっては、表現変換の計算量が多くなり、表現変換および演算を含む全体の計算量が多大になる恐れがあった。
【課題を解決するための手段】
【０００５】
実施形態の演算装置は、受付部と係数算出部と求解部と決定部と出力制御部とを備える。受付部は、有限体の乗法群の部分群の要素をトレース表現で表した複数の入力データと、入力データそれぞれの共役元を区別するための複数の第１付加データとを受付ける。係数算出部は、入力データに対する演算処理の演算結果の取りうる値を解とする方程式の係数を、入力データに基づいて算出する。求解部は、算出された係数を有する方程式の複数の解を求める。選択部は、第１付加データに基づいて複数の解から１の解を演算結果として選択する。決定部は、第１付加データに基づいて、選択された演算結果の共役元を区別するための第２付加データを決定する。出力制御部は、選択された演算結果と第２付加データとを出力する。
【図面の簡単な説明】
【０００６】
【図１】第１の実施形態にかかる演算装置のブロック図。
【図２】第１の実施形態における演算処理のフローチャート。
【図３】第２の実施形態にかかる演算装置のブロック図。
【図４】演算装置のハードウェア構成図。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、この発明にかかる演算装置の好適な実施形態を詳細に説明する。
【０００８】
（第１の実施形態）
図１は、第１の実施形態にかかる演算装置１００の構成の一例を示すブロック図である。図１に示すように、演算装置１００は、受付部１０１と、係数算出部１０２と、求解部１０３と、選択部１０４と、決定部１０５と、出力制御部１０６と、を備えている。
【０００９】
受付部１０１は、演算に用いるデータの入力を受付ける。例えば、受付部１０１は、演算の対象となる複数の入力データと、入力データそれぞれの付加データ（第１付加データ）とを受付ける。入力データは、有限体の乗法群（有限体表現の代数的トーラス）の部分群の要素をトレース表現で表したデータである。以下では、代数的トーラスの元ｇのトレース表現をトレース値Ｔｒ（ｇ）と表記する。付加データは、対応する入力データそれぞれの共役元を区別するためのデータである。
【００１０】
係数算出部１０２は、複数の入力データに対する予め定められた演算処理の演算結果の取りうる値を解とする方程式（多項式）の係数を算出する。以下では、予め定められた演算処理として、複数の入力データの乗算処理を例に説明するが、これに限られるものではない。例えば、複数の入力データのうち一方のフロベニウス写像と他方との乗算処理、および、複数の入力データのフロベニウス写像の乗算処理に対しても同様の手法を適用できる。
【００１１】
求解部１０３は、算出された係数を有する上記多項式の複数の解を求める。求解部１０３は、従来から用いられているあらゆるアルゴリズムにより多項式の求解（求根）を実行できる。例えば、２次方程式の解の公式、３次方程式の解の公式、有限体上の求解を行うBerlekampのアルゴリズムなどがある。複数の解は、複数の入力データに対する演算処理（例えば乗算処理）の実際の演算結果を表す解とともに、それ以外の解も含む。
【００１２】
選択部１０４は、受付けられた付加データに基づいて、複数の解から１の解を演算結果として選択する。
【００１３】
決定部１０５は、複数の入力データそれぞれに対する複数の付加データを用いて、演算結果として選択された解の共役元を区別するための付加データ（第２付加データ）を決定する。
【００１４】
出力制御部１０６は、選択された解（演算結果）と、この解の付加データとを出力する。
【００１５】
次に、このように構成された第１の実施形態にかかる演算装置１００による演算処理について図２を用いて説明する。図２は、第１の実施形態における演算処理の全体の流れを示すフローチャートである。
【００１６】
受付部１０１は、乗算する複数の入力データ（トレース値ともいう）、および、トレース値ごとの付加データの入力を受付ける（ステップＳ１０１）。係数算出部１０２は、複数のトレース値の乗算結果（乗算値ともいう）の取りうる値を解（根）として持つ多項式の係数を算出する（ステップＳ１０２）。求解部１０３は、算出された係数を有する多項式の解を求める（ステップＳ１０３）。
【００１７】
選択部１０４は、受付けられた付加データを用いて、求められた複数の解から、複数のトレース値の乗算結果（乗算値ともいう）として出力する解を選択する（ステップＳ１０４）。
【００１８】
一方、決定部１０５は、受付けられた付加データを用いて、選択された解（乗算値）の付加データを決定する（ステップＳ１０５）。なお、ステップＳ１０２〜ステップＳ１０４と、ステップＳ１０５とは、図２の順序で実行する必要はない。逆の順序で実行してもよいし、並行して実行してもよい。
【００１９】
出力制御部１０６は、選択された乗算値と、乗算値に対して決定された付加データとを出力し（ステップＳ１０６）、演算処理を終了する。
【００２０】
以下、演算処理の詳細についてさらに説明する。まず、本実施形態にかかる代数的トーラスにおける演算の数学的準備について説明する。代数的トーラスＴｎが定義される有限体をＦｐ＾ｍとする。ここで、ｐは素数、ｎとｍは正整数とする。記号「＾」はべき乗を表す。例えば、ｐ＾ｍはｐのｍ乗を表す。Ｆｐ＾ｍは、要素数がｐ＾ｍの有限体を表す。代数的トーラスＴｎ（Ｆｐ＾ｍ）は要素数がΦｎ（ｐ＾ｍ）の群である。ここで、Φｎ（Ｘ）は第ｎ円分多項式（円周ｎ等分多項式）である。代数的トーラスＴｎ（Ｆｐ＾ｍ）のトレース表現は、φ（ｎ）個のＦｐ＾ｍの元の組で表される。ここで、φ（ｘ）はオイラー関数である。また、代数的トーラスの部分群Ｇ±のトレース表現はφ（ｎ）／２個のＦｐ＾ｍの元の組で表される。
【００２１】
以下にｎ＝４とｎ＝６の場合の部分群Ｇ±の例を示す。
【００２２】
代数的トーラスＴｎ（Ｆｐ＾ｍ）の元ｇのトレース表現は、トレース値Ｔｒ（ｇ）とＴｒ（ｇ＾｛ｐ＾ｍ＋１｝）で表わされる。トレース写像Ｔｒは以下の数１で表される写像である。
【数１】
0005554357.tif 000002
【００２３】
ここで、フロベニウス写像πは、π：ｘ→ｘ＾（ｐ＾ｍ）、ｉ＝０，１，・・・，ｎ−１であり、Ｔｒ（ｇ）はＦｐ＾ｍの元となる。元ｇと元ｇフロベニウス共役を根として持つ以下の数２で表される多項式を特性多項式と呼ぶ。
【数２】
0005554357.tif 000003
【００２４】
特性多項式は、Ｆｐ＾ｍ係数のｎ次式である。ｎ＝２のとき特性多項式は、Ｘ＾２−Ｔｒ（ｇ）Ｘ＋１となる。ｎ＝４のとき特性多項式は以下の数３のようになる。
【数３】
0005554357.tif 000004
【００２５】
ｎ＝６のとき特性多項式は以下の数４のようになる。
【数４】
0005554357.tif 000005
【００２６】
ここで、Ｔｒ（ｇ）＾２＝２Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）＋Ｔｒ（ｇ＾２）＋２Ｔｒ（ｇ）＋６である。Ｘの２次の係数はＸの４次の係数に等しく、Ｘの１次の係数はＸの５次の係数に等しい。従って、特性多項式の係数は、トレース値Ｔｒ（ｇ）とＴｒ（ｇ＾｛ｐ＾ｍ＋１｝）で決まる。そして、特性多項式の求根を行うことで拡大体表現の元ｇと元ｇ共役元を得ることができる。
【００２７】
次に部分群Ｇ±について説明する。部分群Ｇ±は、要素数がｐ＾ｍ±√ｐ＾｛ｍ＋１｝＋１の群である。部分群Ｇ±は、ｍが奇数であり、ｎ＝４かつｐ＝２の場合に、または、ｎ＝６かつｐ＝３の場合に、代数的トーラスＴｎ（Ｆｐ＾ｍ）の部分群となっている。
【００２８】
部分群Ｇ±の元ｇのトレース表現は、トレース値Ｔｒ（ｇ）で表わされる。部分群Ｇ±の元ｇについて、Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）＝Ｔｒ（ｇ）＾｛√ｐ＾｛ｍ＋１｝｝と計算されるため、特性多項式の係数はトレース値Ｔｒ（ｇ）のみで決まるからである。
【００２９】
ここでトレース写像と、標数ｐのベキ乗を指数とするベキ乗と、が交換することに注意する。
【００３０】
トレース表現に、元ｇと、元ｇの共役元を区別する付加データとを組み合わせると、トレース値Ｔｒ（ｇ）を用いて特性多項式の求根を行うことにより、トレース値Ｔｒ（ｇ）を、拡大体表現の元ｇへ一意に表現変換できる。
【００３１】
ｎ個の共役元を区別するので、ｎ＝４のとき２ビット、ｎ＝６のときｌｏｇ２（６）ビット、一般にｌｏｇ２（ｎ）ビットの付加データが用いられる。
【００３２】
次に、トレース表現における乗算方法を示す。トレース表現における乗算とは、トレース値Ｔｒ（ｇ）とＴｒ（ｇ）の付加データ、および、トレース値Ｔｒ（ｈ）とＴｒ（ｈ）の付加データから、拡大体表現ｇとｈに変換せずに、乗算値Ｔｒ（ｇｈ）とＴｒ（ｇｈ）の付加データを計算することである。
【００３３】
ここで、特性多項式の係数がＴｒ（ｇ）のみで決まっているとする。代数的トーラスＴｎ（Ｆｐ＾ｍ）の部分群の場合、乗算値の取りうる値はＴｒ（π＾ｉ（ｇ）ｈ）のｎ通り存在する。従って、選択部１０４は、入力された付加データを用いてｎ通りから適当な乗算値を選択すればよい。
【００３４】
そこで、まず係数算出部１０２が、乗算値の取りうる値を根として持つ多項式の係数をＴｒ（ｇ）とＴｒ（ｈ）から計算する。そして、求解部１０３が多項式の求根を行い、選択部１０４が求めた根から乗算値を選択する。これによりＴｒ（ｇ）とＴｒ（ｈ）の乗算が構成される。
【００３５】
多項式は、Ｆｐ＾ｍ係数のｎ次式であり、求根の際もＦｐ＾ｍで解けばよい。一方、特性多項式もＦｐ＾ｍ係数のｎ次式であるが、代数的トーラスＴｎ（Ｆｐ＾ｍ）の元ｇについて求根の際は大きな拡大体Ｆ（ｐ＾ｍ）＾nで解かなければならない。方程式の解の空間が狭い分、トレース表現における乗算は、拡大体表現への変換後に乗算を行う場合に比べ高速である。
【００３６】
ｎ＝２のとき代数的トーラスＴｎ（Ｆｐ＾ｍ）の元ｇおよび元ｈについて乗算値の取りうる値を根として持つ多項式は以下のようになる。
｛Ｙ−Ｔｒ（ｇｈ）｝｛Ｙ−Ｔｒ（π（ｇ）ｈ）｝
＝Ｙ２−Ｔｒ（ｇ）Ｔｒ（ｈ）Ｙ＋｛Ｔｒ（ｇ）２＋Ｔｒ（ｈ）２−４｝
【００３７】
Ｙの（ｎ−１）次の係数について、ｎに依らずＴｒ（ｇｈ）＋Ｔｒ（π（ｇ）ｈ）＋・・・＋Ｔｒ（π＾｛ｎ−１｝（ｇ）ｈ）＝Ｔｒ（ｇ）Ｔｒ（ｈ）である。定数項について、ｇ＾｛ｐ＾ｍ＋１｝＝１、ｈ＾｛ｐ＾ｍ＋１｝＝１を用いると、Ｔｒ（ｇｈ）Ｔｒ（π（ｇ）ｈ）＝Ｔｒ（ｇ＾２）＋Ｔｒ（ｈ＾２）となる。特性多項式から得られるトレース値の漸化式によりＴｒ（ｇ＾２）＝Ｔｒ（ｇ）＾２−２、Ｔｒ（ｈ＾２）＝Ｔｒ（ｈ）＾２−２となる。以上から上記多項式が得られる。
【００３８】
従って、乗算値の取りうる値を根として持つ多項式の係数はトレース値Ｔｒ（ｇ）とＴｒ（ｈ）のみで決まる。そして、多項式の求根を行うことで乗算値の取りうる値を得ることができる。
【００３９】
ここで、漸化式の一例について説明する。ｎ＝２のときの特性多項式であるＸ＾２−Ｔｒ（ｇ）Ｘ＋１＝０で、Ｘにｇを代入すると、ｇ＾２−Ｔｒ（ｇ）ｇ＋１＝０となる。この式のトレース表現は、Ｔｒ（ｇ＾２）−Ｔｒ（ｇ）＾２＋２＝０となる。ここで、Ｔｒ（１）＝２を用いている。従って、Ｔｒ（ｇ＾２）＝Ｔｒ（ｇ）＾２−２の漸化式が得られる。同様にして、一般に漸化式はＴｒ（ｇ＾ｉ＋１）＝Ｔｒ（ｇ＾ｉ）Ｔｒ（ｇ）−Ｔｒ（ｇ＾ｉ−１）で表される。
【００４０】
ｎ＝４のとき代数的トーラスの部分群Ｇ±の元ｇおよび元ｈについて乗算値の取りうる値を根として持つ多項式は以下の数５のようになる。
【数５】
0005554357.tif 000006
【００４１】
ここで、特性多項式から得られるトレース値の漸化式によりＴｒ（ｇ＾３）＝Ｔｒ（ｇ＾２）Ｔｒ（ｇ）＋Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）Ｔｒ（ｇ）＋Ｔｒ（ｇ）となる。Ｔｒ（ｇ＾２）＝Ｔｒ（ｇ）＾２、Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）＝Ｔｒ（ｇ）＾｛√ｐ＾｛ｍ＋１｝｝よりＴｒ（ｇ＾３）はトレース値Ｔｒ（ｇ）のみから計算される。Ｔｒ（ｈ＾３）も同様である。Ｔｒ（ｇ＾｛ｐ＾ｍ＋２｝）とＴｒ（ｇ＾｛２ｐ＾ｍ＋１｝）との和および積は以下の数６のようになる。
【数６】
0005554357.tif 000007
【００４２】
Ｔｒ（ｇ＾｛ｐ＾ｍ＋２｝）とＴｒ（ｇ＾｛２ｐ＾ｍ＋１｝）は、トレース値Ｔｒ（ｇ）のみから計算される。Ｔｒ（ｈ＾｛ｐ＾ｍ＋２｝）とＴｒ（ｈ＾｛２ｐ＾ｍ＋１｝）も同様である。
【００４３】
従って、乗算値の取りうる値を根として持つ多項式の係数は、トレース値Ｔｒ（ｇ）とＴｒ（ｈ）のみで決まる。そして、多項式の求根を行うことで乗算値の取りうる値を得ることができる。
【００４４】
ｎ＝６のとき代数的トーラスの部分群Ｇ±の元ｇおよび元ｈについて乗算値の取りうる値を根として持つ多項式は以下の数７〜数１２のようになる。
【数７】
0005554357.tif 000008
【数８】
0005554357.tif 000009
【数９】
0005554357.tif 000010
【数１０】
0005554357.tif 000011
【数１１】
0005554357.tif 000012
【数１２】
0005554357.tif 000013
【００４５】
ここで、Ｔｒ（ｇ＾２）＝Ｔｒ（ｇ）＾２＋Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）＋Ｔｒ（ｇ）、Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）＝Ｔｒ（ｇ）＾｛√ｐ＾｛ｍ＋１｝｝である。従って、Ｔｒ（ｇ＾２）はトレース値Ｔｒ（ｇ）のみから計算される。Ｔｒ（ｈ＾２）も同様である。
【００４６】
３次項についてＴｒ（ｇ＾｛ｐ＾ｍ＋２｝）とＴｒ（ｇ＾｛２ｐ＾ｍ＋１｝）との和および積は以下の数１３のようになる。
【数１３】
0005554357.tif 000014
【００４７】
Ｔｒ（ｇ＾｛ｐ＾ｍ＋２｝）とＴｒ（ｇ＾｛２ｐ＾ｍ＋１｝）は、トレース値Ｔｒ（ｇ）のみから計算される。特性多項式から得られるトレース値の漸化式により、Ｔｒ（ｇ＾５）＝Ｔｒ（ｇ）Ｔｒ（ｇ＾４）−｛Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）＋Ｔｒ（ｇ）｝｛Ｔｒ（ｇ）＾３＋Ｔｒ（ｇ）｝＋｛Ｔｒ（ｇ＾２）Ｔｒ（ｇ）−１｝Ｔｒ（ｇ＾２）となるためである。Ｔｒ（ｈ＾｛ｐ＾ｍ＋２｝）とＴｒ（ｈ＾｛２ｐ＾ｍ＋１｝）も同様である。
【００４８】
４次項についてＴｒ（ｇ＾｛ｐ＾ｍ＋３｝）とＴｒ（ｇ＾｛３ｐ＾ｍ＋１｝）との和および積は以下の数１４のようになる。
【数１４】
0005554357.tif 000015
【００４９】
Ｔｒ（ｇ＾｛ｐ＾ｍ＋３｝）とＴｒ（ｇ＾｛３ｐ＾ｍ＋１｝）は、トレース値Ｔｒ（ｇ）のみから計算される。特性多項式から得られるトレース値の漸化式により、Ｔｒ（ｇ＾７）＝Ｔｒ（ｇ）｛Ｔｒ（ｇ＾６）＋Ｔｒ（ｇ＾２）｝−｛Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）＋Ｔｒ（ｇ）｝｛Ｔｒ（ｇ＾５）＋Ｔｒ（ｇ）＾３｝＋｛Ｔｒ（ｇ＾２）Ｔｒ（ｇ）−１｝Ｔｒ（ｇ＾４）Ｔｒ（ｇ）となるためである。Ｔｒ（ｈ＾｛ｐ＾ｍ＋３｝）とＴｒ（ｈ＾｛３ｐ＾ｍ＋１｝）も同様である。
【００５０】
５次項についてＴｒ（ｇ＾｛ｐ＾ｍ＋４｝）とＴｒ（ｇ＾｛４ｐ＾ｍ＋１｝）との和および積、並びに、Ｔｒ（ｇ＾｛２ｐ＾ｍ＋３｝）とＴｒ（ｇ＾｛３ｐ＾ｍ＋２｝）との和および積は、以下の数１５のようになる。
【数１５】
0005554357.tif 000016
【００５１】
Ｔｒ（ｇ＾｛ｐ＾ｍ＋４｝）とＴｒ（ｇ＾｛４ｐ＾ｍ＋１｝）、Ｔｒ（ｇ＾｛２ｐ＾ｍ＋３｝）とＴｒ（ｇ＾｛３ｐ＾ｍ＋２｝）は、トレース値Ｔｒ（ｇ）のみから計算される。Ｔｒ（ｈ＾｛ｐ＾ｍ＋４｝）とＴｒ（ｈ＾｛４ｐ＾ｍ＋１｝）、Ｔｒ（ｈ＾｛２ｐ＾ｍ＋３｝）とＴｒ（ｈ＾｛３ｐ＾ｍ＋２｝）も同様である。
【００５２】
６次項についてＴｒ（ｇ＾｛ｐ＾ｍ＋５｝）とＴｒ（ｇ＾｛５ｐ＾ｍ＋１｝）との和および積は以下の数１６のようになる。
【数１６】
0005554357.tif 000017
【００５３】
Ｔｒ（ｇ＾｛ｐ＾ｍ＋５｝）とＴｒ（ｇ＾｛５ｐ＾ｍ＋１｝）は、トレース値Ｔｒ（ｇ）のみから計算される。特性多項式から得られるトレース値の漸化式により、Ｔｒ（ｇ＾｛１１｝）＝Ｔｒ（ｇ）｛Ｔｒ（ｇ＾｛１０｝）＋Ｔｒ（ｇ＾２）＾３｝−｛Ｔｒ（ｇ＾｛ｐ＾ｍ＋１｝）＋Ｔｒ（ｇ）｝｛Ｔｒ（ｇ）＾９＋Ｔｒ（ｇ＾７）｝＋｛Ｔｒ（ｇ＾２）Ｔｒ（ｇ）−１｝Ｔｒ（ｇ＾８）Ｔｒ（ｇ＾５）となるためである。Ｔｒ（ｈ＾｛ｐ＾ｍ＋５｝）とＴｒ（ｈ＾｛５ｐ＾ｍ＋１｝）も同様である。
【００５４】
以上によりトレース乗算が可能であることが示された。以下に上記手順をまとめる。
【００５５】
受付部１０１が、入力としてトレース値Ｔｒ（ｇ）と付加データ、トレース値Ｔｒ（ｈ）と付加データを受け付ける。係数算出部１０２が、トレース値Ｔｒ（ｇ）とＴｒ（ｈ）から、乗算値の取りうる値を根として持つ多項式の係数ｄ１（ｇ，ｈ）＝Ｔｒ（ｇ）Ｔｒ（ｈ），ｄ２（ｇ，ｈ），・・・，ｄｎ（ｇ，ｈ）を計算する。求解部１０３が、上記多項式の求根を行う。選択部１０４が、得られたｎ個の根からトレース値Ｔｒ（ｇ）の付加データとトレース値Ｔｒ（ｈ）の付加データとを用いて乗算値を１つ選択する。決定部１０５が、トレース値Ｔｒ（ｇ）の付加データとトレース値Ｔｒ（ｈ）の付加データとを用いて乗算値の付加データを決定する。
【００５６】
なお、付加データの決め方としては、様々な方法を用いることができる。最も単純な例は、拡大体表現または射影表現における共役元の大小関係により、小さい順または大きい順に０，１，２，・・・，ｎ−１のように付加データの値を割り振る方法である。
【００５７】
拡大体表現または射影表現における共役元のうち、最も小さい元を基準として、この基準の元の｛ｐ＾ｍ｝＾ｉ乗を付加データの値としてもよい。他に、標数ｐ＝２，３の場合、正規基底におけるいずれかの要素の｛０，１｝または｛０，１，２｝の値で付加データの値を決めてもよい。それぞれ２次方程式と３次方程式が正規基底においていずれかの要素の代入のみで解けるからである。
【００５８】
４次方程式は２次式と２次式の積とすると２次方程式を２回解くことで解が得られる。６次方程式は３次式と３次式の積または２次式と２次式と２次式の積とすると、いずれの場合も２次方程式を１回と３次方程式を１回解くことで解が得られる。
【００５９】
次に、選択部１０４による乗算値の選択と、決定部１０５による乗算値の付加データの決定について例を示す。まず、ｎ＝２の場合について説明する。
【００６０】
ｎ＝２のとき代数的トーラスＴｎ（Ｆｐ＾ｍ）の元ｇについて特性多項式は以下のようになる。
Ｘ２−Ｔｒ（ｇ）Ｘ＋１
【００６１】
特性多項式＝０をＸについて解くことにより、トレース値と付加データで拡大体表現を次の数１７のように表すことができる。
【数１７】
0005554357.tif 000018
【００６２】
伸長後に乗算を行うと、その結果は次の数１８および数１９のようになる。複号同順に注意する必要がある。
【数１８】
0005554357.tif 000019
【数１９】
0005554357.tif 000020
【００６３】
トレース値は次の数２０および数２１のようになる。
【数２０】
0005554357.tif 000021
【数２１】
0005554357.tif 000022
【００６４】
乗算値の取りうる値を根として持つ多項式＝０をＹについて解くと、次の数２２のようになる。
【数２２】
0005554357.tif 000023
【００６５】
従って、選択部１０４は、トレース値Ｔｒ（ｇ）の付加データとトレース値Ｔｒ（ｈ）の付加データの符号が揃っていれば「＋」の乗算値を選択し、異なっていれば「−」の乗算値を選択すればよい。
【００６６】
乗算値の付加データについて、トレース値と付加データで拡大体表現を次の数２３のように表すことができる。
【数２３】
0005554357.tif 000024
【００６７】
Ｔｒ（ｇｈ）＝Ｔｒ（（Ｔｒ（ｇ），±）（Ｔｒ（ｈ），±））と仮定すると、拡大体表現は次の数２４のように表わされる。
【数２４】
0005554357.tif 000025
【００６８】
決定部１０５は、トレース値Ｔｒ（ｇ）の付加データとトレース値Ｔｒ（ｈ）の付加データとが、共に「＋」ならば、Ｔｒ（ｇｈ）の付加データは「＋」に決定し、共に「−」ならば「−」に決定すればよい。また、他方の乗算値についても次の数２５のように表わされる。
【数２５】
0005554357.tif 000026
【００６９】
トレース値Ｔｒ（ｇ）の付加データとトレース値Ｔｒ（ｈ）の付加データとは互いに異なるので、決定部１０５は、Ｔｒ（ｇｈ）の付加データはトレース値Ｔｒ（ｈ）の付加データに決定すればよい。
【００７０】
以上の議論の中で、２つの平方根の決め方が明示されることが重要である。例えば、ある数５に対して√５＾２＝５とするならば、√（−５）＾２＝５とすべきであり、√（−５）＾２＝−５としてはならない。有限体の元においては√α＾２を決定する際に、例えばαと−αの小さい方を選択する。
【００７１】
次に、ｎ＝４の場合について説明する。ｎ＝４のとき特性多項式＝０をＸについて解くと、トレース値と付加データで元ｇと元ｇのフロベニウス共役元の拡大体表現を導出できる。４次の特性多項式を２つの２次式に分解して２次方程式を２回解く。標数ｐ＝２より解の公式は利用できないことに注意する。
【００７２】
特性多項式を以下の数２６のように分解する。ここでトレース写像Ｔｒ４／２はトレース写像Ｔｒにおけるπをπ＾２で置き換えた写像である。写像中のｉに関する和はｉ＝０，１，・・・，ｎ／２−１となる。
【数２６】
0005554357.tif 000027
【００７３】
上記の第１項についてＸ＝Ｔｒ４／２（ｇ）Ｘ’として変数変換を行って得られる次の数２７の方程式は、正規基底において計算コストなしで解が得られる。また、その２つの解は互いにビット反転になっており、１ビットで区別できる。
【数２７】
0005554357.tif 000028
【００７４】
上記の方程式を解くためには、先にＴｒ４／２（ｇ）を求めなければならない。Ｔｒ４／２（ｇ）とＴｒ４／２（ｇ）＾｛ｐ＾ｍ｝を解とする方程式は次の数２８のようになる。
【数２８】
0005554357.tif 000029
【００７５】
上記の方程式についてＺ＝Ｔｒ（ｇ）Ｚ’として変数変換を行って得られる次の数２９の方程式も、正規基底において計算コストなしで解が得られる。また、その２つの解は互いにビット反転になっており、１ビットで区別できる。
【数２９】
0005554357.tif 000030
【００７６】
以上をまとめると元ｇと元ｇフロベニウス共役元の拡大体表現は次の数３０のように表すことができる。
【数３０】
0005554357.tif 000031
【００７７】
ここで第一成分がｉ１である右側のベクトルが、Ｚ’に関する上記の方程式の解を表し、Ｆｐ＾｛２ｍ｝の元である。第一成分がｉ２である左側のベクトルが、Ｘ’に関する上記の方程式の解を表し、Ｆｐ＾｛４ｍ｝の元である。ｉ１とｉ２は、それぞれ０または１を取る。（ｉ１，ｉ２）∈｛０，１｝×｛０，１｝をＴｒ（ｇ）の付加データとする。元ｈと元ｈのフロベニウス共役元の拡大体表現についても同様である。
【００７８】
伸長後に乗算を行うと、その結果は次の数３１のようになる。ここでｈの表記も上記のｇの表記と同様である。拡大体の元の掛け算は可換であることに注意する。
【数３１】
0005554357.tif 000032
【００７９】
乗算値の取りうる値を根として持つ多項式＝０をＹについて解くと、乗算値の取りうる値を得ることができる。４次の上記多項式を２つの２次式に分解して２次方程式を２回解く。標数ｐ＝２より解の公式は利用できないことに注意する。上記多項式を以下の数３２のように分解する。
【数３２】
0005554357.tif 000033
【００８０】
上記の多項式の根を求めるためには、先にＴｒ４／２（ｇ）Ｔｒ４／２（ｈ）＋Ｔｒ４／２（ｇ）＾｛ｐ＾ｍ｝Ｔｒ４／２（ｈ）＾｛ｐ＾ｍ｝と、Ｔｒ４／２（ｇ）Ｔｒ４／２（ｈ）＾｛ｐ＾ｍ｝＋Ｔｒ４／２（ｇ）＾｛ｐ＾ｍ｝Ｔｒ４／２（ｈ）を求めなければならない。これらを解とする方程式は次の数３３のようになる。
【数３３】
0005554357.tif 000034
【００８１】
上記の方程式についてＷ＝Ｔｒ（ｇ）Ｔｒ（ｈ）Ｗ’として変数変換を行って得られる次の数３４の方程式も、正規基底において計算コストなしで解が得られる。また、その２つの解は互いにビット反転になっており、１ビットで区別できる。
【数３４】
0005554357.tif 000035
【００８２】
Ｙに関する上記多項式の第１項についてＹ＝（Ｔｒ４／２（ｇ）Ｔｒ４／２（ｈ）＋Ｔｒ４／２（ｇ）＾｛ｐ＾ｍ｝Ｔｒ４／２（ｈ）＾｛ｐ＾ｍ｝）Ｙ’として変数変換を行って得られる次の数３５の方程式も、正規基底において計算コストなしで解が得られる。また、その２つの解は互いにビット反転になっており、１ビットで区別できる。
【数３５】
0005554357.tif 000036
【００８３】
以上をまとめると乗算値の取りうる値は次の数３６のようになる。
【数３６】
0005554357.tif 000037
【００８４】
ここでｌ１で代表される右側のベクトルがＷ’に関する上記の方程式の解を表しＦｐ＾ｍの元である。ｌ２で代表される左側のベクトルがＹ’に関する上記の方程式の解を表しＦｐ＾ｍの元である。ｌ１とｌ２は、それぞれ０または１を取る。ある（ｌ１，ｌ２）が乗算値Ｔｒ（ｇｈ）を表すとすると、乗算値と付加データで乗算値の拡大体表現を次の数３７のように表すことができる。
【数３７】
0005554357.tif 000038
【００８５】
ここでｋ２で代表されるベクトルはＺ’に関する方程式の解を表しＦｐ＾｛２ｍ｝の元である。ｋ２で代表されるベクトルはＸ’に関する方程式の解を表しＦｐ＾｛４ｍ｝の元である。ｋ１とｋ２は、それぞれ０または１を取る。（ｋ１，ｋ２）∈｛０，１｝×｛０，１｝は、Ｔｒ（ｇｈ）の付加データとなる。入力である（ｉ１，ｉ２，ｊ１，ｊ２）と、出力とする（ｋ１，ｋ２，ｌ１，ｌ２）の関係は次の数３８のようになる。
【数３８】
0005554357.tif 000039
【００８６】
Ｗ’に関する方程式の解をＴｒ４／２（ｇ）とＴｒ４／２（ｈ）で表わすと次の数３９のようになる。ここで加算記号（＋）は有限体の元の加算を表す。
【数３９】
0005554357.tif 000040
【００８７】
Ｙ’に関する方程式の解をｇとｈで表わすと次の数４０のようになる。
【数４０】
0005554357.tif 000041
【００８８】
Ｔｒ４／２（ｇｈ）とＴｒ４／２（ｇｈ）＾｛ｐ＾ｍ｝をｇとｈで表わすと次の数４１のようになる。
【数４１】
0005554357.tif 000042
【００８９】
以上よりｋ２、ｋ１、ｌ２は次の数４２のように表わされる。
【数４２】
0005554357.tif 000043
【００９０】
次に、ｎ＝６の場合について説明する。ｎ＝６のとき特性多項式＝０をＸについて解くと、トレース値と付加データで元ｇと元ｇのフロベニウス共役元の拡大体表現を導出できる。６次の特性多項式を３つの２次式に分解して２次方程式を１回と３次方程式を１回解く。標数ｐ＝３より３次の解の公式は利用できないことに注意する。特性多項式を以下の数４３のように分解する。
【数４３】
0005554357.tif 000044
【００９１】
ｘ＾２−Ｔｒ６／３（ｇ）Ｘ＋１＝０をＸについて解くと次の数４４の解が得られる。
【数４４】
0005554357.tif 000045
【００９２】
上記のＸを計算するためには、先にＴｒ６／３（ｇ）を求めなければならない。Ｔｒ６／３（ｇ）とＴｒ６／３（ｇ）＾｛ｐ＾ｍ｝とＴｒ６／３（ｇ）＾｛ｐ＾｛２ｍ｝｝を解とする方程式は次の数４５のようになる。
【数４５】
0005554357.tif 000046
【００９３】
上記の方程式についてＺ＝−√｛Ｔｒ（ｇ）＾５−Ｔｒ（ｇ）＾｛２√３ｐ＾ｍ＋２｝−Ｔｒ（ｇ）＾｛3＋√３ｐ＾ｍ｝｝＋Ｔｒ（ｇ）＾｛３√３ｐ＾ｍ｝｝／｛Ｔｒ（ｇ）＾２Ｚ’｝−｛Ｔｒ（ｇ）＾｛√３ｐ＾ｍ｝＋Ｔｒ（ｇ）｝／Ｔｒ（ｇ）として変数変換を行って得られる次の数４６の方程式も、正規基底において計算コストなしで解が得られる。また、その３つの解は互いに０を１に、１を２に、２を０に置き換えた形になっており、｛０，１，２｝で区別できる。
【数４６】
0005554357.tif 000047
【００９４】
Ｔｒ６／３（ｇ）とＴｒ６／３（ｇ）＾｛ｐ＾ｍ｝とＴｒ６／３（ｇ）＾｛ｐ＾｛２ｍ｝｝の拡大体表現は次の数４７のようになる。
【数４７】
0005554357.tif 000048
【００９５】
ここでｉ１で代表されるベクトルがＺ’に関する上記の方程式の解を表しＦｐ＾｛３ｍ｝の元である。ｇとｇ＾｛ｐ＾｛３ｍ｝｝の拡大体表現は次の数４８のようになる。
【数４８】
0005554357.tif 000049
【００９６】
以上をまとめると元ｇと元ｇのフロベニウス共役元の拡大体表現は次の数４９のようになる。
【数４９】
0005554357.tif 000050
【００９７】
Ｘに関する上記の方程式の解はＦｐ＾｛６ｍ｝の元であり、±で区別される。ｉ１は０または１または２を取る。（ｉ１，ｉ２）∈｛０，１，２｝×｛＋，−｝をＴｒ（ｇ）の付加データとする。元ｈと元ｈのフロベニウス共役元の拡大体表現についても同様である。
【００９８】
ｉ１がＴｒ６／３（ｇ）を表し、ｊ１がＴｒ６／３（ｈ）を表すとして伸長後に乗算を行うと、その結果は次の数５０のようになる。複号同順に注意する必要がある。
【数５０】
0005554357.tif 000051
【００９９】
乗算値の取りうる値を根として持つ多項式＝０をＹについて解くと、乗算値の取りうる値を得ることができる。６次の上記多項式を３つの２次式に分解して２次方程式を１回と３次方程式を１回解く。標数ｐ＝３より３次の解の公式は利用できないことに注意する。上記多項式を次の数５１〜数５３のように分解する。
【数５１】
0005554357.tif 000052
【数５２】
0005554357.tif 000053
【数５３】
0005554357.tif 000054
【０１００】
ここで例えば次の数５４のように書きかえることができる。
【数５４】
0005554357.tif 000055
【０１０１】
すなわち、乗算値の取りうる値を根として持つ多項式を３つの２次式に分解する場合、根を求めるためには、先にＴｒ３／１［Ｔｒ６／３（ｇ）Ｔｒ６／３（ｈ）］とＴｒ３／１［Ｔｒ６／３（ｇ）Ｔｒ６／３（ｈ）＾｛ｐ＾ｍ｝］とＴｒ３／１［Ｔｒ６／３（ｇ）Ｔｒ６／３（ｈ）＾｛ｐ＾｛２ｍ｝｝］を求めなければならない。これらを解とする方程式は次の数５５および数５６のようになる。
【数５５】
0005554357.tif 000056
【数５６】
0005554357.tif 000057
【０１０２】
Ｔｒ（ｇ＾｛ｐ＾ｍ＋２｝）とＴｒ（ｇ＾｛２ｐ＾ｍ＋１｝）との和および積は、先に示した通りＴｒ（ｇ）から計算できる。すなわち次の数５７の２次方程式の解を計算すればよい。
【数５７】
0005554357.tif 000058
【０１０３】
Ｔｒ（ｈ＾｛ｐ＾ｍ＋２｝）とＴｒ（ｈ＾｛２ｐ＾ｍ＋１｝）についても同様である。Ｗに関する３次方程式について変数変換を行って正規基底において計算コストなしで解が得られる形にする。Ｗの１次の係数をｂと置いて、Ｗ＝−√●／｛Ｔｒ（ｇ）＾２Ｔｒ（ｈ）＾２Ｗ’｝−ｂ／｛Ｔｒ（ｇ）Ｔｒ（ｈ）｝と変換すると次の数５８の方程式が得られる。また、その３つの解は互いに０を１に、１を２に、２を０に置き換えた形になっており、｛０，１，２｝で区別できる。
【数５８】
0005554357.tif 000059
【０１０４】
Ｔｒ３／１［Ｔｒ６／３（ｇ）Ｔｒ６／３（ｈ）］とＴｒ３／１［Ｔｒ６／３（ｇ）Ｔｒ６／３（ｈ）＾｛ｐ＾ｍ｝］とＴｒ３／１［Ｔｒ６／３（ｇ）Ｔｒ６／３（ｈ）＾｛ｐ＾｛２ｍ｝｝］の拡大体表現は次の数５９のようになる。
【数５９】
0005554357.tif 000060
【０１０５】
ここでｌ１で代表されるベクトルがＷ’に関する上記の方程式の解を表しＦｐ＾｛３ｍ｝の元である。乗算値Ｔｒ（ｇｈ）とＴｒ（ｇ＾｛ｐ＾｛３ｍ｝｝ｈ）の取りうる値は次の数６０のようになる。
【数６０】
0005554357.tif 000061
【０１０６】
以上をまとめると乗算値の取りうる値は次の数６１のようになる。
【数６１】
0005554357.tif 000062
【０１０７】
ある（ｌ１，ｌ２）が乗算値Ｔｒ（ｇｈ）を表すとすると、乗算値と付加データで乗算値の拡大体表現を次の数６２のように表すことができる。
【数６２】
0005554357.tif 000063
【０１０８】
一方入力は次の数６３のように表わせた。
【数６３】
0005554357.tif 000064
【０１０９】
従って上記の出力の式と、入力から計算される乗算の式と、を互いに等しいとして、入力である（ｉ１，ｉ２，ｊ１，ｊ２）から出力とする（ｋ１，ｋ２，ｌ１，ｌ２）を計算する。
【０１１０】
このように、第１の実施形態にかかる演算装置では、例えば射影表現または拡大体表現への表現変換を行うことなく、トレース表現での演算を行うことができる。これにより、全体の計算量を削減可能となる。
【０１１１】
（第２の実施形態）
第２の実施形態では、特性多項式の係数が全て決定している場合における乗算方法を示す。
【０１１２】
図３は、第２の実施形態にかかる演算装置１００−２の構成の一例を示すブロック図である。図３に示すように、演算装置１００−２は、受付部１０１と、係数算出部１０２−２と、求解部１０３と、選択部１０４と、決定部１０５と、出力制御部１０６と、を備えている。
【０１１３】
第２の実施形態では、係数算出部１０２−２の機能が第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる演算装置１００のブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１１４】
係数算出部１０２−２は、予め求められた特性多項式の係数を用いて、乗算値の取りうる値を根として持つ多項式の係数を算出する点が、第１の実施形態の係数算出部１０２と異なっている。以下に本実施形態での係数の算出方法について説明する。
【０１１５】
特性多項式が次の数６４のように与えられるとする。定数項は、代数的トーラスＴｎ（Ｆｐ＾ｍ）の元ｇのノルムが１であることより導かれる。
【数６４】
0005554357.tif 000065
【０１１６】
乗算値の取りうる値を根として持つ次の数６５の多項式の係数を特性多項式の係数から計算する。
【数６５】
0005554357.tif 000066
【０１１７】
ｄ２（ｇ，ｈ）は、例えばｎ＝２のときｄ２（ｇ，ｈ）＝ａ２（ｇ）Ｔｒ（ｈ＾２）＋Ｔｒ（ｇ＾２）ａ２（ｈ）となる。ｎ＝３のときｄ２（ｇ，ｈ）＝ａ２（ｇ）Ｔｒ（ｈ＾２）＋Ｔｒ（ｇ＾２）ａ２（ｈ）＋ａ２（ｇ）ａ２（ｈ）、ｎ＝４のときｄ２（ｇ，ｈ）＝ａ２（ｇ）Ｔｒ（ｈ＾２）＋Ｔｒ（ｇ＾２）ａ２（ｈ）＋ａ２（ｇ）ａ２（ｈ）＋２ａ２（ｇ）＋２ａ２（ｈ）−１２となる。ここでａｉ（ｇ）とｄｉ（ｇ，ｈ）は以下の数６６のように表わされている。ｄｉ（ｈ）も同様である。
【数６６】
0005554357.tif 000067
【０１１８】
従って、係数算出部１０２−２は、特性多項式の係数と特性多項式から得られるトレース値の漸化式を用いて、ｄｉ（ｇ，ｈ）を、ｄｉ（ｇ）、ｄｉ（ｈ）、Ｔｒ（ｇ＾ｉ）および、Ｔｒ（ｈ＾ｉ）から計算することで、乗算値の取りうる値を根として持つ多項式の係数を計算する。
【０１１９】
求解部１０３は、上記多項式の求根を行う。選択部１０４は、得られたｎ個の根から、元ｇに関する特性多項式の係数に対する付加データと元ｈに関する特性多項式の係数に対する付加データとを用いて乗算値を１つ選択する。また、決定部１０５が、元ｇに関する特性多項式の係数に対する付加データと元ｈに関する特性多項式の係数に対する付加データとを用いて、乗算値の付加データを決定する。
【０１２０】
以上説明したとおり、第１から第２の実施形態によれば、表現変換をせずにトレース表現での演算を行うことができ、全体の計算量を削減することができる。
【０１２１】
次に、第１または第２の実施形態にかかる演算装置のハードウェア構成について図４を用いて説明する。図４は、第１または第２の実施形態にかかる演算装置のハードウェア構成を示す説明図である。
【０１２２】
第１または第２の実施形態にかかる演算装置は、ＣＰＵ（Central  Processing  Unit）５１などの制御装置と、ＲＯＭ（Read  Only  Memory）５２やＲＡＭ（Random  Access  Memory）５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、各部を接続するバス６１を備えている。
【０１２３】
第１または第２の実施形態にかかる演算装置で実行される演算プログラムは、ＲＯＭ５２等に予め組み込まれて提供される。
【０１２４】
第１または第２の実施形態にかかる演算装置で実行される演算プログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact  Disk  Read  Only  Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact  Disk  Recordable）、ＤＶＤ（Digital  Versatile  Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供されるように構成してもよい。
【０１２５】
さらに、第１または第２の実施形態にかかる演算装置で実行される演算プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、第１または第２の実施形態にかかる演算装置で実行される演算プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１２６】
第１または第２の実施形態にかかる演算装置で実行される演算プログラムは、コンピュータを上述した演算装置の各部（受付部、係数算出部、求解部、選択部、決定部、出力制御部）として機能させうる。このコンピュータは、ＣＰＵ５１がコンピュータ読取可能な記憶媒体から演算プログラムを主記憶装置上に読み出して実行することができる。
【０１２７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１２８】
１００、１００−２  演算装置
１０１  受付部
１０２、１０２−２  係数算出部
１０３  求解部
１０４  選択部
１０５  決定部
１０６  出力制御部
【図１】
0005554357.tif 000068
【図２】
0005554357.tif 000069
【図３】
0005554357.tif 000070
【図４】
0005554357.tif 000071