JP3565494B2 - 拡大体演算装置およびそのプログラム記録媒体 - Google Patents

Description

【０００１】
【発明の属する技術分野】
この発明は、例えば楕円曲線暗号／署名などの情報セキュリティ技術を実現するために用いられ、有限体ＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大体ＧＦ（ｑ^ｋ ）＝ＧＦ（ｑ［ｘ］／ｆ（ｘ））装置に関する。
【０００２】
【従来の技術】
楕円曲線暗号を実現する際、楕円曲線の定義体として、有限体ＧＦ（ｑ）（但しｑは計算機の語長に近い素数または素数のべき（冪））のｋ次拡大体ＧＦ（ｑ^ｋ ）を用いる場合がある。拡大体ＧＦ（ｑ^ｋ ）上の演算を高速化できれば、拡大体ＧＦ（ｑ^ｋ ）上で定義された楕円曲線暗号の処理速度を高速化できる。今ＧＦ（ｑ）のｋ次拡大体ＧＦ（ｑ^ｋ ）上の元Ａ及びＢのＧＦ（ｑ^ｋ ）上の積Ｃ＝Ａ×Ｂの演算を実行する装置を構成したいとする。拡大に用いる既約多項式をＧＦ（ｑ）上のｆ（ｘ）とし、代数方程式ｆ（ｘ）＝０の解の一つをαとすると、一般にＧＦ（ｑ^ｋ ）上の元Ａは、ＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルａ_ｉ （但し０＜ｉ＜ｋ）を用いて、
Ａ＝Σ_ｉ＝０ ^ｋ−１ ａ_ｉ α^ｉ
と一意に書くことが出来る。ＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルａ_ｉ をＡの多項式基底による表現と呼ぶ。即ちＡ及びＢの多項式基底による表現ａ_ｉ 及びｂ_ｉ （但し０＜ｉ＜ｋ）を入力とし、Ｃの多項式基底による表現ｃ_ｉ （但し０＜ｉ＜ｋ）を出力とする、演算装置を構成する場合、Ｃを計算する為には、まずＡ及びＢをαに関する多項式と見做し、Ｃ＝Ａ×Ｂを多項式演算で計算する。即ち
Σ_ｊ＝０ ^２ｋ−２ｄ_ｊα^ｊ＝（Σ_ｉ＝０ ^ｋ−１ａ_ｉα^ｉ）×（Σ_ｉ＝０ ^ｋ−１ｂ_ｉα^ｉ） （１）
なるｄ_ｊ （但し０＜ｊ＜２ｋ−１）を求める。この時ＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元ベクトルｄ_ｊ （但し０＜ｊ＜２ｋ−１）は、ＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルではないので、Ｃの多項式基底による表現とはなっていない。Ｃの多項式基底による表現を得る為には
Σ_ｉ＝０ ^ｋ−１ ｃ_ｉ α^ｉ ＝Σ_ｊ＝０ ^２ｋ−２ｄ_ｊ α^ｊ （２）
なるｃ_ｉ （但し０＜ｉ＜ｋ）を求めなくてはならない。この目的の為にはｆ（α）＝０が用いられる。ｆ（ｘ）がｘのｋ次多項式であるからｆ（α）＝Ｐ_０ ＋Ｐ_１ α＋Ｐ_２ α^２ ＋…＋Ｐ_ｋ−１ α^ｋ−１ ＋Ｐ_ｋ α^ｋ ＝０の関係から、
α^ｋ ＝Σ_ｊ＝０ ^ｋ−１ ｒ_ｊ α^ｊ （３）
とすることができる。従って、式（３）を使ってｋ次以上のαの多項式をｋ−１次のαの多項式に変換することが出来る。この操作を還元と呼ぶ。もし拡大に用いる多項式ｆ（ｘ）がＧＦ（ｑ）上既約ｋ次２項多項式ｘ^ｋ−ｒであれば、α^ｋ ＝ｒであるので、整数ｍに対してα^ｍ＝ｒα^ｍ−ｋである。従って、ｋ−１箇のα^ｋ 以上の各項のｄ_ｊ（ｊ＝ｋ〜２ｋ−２ ）をｒ倍して次数をｋ−１以下にすると共に、その下げた次数と対応する次数のｄ_ｊ（ｊ＝０〜ｋ−１）と加算して各ｃ_ｉ（ｉ＝０〜ｋ−１）を求めることができ、つまりｋ−１回のｒ倍と加算を用いて還元を実行することが出来る。２項多項式ｘ^ｋ−ｒには上記のような性質があるので、従来、拡大体上の演算を高速に行う為には拡大に用いる多項式を２項多項式ｘ^ｋ−ｒにすることが必要とされてきた（特願平１０−２５５５２６号参照）。
【０００３】
【発明が解決しようとする課題】
上記２項多項式による拡大体演算法では、ｑやｋの値によってはＧＦ（ｑ）上既約２項多項式ｆ（ｘ）＝ｘ^ｋ −ｒが存在しなかったり、ｒ倍が必ずしも高速に実行できない場合が数多く存在した。例えばｋ＝１３の場合２^１２より大きい素数のうちの最初の２００個の中で、−１００＜ｒ＜１００なる既約２項多項式が存在する素数はわずか１２個に過ぎない。この発明は、どのような場合でも拡大体上演算を高速に実行することを可能とする拡大体演算装置を提供することを目的とする。
【０００４】
【課題を解決するための手段】
以下にこの発明の原理を説明する。簡単のためαのｍ次多項式をｆ（α）＝０を用いてｍ−１次多項式に変換することを考える（但しｋ＜ｍ＜２ｋ）。αのｍ次多項式を
Σ_ｉ＝０ ^２ｋ−１ｄ_ｉα^ｉ＝Σ_ｉ＝０ ^ｋ−１ｄ_ｉα^ｉ＋Σ_ｉ＝０ ^ｋ−１ｄ_ｉ＋ｋ（α^ｉ・α^ｋ） （４）
とすることができる。ｍ次多項式をｍ−１次多項式にする為には、αのすべてのｋ次以上の冪をｆ（α）＝０の関係から次数を１次下げれば良い。即ち式（３）を使って式（４）を

