(57)【特許請求の範囲】
【請求項１】
ｑを素数または素数の冪とし、有限体ＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大ＧＦ（ｑk ）＝ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の元の演算実行中にＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元縦ベクトル［ｄ］をＧＦ（ｑ）上の元を要素に持つｋ次元縦ベクトル［ｃ］にｆ（ｘ）＝０を用いて還元を行う還元手段を備える演算装置であって、
上記還元手段は上記縦ベクトル［ｄ］を入力して、ＧＦ（ｑ）上の元を要素に持つｋ行ｋ列単位行列Ｉ及び上記ｋ次多項式ｆ（ｘ）により定まるＧＦ（ｑ）上の元を要素に持つｋ行ｋ−１列の行列Ｒについて、
［ｃ］＝［Ｉ｜Ｒ］［ｄ］
を演算して、その結果を上記縦ベクトル［ｃ］として出力するものであり、
上記行列Ｒは探索し得る既約多項式と対応する還元行列中の還元演算コストが最も少ないものであることを特徴とする拡大体演算装置。
【請求項２】
ｑを素数または素数の冪とし、有限体ＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大ＧＦ（ｑｋ  ）＝ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の元の演算実行中にＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元縦ベクトル［ｄ］をＧＦ（ｑ）上の元を要素に持つｋ次元縦ベクトル［ｃ］にｆ（ｘ）＝０を用いて還元を行う還元手段を備える演算装置であって、
上記還元手段は上記縦ベクトル［ｄ］を入力して、ＧＦ（ｑ）上の元を要素に持つｋ行ｋ列単位行列Ｉ及び上記ｋ次多項式ｆ（ｘ）により定まるＧＦ（ｑ）上の元を要素に持つｋ行ｋ−１列の行列Ｒについて、
［ｃ］＝［Ｉ｜Ｒ］［ｄ］                                  （Ｅ）
を演算して、その結果を上記縦ベクトル［ｃ］として出力するものであり、
一般のｋ行ｋ−１列の行列を基本変形により標準形
【数１】
0003565494.tif 000017
にする為に必要な基本変形の最小回数をＭ回とすると、上記行列ＲはＭ／２回以下の基本変形で標準形になるものであることを特徴とする拡大体演算装置。
【請求項３】
請求項２記載の装置において、
上記還元手段は上記式（Ｅ）の演算において、ある行の部分的な演算結果を他の行演算に流用する手段を備えることを特徴とする拡大体演算装置。
【請求項４】
請求項１乃至３の何れかに記載の装置において、
上記多項式ｆ（ｘ）は３項又は４項からなる３次又は４次以上の多項式であることを特徴とする拡大体演算装置。
【請求項５】
請求項１乃至４の何れかに記載の装置において、
上記多項式ｆ（ｘ）はその最高次の項の係数で他の項の係数を割るとその値が±１となるものであることを特徴とする拡大体演算装置。
【請求項６】
有限体ＧＦ（ｑ）（ｑは素数又は素数の冪）上の既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大ＧＦ（ｑｋ  ）上の元Ａ及びＢの積Ｃ＝Ａ×Ｂを、ｆ（ｘ）＝０の解の一つαとするとき、ＧＦ（ｑ）上の元を要素に持つｋ次元ベクトル
Ａ＝Σｉ＝０ ｋ−１  ａｉ  αｉ  、Ｂ＝Σｉ＝０ ｋ−１  ｂｉ  αｉ  （０＜ｉ＜ｋ）
を用いて演算する装置のコンピュータに、
入力されたＡ及びＢを記憶手段に記憶する処理と、
記憶手段から上記Ａ及びＢを取出して多項式乗算を行ってΣｉ＝０ ２ｋ−２ｄｉ  αｊ  （０＜ｊ＜２ｋ−１）を求め、その係数ｄｊ  を記憶手段に記憶する処理と、
上記ｄｊを記憶手段から取出し、ＧＦ（ｑ）上の元を要素に持つｋ行ｋ列単位行列Ｉ及び上記ｋ次多項式ｆ（ｘ）により定まるＧＦ（ｑ）上の元を要素に持つｋ行ｋ−１列の行列Ｒについて、
［ｃ］＝［Ｉ  Ｒ］［ｄ］
を演算する還元処理と、
上記演算結果Σｉ＝０ ｋ−１  ｃｉ  をＣとして出力する処理と
を実行させるプログラムを記録した記録媒体。
【請求項７】
請求項６記載の記録媒体において、
上記行列Ｒは探索し得る既約多項式と対応する還元行列中の還元演算コストが最も少ないものであることを特徴とする記録媒体。
【請求項８】
請求項６記載の記録媒体において、
上記還元処理において、ある行の部分的な演算結果を他の行の演算に流用することを少なくとも複数回縦続的に行う処理を含むことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、例えば楕円曲線暗号／署名などの情報セキュリティ技術を実現するために用いられ、有限体ＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大体ＧＦ（ｑｋ  ）＝ＧＦ（ｑ［ｘ］／ｆ（ｘ））装置に関する。
【０００２】
【従来の技術】
楕円曲線暗号を実現する際、楕円曲線の定義体として、有限体ＧＦ（ｑ）（但しｑは計算機の語長に近い素数または素数のべき（冪））のｋ次拡大体ＧＦ（ｑｋ  ）を用いる場合がある。拡大体ＧＦ（ｑｋ  ）上の演算を高速化できれば、拡大体ＧＦ（ｑｋ  ）上で定義された楕円曲線暗号の処理速度を高速化できる。今ＧＦ（ｑ）のｋ次拡大体ＧＦ（ｑｋ  ）上の元Ａ及びＢのＧＦ（ｑｋ  ）上の積Ｃ＝Ａ×Ｂの演算を実行する装置を構成したいとする。拡大に用いる既約多項式をＧＦ（ｑ）上のｆ（ｘ）とし、代数方程式ｆ（ｘ）＝０の解の一つをαとすると、一般にＧＦ（ｑｋ  ）上の元Ａは、ＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルａｉ  （但し０＜ｉ＜ｋ）を用いて、
Ａ＝Σｉ＝０ ｋ−１  ａｉ  αｉ  
と一意に書くことが出来る。ＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルａｉ  をＡの多項式基底による表現と呼ぶ。即ちＡ及びＢの多項式基底による表現ａｉ  及びｂｉ  （但し０＜ｉ＜ｋ）を入力とし、Ｃの多項式基底による表現ｃｉ  （但し０＜ｉ＜ｋ）を出力とする、演算装置を構成する場合、Ｃを計算する為には、まずＡ及びＢをαに関する多項式と見做し、Ｃ＝Ａ×Ｂを多項式演算で計算する。即ち
Σｊ＝０２ｋ−２ｄｊαｊ＝（Σｉ＝０ｋ−１ａｉαｉ）×（Σｉ＝０ｋ−１ｂｉαｉ）      （１）
なるｄｊ  （但し０＜ｊ＜２ｋ−１）を求める。この時ＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元ベクトルｄｊ  （但し０＜ｊ＜２ｋ−１）は、ＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルではないので、Ｃの多項式基底による表現とはなっていない。Ｃの多項式基底による表現を得る為には
Σｉ＝０ ｋ−１  ｃｉ  αｉ  ＝Σｊ＝０ ２ｋ−２ｄｊ  αｊ                      （２）
なるｃｉ  （但し０＜ｉ＜ｋ）を求めなくてはならない。この目的の為にはｆ（α）＝０が用いられる。ｆ（ｘ）がｘのｋ次多項式であるからｆ（α）＝Ｐ０  ＋Ｐ１  α＋Ｐ２  α２  ＋…＋Ｐｋ−１  αｋ−１  ＋Ｐｋ  αｋ  ＝０の関係から、
αｋ  ＝Σｊ＝０ ｋ−１  ｒｊ  αｊ                                    （３）
とすることができる。従って、式（３）を使ってｋ次以上のαの多項式をｋ−１次のαの多項式に変換することが出来る。この操作を還元と呼ぶ。もし拡大に用いる多項式ｆ（ｘ）がＧＦ（ｑ）上既約ｋ次２項多項式ｘｋ−ｒであれば、αｋ  ＝ｒであるので、整数ｍに対してαｍ＝ｒαｍ−ｋである。従って、ｋ−１箇のαｋ  以上の各項のｄｊ（ｊ＝ｋ〜２ｋ−２  ）をｒ倍して次数をｋ−１以下にすると共に、その下げた次数と対応する次数のｄｊ（ｊ＝０〜ｋ−１）と加算して各ｃｉ（ｉ＝０〜ｋ−１）を求めることができ、つまりｋ−１回のｒ倍と加算を用いて還元を実行することが出来る。２項多項式ｘｋ−ｒには上記のような性質があるので、従来、拡大体上の演算を高速に行う為には拡大に用いる多項式を２項多項式ｘｋ−ｒにすることが必要とされてきた（特願平１０−２５５５２６号参照）。
【０００３】
【発明が解決しようとする課題】
上記２項多項式による拡大体演算法では、ｑやｋの値によってはＧＦ（ｑ）上既約２項多項式ｆ（ｘ）＝ｘｋ  −ｒが存在しなかったり、ｒ倍が必ずしも高速に実行できない場合が数多く存在した。例えばｋ＝１３の場合２１２より大きい素数のうちの最初の２００個の中で、−１００＜ｒ＜１００なる既約２項多項式が存在する素数はわずか１２個に過ぎない。この発明は、どのような場合でも拡大体上演算を高速に実行することを可能とする拡大体演算装置を提供することを目的とする。
【０００４】
【課題を解決するための手段】
以下にこの発明の原理を説明する。簡単のためαのｍ次多項式をｆ（α）＝０を用いてｍ−１次多項式に変換することを考える（但しｋ＜ｍ＜２ｋ）。αのｍ次多項式を
Σｉ＝０２ｋ−１ｄｉαｉ＝Σｉ＝０ｋ−１ｄｉαｉ＋Σｉ＝０ｋ−１ｄｉ＋ｋ（αｉ・αｋ）                （４）
とすることができる。ｍ次多項式をｍ−１次多項式にする為には、αのすべてのｋ次以上の冪をｆ（α）＝０の関係から次数を１次下げれば良い。即ち式（３）を使って式（４）を
0003565494.tif 000002
と変形すれば良い。式（５）の左辺がαのｍ次式（ｋ＜ｍ＜２ｋ）なら式（５）の右辺はαのｍ−１次式である。式（５）の右辺をαの多項式と見做しαｉ  の係数をｄ′ｉ  とおくと式（５）は、
Σｉ＝０ ２ｋ−１ｄｉ  αｉ  ＝Σｉ＝０ ２ｋ−１ｄ′ｉ  αｉ                  （６）
とかける。但しｉ＞ｍの場合ｄ′ｉ  ＝０である。ＧＦ（ｑ）上の元を要素に持つ２ｋ次元ベクトルｄｉ  を縦ベクトルで
【０００５】
【数２】
0003565494.tif 000003
と表現するなら、この過程は以下のように行列を用いて
【０００６】
【数３】
0003565494.tif 000004
【０００７】
と表現することが出来る（空白は０と見做す、以下も同様）。右辺の２ｋ行２ｋ列の行列内の縦線と横線は便宜上付けたものであり、この縦線、横線で分けられた左上の小行列（単位行列）は式（５）の右辺第１項と対応し、右の上下の小行列は右第２項と対応する。説明の便宜の為、区切られた小行列に名前を付け式（７）を次式
【０００８】
【数４】
0003565494.tif 000005
と表現することにする。Ｉはｋ行ｋ列の単位行列であり、Ｏはｋ行ｋ列の零行列である。また、
【０００９】
【数５】
0003565494.tif 000006
【００１０】
とする。式（８）で行列を縦ベクトルに１回かけることはｆ（α）＝０の関係を使ってαのｍ次式をｍ−１次式に変換することに相当している。従ってαの２ｋ−１次式をｋ−１次式に変換することは式（８）の行列を縦ベクトルにｋ回かけることに他ならない。即ち還元とは
【００１１】
【数６】
0003565494.tif 000007
に他ならない（但しｉ＞ｋの時ｃｉ  ＝０）。
【００１２】
【数７】
0003565494.tif 000008
を２乗、３乗と順次計算し、ｋ乗まで行うと、
【００１３】
【数８】
0003565494.tif 000009
【００１４】
となる。所で
Ｒ１ｋ−Ｉ＝（Ｒ１  −Ｉ）（Ｒ１ｋ−１＋Ｒ１ｋ−２＋…＋Ｒ１  ＋Ｉ）
であり、Ｒ１  は式（１０）の行列であるから、これをｋ乗すると０となる。よって
−Ｉ＝（Ｒ１  −Ｉ）（Ｒ１ｋ−１＋Ｒ１ｋ−２＋…＋Ｒ１  ＋Ｉ）
両辺に（Ｒ１  −Ｉ）−１を乗算すると、
−（Ｒ１  −Ｉ）−１＝Ｒ１ｋ−１＋Ｒ１ｋ−２＋…＋Ｒ１  ＋Ｒ０  
（Ｉ−Ｒ１  ）−１＝Σｉ＝０ ｋ−１  Ｒ１ｉ
この関係を式（１１）に代入し、またＲ１ｋ＝０であるから
【００１５】
【数９】
0003565494.tif 000010
となる。Ｒ′＝Ｒ０  （Ｉ−Ｒ１  ）−１とおけば式（１０）は
【００１６】
【数１０】
0003565494.tif 000011
【００１７】
とかける。二つのｋ−１次多項式の積は２ｋ−２次多項式であるので、ＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大ＧＦ（ｑｋ  ）＝ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の２つの元の乗算を考える上ではｄ２ｋ−１＝０である。従ってＲ′のなかで実際に必要な列は第０列から第ｋ−２列までである。行列Ｒ′の第０列から第ｋ−２列までのｋ行（ｋ−１）列の行列Ｒを還元行列と呼び、式（１３）はＲを用い簡単に
【００１８】
【数１１】
0003565494.tif 000012
【００１９】
と表わせる。式（１４）よりＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の２つの元の乗算が高速に計算できるかどうかは還元行列Ｒの性質に依存することが判る。一般の拡大体ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上の２つの元の乗算における還元には式（７）、（８）、（１４）からｋ（ｋ−１）回のＧＦ（ｑ）上定数倍とｋ（ｋ−１）回のＧＦ（ｑ）上加算の演算が必要である。一方、従来高速とされてきた既約２項多項式による拡大体ＧＦ（ｑ）［ｘ］／（ｘk −ｒ）の場合Ｒ′＝ｒＩになるので還元には（ｋ−１）回のＧＦ（ｑ）上定数倍（ｒ倍）と（ｋ−１）回のＧＦ（ｑ）上加算の演算しか必要ない。ところで、２項式ｘk −ｒが既約かそうでないかは定義体ｑと拡大次数ｋの値によって決まる。例えばｑ＝６５５３９、ｋ＝１０の場合、既約２項式は存在しない。そのような場合は従来効率的な乗算装置は構成できないと考えられていた。あるいはｑ＝４２０１，ｋ＝１０の場合、既約２項式ｘk −ｒはｒ＝±１１、±１３、±１９、…であるが、加算のみでこれらｒ倍を実現するには少なくとも５回の加算が必要であり、必ずしもｒ倍が高速であるとは云えない。しかし、このような場合でも以下の手順に従えば効率的な乗算装置を構成できる。
【００２０】
Ｓｔｅｐ１：探索し得る全ての既約多項式に対応する還元行列Ｒを上記手順に従い計算する。
Ｓｔｅｐ２：Ｒによる還元演算の演算コストに関する性質を調べる。
Ｓｔｅｐ３：探索し得る全ての既約多項式の中で最も演算コストの少ない既約多項式ｆ（ｘ）を見つけ出す。
Ｓｔｅｐ４：ｆ（ｘ）における還元演算装置の構成を行い、乗算装置を構成する。
【００２１】
上記手順の、探索し得る既約多項式に、既約２項多項式を含めても手順は全く変わらない。従ってこのようにすれば、既約２項多項式をも含めた、探索し得る全ての既約多項式に関して、最も効率的な乗算装置を構成できる。
つまりこの発明では前述のように決めた既約多項式が用いられ還元演算の演算コストが少ないものであり、つまり還元演算手段に用いられる還元行列Ｒはその行列の要素数中の半分以上が零要素であり、還元演算において行列Ｒの零要素の部分のＧＦ（ｑ）上積和演算が省略され、還元演算を高速に行うことができる。
あるいは、一般のｋ行ｋ−１列の行列を基本変形により標準形
【００２２】
【数１２】
0003565494.tif 000013
【００２３】
にするために必要な基本変形の最小回数をＭ回とすると還元行列ＲはＭ／２回以下の基本変形で標準形になるようなものであり、行列Ｒはこのような性質があるため、還元演算におけるある行の部分的な演算結果を他の行の演算に流用するように還元演算手段が多く構成され、それだけ還元を高速に行うことができる。
このような構成とすることにより、既約多項式としては３項よりなる３次以上のもの、あるいは４項よりなる４次以上のものが用いられる。
一般に式（１２）の行列Ｖは
【００２４】
【数１３】
0003565494.tif 000014
【００２５】
のように分解できる。これは、還元を行う場合に次数の高い項から順にｆ（α）＝０の関係を使って一次ずつ次数を下げてゆくことに対応する。従って、２項多項式でなくとも項数が少なく、ｒｉ  倍が高速なら還元を高速に行うことができる。また、項数が多くとも、行列Ｖを何らかの分解によって要素の絶対値が小さい少数の疎行列の積に分解できれば同様に還元を高速に行うことができる。このような分解が出来ると云うことは、式（１４）の計算に於いて、ある行の計算過程に於ける部分的な結果を他の行の計算に流用できることに相当している。例えばｑ＝６５５３９、ｋ＝１０の場合はｆ（ｘ）＝ｘ１０−ｘ９  −１あるいはｆ（ｘ）＝ｘ１０−ｘ−１、ｑ＝４２０１、ｋ＝１０の場合はｆ（ｘ）＝ｘ１０＋ｘ９  ＋１あるいはｆ（ｘ）＝ｘ１０＋ｘ＋１等は２項式ではないが還元を高速に行うことができる。
【００２６】
【発明の実施の形態】
以下にこの発明の実施例を示す。
図１はこの発明を拡大体ＧＦ（ｑｋ  ）の乗算装置に適用した場合である。この乗算装置１ＡはＧＦ（ｑｋ  ）上の元Ａ及びＢを入力し、その積Ｃ＝Ａ×Ｂを出力するものであり、ＧＦ（ｑｋ  ）上の元Ａ、Ｂ、Ｃは、それぞれＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルａｉ  ，ｂｉ  ，ｃｉ  （但し０＜ｉ＜ｋ）で表されており、ＧＦ（ｑ）上ｋ次既約多項式ｆ（ｘ）＝０の一つの解をαとすると、それぞれ
Ａ＝Σｉ＝０ ｋ−１  ａｉ  αｉ  ，Ｂ＝Σｉ＝０ ｋ−１  ｂｉ  αｉ  ，Ｃ＝Σｉ＝０ ｋ−１  ｃｉ  αｉ  
を意味している。この実施例では簡単のため、ｋ＝１０の場合を説明するが、一般にｆ（ｘ）の項数をｍとするとｍ−１以上のｋでもこの発明の効果を享受出来る。装置１Ａは多項式乗算装置１Ｂと還元装置１Ｃとからなる。
【００２７】
多項式乗算装置１ＢはＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルａｉ  ，ｂｉ  （但し０＜ｉ＜ｋ）を入力とし、ｘのＧＦ（ｑ）上係数多項式
Σｊ＝０２ｋ−２ｄｊｘｊ＝（Σｉ＝０ｋ−１ａｉｘｉ）（Σｉ＝０ｋ−１ｂｉｘｉ）    （１６）
の係数ｄｊ  （但し０＜ｊ＜２ｋ−１）を演算して出力する。
還元装置１Ｃは係数ｄｉ  が入力され、式（１４）が演算され、ｆ（α）＝０を満たすαについて
Σｉ＝０ ｋ−１  ｃｉ  αｉ  ＝Σｊ＝０ ２ｋ−２ｄｊ  αｊ                      （１７）
なる係数ｃｉ  （但し０＜ｉ＜ｋ）を出力する。
【００２８】
還元装置１Ｃは例えば図２に示すように構成される。この例は還元行列Ｒはその構成要素の半分以上が零要素の場合で具体的にｋ＝１０、ｆ（ｘ）＝ｘ１０−ｘ−１が用いられその還元行列は式（９）、式（１２）から次式となる。
【００２９】
【数１４】
0003565494.tif 000015
【００３０】
つまり行列Ｒはその要素数１０×９＝９０のうち零要素の数が７２、つまり８０％もある。この還元行列Ｒを用いた式（１４）の演算は図２に示すように構成することができる。図２中の（＋）はＧＦ（ｑ）上加算を表わす。この場合は単位行列Ｉも還元行列Ｒも１の要素と零の要素とよりなり、ｄ0 〜ｄ9 が単位行列Ｉとの演算であり、ｄ10〜ｄ18が還元行列Ｒとの演算であり、各行ごとに単位行列Ｉ、還元行列Ｒ中の１の要素との演算がなされるｄ0 〜ｄ18が加算される。例えば第２行目では単位行列Ｉとの演算はｄ1 であり、還元行列Ｒとの演算はｄ10とｄ11であり、これらｄ1 とｄ10とｄ11が加算されてｃ1 となる。
【００３１】
このように還元装置１Ｃが構成されているため、この装置１Ｃでは還元を行う為のコストは加算１８回である。一般にｋ次式ｆ（ｘ）＝ｘｋ  −ｘ−１が既約の場合還元を行う為のコストは加算２（ｋ−１）回であり、２項式の定数倍（ｒ倍）が加算１回より高速に行えない場合この実施例の方が高速になる。
還元装置１Ｃの他の構成例を図３に示す。この場合は先に述べたように一般のｋ行ｋ−１列の行列を基本変形により標準形にするために必要な基本変形の回数がＭ回の場合に、還元行列ＲがＭ／２回以下の基本変形で標準形となる還元行列Ｒが用いられた場合で、この実施例では還元行列Ｒはｋ＝１０，ｆ（ｘ）＝ｘ１０−ｘ９  −１が用いられ、次式で与えられる。
【００３２】
【数１５】
0003565494.tif 000016
【００３３】
なおこの行列Ｒは、例えば第９行の各要素で他の全ての行の対応する要素をそれぞれ引算し、その結果の行列について第８行の各要素で他の全ての行の対応する要素をそれぞれ引算し、その結果の行列について第７行の各要素で他の全ての行の対応する要素をそれぞれ引算し、以下同様のことを行えば９回という少ない回数の基本変形で標準形にすることができるものである。
このような還元行列では、図３に示すように例えばｃ７  を求めるための演算ｄ１７（＋）ｄ１８（＋）ｄ７  中のｄ１７（＋）ｄ１８の演算結果はｃ６を求めるための演算ｄ１６（＋）ｄ１７（＋）ｄ１８（＋）ｄ６  中のｄ１７（＋）ｄ１８の演算に流用され、またｃ５  を求めるための演算ｄ１５（＋）ｄ１６（＋）ｄ１７（＋）ｄ１８（＋）ｄ５  中のｄ１６（＋）ｄ１７（＋）ｄ１８の演算はｃ６  を求めるための演算中のｄ１６（＋）ｄ１７（＋）ｄ１８の演算結果が流用され、以下同様に、ある行の部分的な演算結果が他の行の演算に流用され、特に図３の例ではその流用演算手段が順次縦続的に行われているため、ここに演算する場合と比較して、全体としての演算回数が少なくなる。この還元装置１Ｃでは還元を行う為のコストは加算１８回である。一般にｋ次式ｆ（ｘ）＝ｘｋ  −ｘｋ−１  −１が既約の場合還元を行う為のコストは加算２（ｋ−１）回であり、２項式の定数倍（ｒ倍）が加算１回より高速に行えない場合この実施例の方が高速になる。
【００３４】
この発明の拡大体乗算をコンピュータにプログラムを実行させて行うこともできる。図４にその構成を示す。入出力インターフェース１１、記憶部１２、ＣＰＵ（中央演算装置）１３、コンピュータを動作させる基本プログラムが記憶されたプログラムメモリ１４、各種応用プログラムが記憶されたハードディスク１５、ＲＡＭ１６などがバス１７に接続されている。ハードディスク１５からこの拡大体乗算を行うためのプログラムがＲＡＭ１６に転送し、そのプログラムを実行することにより、入出力インターフェース１１からＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルで表されるＧＦ（ｑｋ  ）上の元Ａ、Ｂが入力されると、これらを取込み記憶部１２に格納する（Ｓ１）（図５参照）。
【００３５】
その後、記憶部１２から元Ａ、Ｂを取出して、ＣＰＵ１３は多項式演算処理１８を実行して、つまりａｉ  及びｂｉ  （０＜ｉ＜ｋ）から式（１６）を満たす係数ｄｊ  （０＜ｊ＜２ｋ−１）を求め、これら係数ｄｊを記憶部１２に格納する（Ｓ２）。
次に記憶部１２からｄｊ  を取出し、還元演算処理１９を実行して、式（１４）を演算することにより式（１７）を満たす係数ｃｉ  を求め（Ｓ３）、この結果であるＧＦ（ｑ）上の元ｃｉ  のベクトルからなるＧＦ（ｑｋ  ）上の元Ｃを出力インターフェース１１から外部へ出力する（Ｓ４）。
【００３６】
図２に示した還元装置１Ｃの演算をコンピュータにより、つまり、図５中の還元演算処理を行わせるには、例えば図６に示す手順で行えばよい。ｄ０  とｄ１０を記憶部１２から取出し、これらを加算してｃ０  として記憶部１２に格納し（Ｓ１）、
記憶部１２からｄ１  ，ｄ１０，ｄ１１を取出してこれらを加算してｃ１  として記憶部１２に格納し（Ｓ２）、
記憶部１２からｄ２  ，ｄ１１，ｄ１２を取出してこれらを加算してｃ２  として記憶部１２に格納し（Ｓ３）、
記憶部１２からｄ３  ，ｄ１２，ｄ１３を取出し、これらを加算してｃ３  として記憶部１２に格納し（Ｓ４）、
記憶部１２からｄ４  ，ｄ１３，ｄ１４を取出してこれらを加算してｃ４  として記憶部１２に格納し（Ｓ５）、
記憶部１２からｄ５  ，ｄ１４，ｄ１５を取出して、これらを加算してｃ５  として記憶部１２に格納し（Ｓ６）、
記憶部１２からｄ６  ，ｄ１５，ｄ１６を取出し、これらを加算してｃ６  として記憶部１２に格納し（Ｓ７）、
記憶部１２からｄ７  ，ｄ１６，ｄ１７を取出し、これらを加算してｃ７  として記憶部１２に格納し（Ｓ８）、
記憶部１２からｄ８  ，ｄ１７，ｄ１８を取出し、これらを加算してｃ８  として記憶部１２に格納し（Ｓ９）、
記憶部１２からｄ９  ，ｄ１８を取出し、これらを加算してｃ９として記憶部１２に格納する（Ｓ１０）。
【００３７】
なおこれらのステップＳ１〜Ｓ１０の順番は任意でよい。
図３に示した還元装置をコンピュータにより還元演算処理をさせるには例えば図７に示すようにすればよい。
まず記憶部１２からｄ１８を取出し、これをｔとしてＣＰＵ１３内のレジスタに一時格納し（Ｓ１）、
記憶部１２からｄ８  とｄ１７を取出し、そのｄ１７とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ８  を加算してｃ８  として記憶部１２に記憶し（Ｓ２）、
記憶部１２からｄ７  とｄ１６を取出し、ｄ１６とｔを加算し、その結果でレジスタ内のｔを更新すると共に、そのｔとｄ７  を加算してｃ７  として記憶部１２に格納し（Ｓ３）、
記憶部１２からｄ６  ，ｄ１５を取出し、ｄ１５とｔを加算し、その結果でレジスタ内のｔを更新すると共にｄ６  とｔを加算してｃ６  として記憶部１２に格納し（Ｓ４）、
記憶部１２からｄ５  ，ｄ１４を取出し、ｄ１４とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ５  を加算してｃ５  として記憶部１２に格納し（Ｓ５）、
記憶部１２からｄ４  ，ｄ１３を取出し、ｄ１３とｔを加算し、その結果でレジスタ内のｔを更新すると共に、そのｔとｄ４  を加算してｃ４  として記憶部１２に格納し（Ｓ６）、
記憶部１２からｄ３  ，ｄ１２を取出し、ｄ１２とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ３  を加算してｃ３  として記憶部１２に格納し（Ｓ７）、
記憶部１２からｄ２  ，ｄ１１を取出し、ｄ１１とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ２  を加算してｃ２  として記憶部１２に格納し（Ｓ８）、
記憶部１２からｄ１  ，ｄ１０を取出し、ｄ１０とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ１  を加算してｃ１  として記憶部１２に格納し（Ｓ９）、
記憶部１２からｄ０  ，ｄ９  を取出し、ｄ９  とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ０  を加算してｃ０  として記憶部１２に格納する（Ｓ１０）。
【００３８】
ｋ次拡大に用いるｋ次多項式ｆ（ｘ）としてはその最高次数の係数で各項の係数を割算した時に、つまりモニックした時に、各項の係数が±１になるものが好ましい。このようにすると、還元行列Ｒの構成要素が零要素と１要素とで構成され、定数倍演算をしなくてすみ、高速演算が可能となる。
図４において、駆動部２１を介して外部ディスク装置２２を駆動し、外部ディスク装置２２に記録されたプログラムを実行して前記処理を行うようにしてもよい。また上述ではこの発明を乗算装置に適用したが、一般にＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大体ＧＦ（ｑｋ  ）上の演算において、演算実行中にＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元縦ベクトルｄをＧＦ（ｑ）上の元を要素に持つｋ次元縦ベクトルｃに、ｆ（ｘ）＝０の関係を用いて還元を行う拡大体演算装置に適用できる。
【００３９】
【発明の効果】
従来ＧＦ（ｑ）上既約２項式が存在しない場合ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上乗算において還元にｋ（ｋ−１）回のＧＦ（ｑ）上定数倍とｋ（ｋ−１）回のＧＦ（ｑ）上加算の演算が必要と考えられていたが、この発明によれば、最も効率の良い時２（ｋ−１）回のＧＦ（ｑ）上加算で還元を実行できる。上記ＧＦ（ｑ）上定倍数はＧＦ（ｑ）上加算より十分大きなコストがかかるが、ＧＦ（ｑ）上定数倍をＧＦ（ｑ）上加算の５倍と見積もっても、ｋ＝１０の場合で還元が３０倍高速化できる。ＧＦ（ｑ）上既約２項式ｘｋ  −ｒが存在しても、ｒ倍が必ずしも高速に実行できない場合ｒ倍をＧＦ（ｑ）上加算の５倍と見積もると、最も効率の良い場合、この発明により、還元が３倍高速化できる。
【図面の簡単な説明】
【図１】ＧＦ（ｑｋ  ）乗算装置の構成を示す図。
【図２】図１中の還元装置１Ｃの具体例を示す図。
【図３】図１中の還元装置１Ｃの他の具体例を示す図。
【図４】この発明装置をコンピュータにより実現する例を示すブロック図。
【図５】ＧＦ（ｑｋ  ）乗算の処理の流れを示す図。
【図６】還元演算処理の流れを示す図。
【図７】還元演算処理の他の例の流れを示す図。
【図１】
0003565494.tif 000018
【図２】
0003565494.tif 000019
【図３】
0003565494.tif 000020
【図４】
0003565494.tif 000021
【図５】
0003565494.tif 000022
【図６】
0003565494.tif 000023
【図７】
0003565494.tif 000024