と変形すれば良い。式（５）の左辺がαのｍ次式（ｋ＜ｍ＜２ｋ）なら式（５）の右辺はαのｍ−１次式である。式（５）の右辺をαの多項式と見做しα^ｉ の係数をｄ′_ｉ とおくと式（５）は、
Σ_ｉ＝０ ^２ｋ−１ｄ_ｉ α^ｉ ＝Σ_ｉ＝０ ^２ｋ−１ｄ′_ｉ α^ｉ （６）
とかける。但しｉ＞ｍの場合ｄ′_ｉ ＝０である。ＧＦ（ｑ）上の元を要素に持つ２ｋ次元ベクトルｄ_ｉ を縦ベクトルで
【０００５】
【数２】

と表現するなら、この過程は以下のように行列を用いて
【０００６】
【数３】

【０００７】
と表現することが出来る（空白は０と見做す、以下も同様）。右辺の２ｋ行２ｋ列の行列内の縦線と横線は便宜上付けたものであり、この縦線、横線で分けられた左上の小行列（単位行列）は式（５）の右辺第１項と対応し、右の上下の小行列は右第２項と対応する。説明の便宜の為、区切られた小行列に名前を付け式（７）を次式
【０００８】
【数４】

と表現することにする。Ｉはｋ行ｋ列の単位行列であり、Ｏはｋ行ｋ列の零行列である。また、
【０００９】
【数５】

【００１０】
とする。式（８）で行列を縦ベクトルに１回かけることはｆ（α）＝０の関係を使ってαのｍ次式をｍ−１次式に変換することに相当している。従ってαの２ｋ−１次式をｋ−１次式に変換することは式（８）の行列を縦ベクトルにｋ回かけることに他ならない。即ち還元とは
【００１１】
【数６】

に他ならない（但しｉ＞ｋの時ｃ_ｉ ＝０）。
【００１２】
【数７】

を２乗、３乗と順次計算し、ｋ乗まで行うと、
【００１３】
【数８】

【００１４】
となる。所で
Ｒ_１ ^ｋ−Ｉ＝（Ｒ_１ −Ｉ）（Ｒ_１ ^ｋ−１＋Ｒ_１ ^ｋ−２＋…＋Ｒ_１ ＋Ｉ）
であり、Ｒ_１ は式（１０）の行列であるから、これをｋ乗すると０となる。よって
−Ｉ＝（Ｒ_１ −Ｉ）（Ｒ_１ ^ｋ−１＋Ｒ_１ ^ｋ−２＋…＋Ｒ_１ ＋Ｉ）
両辺に（Ｒ_１ −Ｉ）^−１を乗算すると、
−（Ｒ_１ −Ｉ）^−１＝Ｒ_１ ^ｋ−１＋Ｒ_１ ^ｋ−２＋…＋Ｒ_１ ＋Ｒ^０
（Ｉ−Ｒ_１ ）^−１＝Σ_ｉ＝０ ^ｋ−１ Ｒ_１ ^ｉ
この関係を式（１１）に代入し、またＲ_１ ^ｋ＝０であるから
【００１５】
【数９】

となる。Ｒ′＝Ｒ_０ （Ｉ−Ｒ_１ ）^−１とおけば式（１０）は
【００１６】
【数１０】

【００１７】
とかける。二つのｋ−１次多項式の積は２ｋ−２次多項式であるので、ＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大ＧＦ（ｑ^ｋ ）＝ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の２つの元の乗算を考える上ではｄ_２ｋ−１＝０である。従ってＲ′のなかで実際に必要な列は第０列から第ｋ−２列までである。行列Ｒ′の第０列から第ｋ−２列までのｋ行（ｋ−１）列の行列Ｒを還元行列と呼び、式（１３）はＲを用い簡単に
【００１８】
【数１１】

【００１９】
と表わせる。式（１４）よりＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の２つの元の乗算が高速に計算できるかどうかは還元行列Ｒの性質に依存することが判る。一般の拡大体ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の２つの元の乗算における還元には式（７）、（８）、（１４）からｋ（ｋ−１）回のＧＦ（ｑ）上定数倍とｋ（ｋ−１）回のＧＦ（ｑ）上加算の演算が必要である。一方、従来高速とされてきた既約２項多項式による拡大体ＧＦ（ｑ）［ｘ］／（ｘ^k −ｒ）の場合Ｒ′＝ｒＩになるので還元には（ｋ−１）回のＧＦ（ｑ）上定数倍（ｒ倍）と（ｋ−１）回のＧＦ（ｑ）上加算の演算しか必要ない。ところで、２項式ｘ^k −ｒが既約かそうでないかは定義体ｑと拡大次数ｋの値によって決まる。例えばｑ＝６５５３９、ｋ＝１０の場合、既約２項式は存在しない。そのような場合は従来効率的な乗算装置は構成できないと考えられていた。あるいはｑ＝４２０１，ｋ＝１０の場合、既約２項式ｘ^k −ｒはｒ＝±１１、±１３、±１９、…であるが、加算のみでこれらｒ倍を実現するには少なくとも５回の加算が必要であり、必ずしもｒ倍が高速であるとは云えない。しかし、このような場合でも以下の手順に従えば効率的な乗算装置を構成できる。
【００２０】
Ｓｔｅｐ１：探索し得る全ての既約多項式に対応する還元行列Ｒを上記手順に従い計算する。
Ｓｔｅｐ２：Ｒによる還元演算の演算コストに関する性質を調べる。
Ｓｔｅｐ３：探索し得る全ての既約多項式の中で最も演算コストの少ない既約多項式ｆ（ｘ）を見つけ出す。
Ｓｔｅｐ４：ｆ（ｘ）における還元演算装置の構成を行い、乗算装置を構成する。
【００２１】
上記手順の、探索し得る既約多項式に、既約２項多項式を含めても手順は全く変わらない。従ってこのようにすれば、既約２項多項式をも含めた、探索し得る全ての既約多項式に関して、最も効率的な乗算装置を構成できる。
つまりこの発明では前述のように決めた既約多項式が用いられ還元演算の演算コストが少ないものであり、つまり還元演算手段に用いられる還元行列Ｒはその行列の要素数中の半分以上が零要素であり、還元演算において行列Ｒの零要素の部分のＧＦ（ｑ）上積和演算が省略され、還元演算を高速に行うことができる。
あるいは、一般のｋ行ｋ−１列の行列を基本変形により標準形
【００２２】
【数１２】

【００２３】
にするために必要な基本変形の最小回数をＭ回とすると還元行列ＲはＭ／２回以下の基本変形で標準形になるようなものであり、行列Ｒはこのような性質があるため、還元演算におけるある行の部分的な演算結果を他の行の演算に流用するように還元演算手段が多く構成され、それだけ還元を高速に行うことができる。
このような構成とすることにより、既約多項式としては３項よりなる３次以上のもの、あるいは４項よりなる４次以上のものが用いられる。
一般に式（１２）の行列Ｖは
【００２４】
【数１３】

【００２５】
のように分解できる。これは、還元を行う場合に次数の高い項から順にｆ（α）＝０の関係を使って一次ずつ次数を下げてゆくことに対応する。従って、２項多項式でなくとも項数が少なく、ｒ_ｉ 倍が高速なら還元を高速に行うことができる。また、項数が多くとも、行列Ｖを何らかの分解によって要素の絶対値が小さい少数の疎行列の積に分解できれば同様に還元を高速に行うことができる。このような分解が出来ると云うことは、式（１４）の計算に於いて、ある行の計算過程に於ける部分的な結果を他の行の計算に流用できることに相当している。例えばｑ＝６５５３９、ｋ＝１０の場合はｆ（ｘ）＝ｘ^１０−ｘ^９ −１あるいはｆ（ｘ）＝ｘ^１０−ｘ−１、ｑ＝４２０１、ｋ＝１０の場合はｆ（ｘ）＝ｘ^１０＋ｘ^９ ＋１あるいはｆ（ｘ）＝ｘ^１０＋ｘ＋１等は２項式ではないが還元を高速に行うことができる。
【００２６】
【発明の実施の形態】
以下にこの発明の実施例を示す。
図１はこの発明を拡大体ＧＦ（ｑ^ｋ ）の乗算装置に適用した場合である。この乗算装置１ＡはＧＦ（ｑ^ｋ ）上の元Ａ及びＢを入力し、その積Ｃ＝Ａ×Ｂを出力するものであり、ＧＦ（ｑ^ｋ ）上の元Ａ、Ｂ、Ｃは、それぞれＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルａ_ｉ ，ｂ_ｉ ，ｃ_ｉ （但し０＜ｉ＜ｋ）で表されており、ＧＦ（ｑ）上ｋ次既約多項式ｆ（ｘ）＝０の一つの解をαとすると、それぞれ
Ａ＝Σ_ｉ＝０ ^ｋ−１ ａ_ｉ α^ｉ ，Ｂ＝Σ_ｉ＝０ ^ｋ−１ ｂ_ｉ α^ｉ ，Ｃ＝Σ_ｉ＝０ ^ｋ−１ ｃ_ｉ α^ｉ
を意味している。この実施例では簡単のため、ｋ＝１０の場合を説明するが、一般にｆ（ｘ）の項数をｍとするとｍ−１以上のｋでもこの発明の効果を享受出来る。装置１Ａは多項式乗算装置１Ｂと還元装置１Ｃとからなる。
【００２７】
多項式乗算装置１ＢはＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルａ_ｉ ，ｂ_ｉ （但し０＜ｉ＜ｋ）を入力とし、ｘのＧＦ（ｑ）上係数多項式
Σ_ｊ＝０ ^２ｋ−２ｄ_ｊｘ^ｊ＝（Σ_ｉ＝０ ^ｋ−１ａ_ｉｘ^ｉ）（Σ_ｉ＝０ ^ｋ−１ｂ_ｉｘ^ｉ） （１６）
の係数ｄ_ｊ （但し０＜ｊ＜２ｋ−１）を演算して出力する。
還元装置１Ｃは係数ｄ_ｉ が入力され、式（１４）が演算され、ｆ（α）＝０を満たすαについて
Σ_ｉ＝０ ^ｋ−１ ｃ_ｉ α^ｉ ＝Σ_ｊ＝０ ^２ｋ−２ｄ_ｊ α^ｊ （１７）
なる係数ｃ_ｉ （但し０＜ｉ＜ｋ）を出力する。
【００２８】
還元装置１Ｃは例えば図２に示すように構成される。この例は還元行列Ｒはその構成要素の半分以上が零要素の場合で具体的にｋ＝１０、ｆ（ｘ）＝ｘ^１０−ｘ−１が用いられその還元行列は式（９）、式（１２）から次式となる。
【００２９】
【数１４】

【００３０】
つまり行列Ｒはその要素数１０×９＝９０のうち零要素の数が７２、つまり８０％もある。この還元行列Ｒを用いた式（１４）の演算は図２に示すように構成することができる。図２中の（＋）はＧＦ（ｑ）上加算を表わす。この場合は単位行列Ｉも還元行列Ｒも１の要素と零の要素とよりなり、ｄ₀ 〜ｄ₉ が単位行列Ｉとの演算であり、ｄ₁₀〜ｄ₁₈が還元行列Ｒとの演算であり、各行ごとに単位行列Ｉ、還元行列Ｒ中の１の要素との演算がなされるｄ₀ 〜ｄ₁₈が加算される。例えば第２行目では単位行列Ｉとの演算はｄ₁ であり、還元行列Ｒとの演算はｄ₁₀とｄ ₁₁ であり、これらｄ₁ とｄ₁₀とｄ ₁₁ が加算されてｃ₁ となる。
【００３１】
このように還元装置１Ｃが構成されているため、この装置１Ｃでは還元を行う為のコストは加算１８回である。一般にｋ次式ｆ（ｘ）＝ｘ^ｋ −ｘ−１が既約の場合還元を行う為のコストは加算２（ｋ−１）回であり、２項式の定数倍（ｒ倍）が加算１回より高速に行えない場合この実施例の方が高速になる。
還元装置１Ｃの他の構成例を図３に示す。この場合は先に述べたように一般のｋ行ｋ−１列の行列を基本変形により標準形にするために必要な基本変形の回数がＭ回の場合に、還元行列ＲがＭ／２回以下の基本変形で標準形となる還元行列Ｒが用いられた場合で、この実施例では還元行列Ｒはｋ＝１０，ｆ（ｘ）＝ｘ^１０−ｘ^９ −１が用いられ、次式で与えられる。
【００３２】
【数１５】

【００３３】
なおこの行列Ｒは、例えば第９行の各要素で他の全ての行の対応する要素をそれぞれ引算し、その結果の行列について第８行の各要素で他の全ての行の対応する要素をそれぞれ引算し、その結果の行列について第７行の各要素で他の全ての行の対応する要素をそれぞれ引算し、以下同様のことを行えば９回という少ない回数の基本変形で標準形にすることができるものである。
このような還元行列では、図３に示すように例えばｃ_７ を求めるための演算ｄ_１７（＋）ｄ_１８（＋）ｄ_７ 中のｄ_１７（＋）ｄ_１８の演算結果はｃ_６を求めるための演算ｄ_１６（＋）ｄ_１７（＋）ｄ_１８（＋）ｄ_６ 中のｄ_１７（＋）ｄ_１８の演算に流用され、またｃ_５ を求めるための演算ｄ_１５（＋）ｄ_１６（＋）ｄ_１７（＋）ｄ_１８（＋）ｄ_５ 中のｄ_１６（＋）ｄ_１７（＋）ｄ_１８の演算はｃ_６ を求めるための演算中のｄ_１６（＋）ｄ_１７（＋）ｄ_１８の演算結果が流用され、以下同様に、ある行の部分的な演算結果が他の行の演算に流用され、特に図３の例ではその流用演算手段が順次縦続的に行われているため、ここに演算する場合と比較して、全体としての演算回数が少なくなる。この還元装置１Ｃでは還元を行う為のコストは加算１８回である。一般にｋ次式ｆ（ｘ）＝ｘ^ｋ −ｘ^ｋ−１ −１が既約の場合還元を行う為のコストは加算２（ｋ−１）回であり、２項式の定数倍（ｒ倍）が加算１回より高速に行えない場合この実施例の方が高速になる。
【００３４】
この発明の拡大体乗算をコンピュータにプログラムを実行させて行うこともできる。図４にその構成を示す。入出力インターフェース１１、記憶部１２、ＣＰＵ（中央演算装置）１３、コンピュータを動作させる基本プログラムが記憶されたプログラムメモリ１４、各種応用プログラムが記憶されたハードディスク１５、ＲＡＭ１６などがバス１７に接続されている。ハードディスク１５からこの拡大体乗算を行うためのプログラムがＲＡＭ１６に転送し、そのプログラムを実行することにより、入出力インターフェース１１からＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルで表されるＧＦ（ｑ^ｋ ）上の元Ａ、Ｂが入力されると、これらを取込み記憶部１２に格納する（Ｓ１）（図５参照）。
【００３５】
その後、記憶部１２から元Ａ、Ｂを取出して、ＣＰＵ１３は多項式演算処理１８を実行して、つまりａ_ｉ 及びｂ_ｉ （０＜ｉ＜ｋ）から式（１６）を満たす係数ｄ_ｊ （０＜ｊ＜２ｋ−１）を求め、これら係数ｄ_ｊを記憶部１２に格納する（Ｓ２）。
次に記憶部１２からｄ_ｊ を取出し、還元演算処理１９を実行して、式（１４）を演算することにより式（１７）を満たす係数ｃ_ｉ を求め（Ｓ３）、この結果であるＧＦ（ｑ）上の元ｃ_ｉ のベクトルからなるＧＦ（ｑ^ｋ ）上の元Ｃを出力インターフェース１１から外部へ出力する（Ｓ４）。
【００３６】
図２に示した還元装置１Ｃの演算をコンピュータにより、つまり、図５中の還元演算処理を行わせるには、例えば図６に示す手順で行えばよい。ｄ_０ とｄ_１０を記憶部１２から取出し、これらを加算してｃ_０ として記憶部１２に格納し（Ｓ１）、
記憶部１２からｄ_１ ，ｄ_１０，ｄ_１１を取出してこれらを加算してｃ_１ として記憶部１２に格納し（Ｓ２）、
記憶部１２からｄ_２ ，ｄ_１１，ｄ_１２を取出してこれらを加算してｃ_２ として記憶部１２に格納し（Ｓ３）、
記憶部１２からｄ_３ ，ｄ_１２，ｄ_１３を取出し、これらを加算してｃ_３ として記憶部１２に格納し（Ｓ４）、
記憶部１２からｄ_４ ，ｄ_１３，ｄ_１４を取出してこれらを加算してｃ_４ として記憶部１２に格納し（Ｓ５）、
記憶部１２からｄ_５ ，ｄ_１４，ｄ_１５を取出して、これらを加算してｃ_５ として記憶部１２に格納し（Ｓ６）、
記憶部１２からｄ_６ ，ｄ_１５，ｄ_１６を取出し、これらを加算してｃ_６ として記憶部１２に格納し（Ｓ７）、
記憶部１２からｄ_７ ，ｄ_１６，ｄ_１７を取出し、これらを加算してｃ_７ として記憶部１２に格納し（Ｓ８）、
記憶部１２からｄ_８ ，ｄ_１７，ｄ_１８を取出し、これらを加算してｃ_８ として記憶部１２に格納し（Ｓ９）、
記憶部１２からｄ_９ ，ｄ_１８を取出し、これらを加算してｃ_９として記憶部１２に格納する（Ｓ１０）。
【００３７】
なおこれらのステップＳ１〜Ｓ１０の順番は任意でよい。
図３に示した還元装置をコンピュータにより還元演算処理をさせるには例えば図７に示すようにすればよい。
まず記憶部１２からｄ_１８を取出し、これをｔとしてＣＰＵ１３内のレジスタに一時格納し（Ｓ１）、
記憶部１２からｄ_８ とｄ_１７を取出し、そのｄ_１７とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_８ を加算してｃ_８ として記憶部１２に記憶し（Ｓ２）、
記憶部１２からｄ_７ とｄ_１６を取出し、ｄ_１６とｔを加算し、その結果でレジスタ内のｔを更新すると共に、そのｔとｄ_７ を加算してｃ_７ として記憶部１２に格納し（Ｓ３）、
記憶部１２からｄ_６ ，ｄ_１５を取出し、ｄ_１５とｔを加算し、その結果でレジスタ内のｔを更新すると共にｄ_６ とｔを加算してｃ_６ として記憶部１２に格納し（Ｓ４）、
記憶部１２からｄ_５ ，ｄ_１４を取出し、ｄ_１４とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_５ を加算してｃ_５ として記憶部１２に格納し（Ｓ５）、
記憶部１２からｄ_４ ，ｄ_１３を取出し、ｄ_１３とｔを加算し、その結果でレジスタ内のｔを更新すると共に、そのｔとｄ_４ を加算してｃ_４ として記憶部１２に格納し（Ｓ６）、
記憶部１２からｄ_３ ，ｄ_１２を取出し、ｄ_１２とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_３ を加算してｃ_３ として記憶部１２に格納し（Ｓ７）、
記憶部１２からｄ_２ ，ｄ_１１を取出し、ｄ_１１とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_２ を加算してｃ_２ として記憶部１２に格納し（Ｓ８）、
記憶部１２からｄ_１ ，ｄ_１０を取出し、ｄ_１０とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_１ を加算してｃ_１ として記憶部１２に格納し（Ｓ９）、
記憶部１２からｄ_０ ，ｄ_９ を取出し、ｄ_９ とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_０ を加算してｃ_０ として記憶部１２に格納する（Ｓ１０）。
【００３８】
ｋ次拡大に用いるｋ次多項式ｆ（ｘ）としてはその最高次数の係数で各項の係数を割算した時に、つまりモニックした時に、各項の係数が±１になるものが好ましい。このようにすると、還元行列Ｒの構成要素が零要素と１要素とで構成され、定数倍演算をしなくてすみ、高速演算が可能となる。
図４において、駆動部２１を介して外部ディスク装置２２を駆動し、外部ディスク装置２２に記録されたプログラムを実行して前記処理を行うようにしてもよい。また上述ではこの発明を乗算装置に適用したが、一般にＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大体ＧＦ（ｑ^ｋ ）上の演算において、演算実行中にＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元縦ベクトルｄをＧＦ（ｑ）上の元を要素に持つｋ次元縦ベクトルｃに、ｆ（ｘ）＝０の関係を用いて還元を行う拡大体演算装置に適用できる。
【００３９】
【発明の効果】
従来ＧＦ（ｑ）上既約２項式が存在しない場合ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上乗算において還元にｋ（ｋ−１）回のＧＦ（ｑ）上定数倍とｋ（ｋ−１）回のＧＦ（ｑ）上加算の演算が必要と考えられていたが、この発明によれば、最も効率の良い時２（ｋ−１）回のＧＦ（ｑ）上加算で還元を実行できる。上記ＧＦ（ｑ）上定倍数はＧＦ（ｑ）上加算より十分大きなコストがかかるが、ＧＦ（ｑ）上定数倍をＧＦ（ｑ）上加算の５倍と見積もっても、ｋ＝１０の場合で還元が３０倍高速化できる。ＧＦ（ｑ）上既約２項式ｘ^ｋ −ｒが存在しても、ｒ倍が必ずしも高速に実行できない場合ｒ倍をＧＦ（ｑ）上加算の５倍と見積もると、最も効率の良い場合、この発明により、還元が３倍高速化できる。
【図面の簡単な説明】
【図１】ＧＦ（ｑ^ｋ ）乗算装置の構成を示す図。
【図２】図１中の還元装置１Ｃの具体例を示す図。
【図３】図１中の還元装置１Ｃの他の具体例を示す図。
【図４】この発明装置をコンピュータにより実現する例を示すブロック図。
【図５】ＧＦ（ｑ^ｋ ）乗算の処理の流れを示す図。
【図６】還元演算処理の流れを示す図。
【図７】還元演算処理の他の例の流れを示す図。

Claims (8)

1. ｑを素数または素数の冪とし、有限体ＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大ＧＦ（ｑ^k ）＝ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の元の演算実行中にＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元縦ベクトル［ｄ］をＧＦ（ｑ）上の元を要素に持つｋ次元縦ベクトル［ｃ］にｆ（ｘ）＝０を用いて還元を行う還元手段を備える演算装置であって、
   上記還元手段は上記縦ベクトル［ｄ］を入力して、ＧＦ（ｑ）上の元を要素に持つｋ行ｋ列単位行列Ｉ及び上記ｋ次多項式ｆ（ｘ）により定まるＧＦ（ｑ）上の元を要素に持つｋ行ｋ−１列の行列Ｒについて、
   ［ｃ］＝［Ｉ｜Ｒ］［ｄ］
   を演算して、その結果を上記縦ベクトル［ｃ］として出力するものであり、
   上記行列Ｒは探索し得る既約多項式と対応する還元行列中の還元演算コストが最も少ないものであることを特徴とする拡大体演算装置。
2. ｑを素数または素数の冪とし、有限体ＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大ＧＦ（ｑ^ｋ ）＝ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の元の演算実行中にＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元縦ベクトル［ｄ］をＧＦ（ｑ）上の元を要素に持つｋ次元縦ベクトル［ｃ］にｆ（ｘ）＝０を用いて還元を行う還元手段を備える演算装置であって、
   上記還元手段は上記縦ベクトル［ｄ］を入力して、ＧＦ（ｑ）上の元を要素に持つｋ行ｋ列単位行列Ｉ及び上記ｋ次多項式ｆ（ｘ）により定まるＧＦ（ｑ）上の元を要素に持つｋ行ｋ−１列の行列Ｒについて、
   ［ｃ］＝［Ｉ｜Ｒ］［ｄ］ （Ｅ）
   を演算して、その結果を上記縦ベクトル［ｃ］として出力するものであり、
   一般のｋ行ｋ−１列の行列を基本変形により標準形
   

   

   にする為に必要な基本変形の最小回数をＭ回とすると、上記行列ＲはＭ／２回以下の基本変形で標準形になるものであることを特徴とする拡大体演算装置。
3. 請求項２記載の装置において、
   上記還元手段は上記式（Ｅ）の演算において、ある行の部分的な演算結果を他の行演算に流用する手段を備えることを特徴とする拡大体演算装置。
4. 請求項１乃至３の何れかに記載の装置において、
   上記多項式ｆ（ｘ）は３項又は４項からなる３次又は４次以上の多項式であることを特徴とする拡大体演算装置。
5. 請求項１乃至４の何れかに記載の装置において、
   上記多項式ｆ（ｘ）はその最高次の項の係数で他の項の係数を割るとその値が±１となるものであることを特徴とする拡大体演算装置。
6. 有限体ＧＦ（ｑ）（ｑは素数又は素数の冪）上の既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大ＧＦ（ｑ^ｋ ）上の元Ａ及びＢの積Ｃ＝Ａ×Ｂを、ｆ（ｘ）＝０の解の一つαとするとき、ＧＦ（ｑ）上の元を要素に持つｋ次元ベクトル
   Ａ＝Σ_ｉ＝０ ^ｋ−１ ａ_ｉ α^ｉ 、Ｂ＝Σ_ｉ＝０ ^ｋ−１ ｂ_ｉ α^ｉ （０＜ｉ＜ｋ）
   を用いて演算する装置のコンピュータに、
   入力されたＡ及びＢを記憶手段に記憶する処理と、
   記憶手段から上記Ａ及びＢを取出して多項式乗算を行ってΣ_ｉ＝０ ^２ｋ−２ｄ_ｉ α^ｊ （０＜ｊ＜２ｋ−１）を求め、その係数ｄ_ｊ を記憶手段に記憶する処理と、
   上記ｄ_ｊを記憶手段から取出し、ＧＦ（ｑ）上の元を要素に持つｋ行ｋ列単位行列Ｉ及び上記ｋ次多項式ｆ（ｘ）により定まるＧＦ（ｑ）上の元を要素に持つｋ行ｋ−１列の行列Ｒについて、
   ［ｃ］＝［Ｉ Ｒ］［ｄ］
   を演算する還元処理と、
   上記演算結果Σ_ｉ＝０ ^ｋ−１ ｃ_ｉ をＣとして出力する処理と
   を実行させるプログラムを記録した記録媒体。
7. 請求項６記載の記録媒体において、
   上記行列Ｒは探索し得る既約多項式と対応する還元行列中の還元演算コストが最も少ないものであることを特徴とする記録媒体。
8. 請求項６記載の記録媒体において、
   上記還元処理において、ある行の部分的な演算結果を他の行の演算に流用することを少なくとも複数回縦続的に行う処理を含むことを特徴とする記録媒体。

Images