JP3565494B2 - Enlarged field arithmetic device and program recording medium therefor - Google Patents

Description

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【００３３】
なおこの行列Ｒは、例えば第９行の各要素で他の全ての行の対応する要素をそれぞれ引算し、その結果の行列について第８行の各要素で他の全ての行の対応する要素をそれぞれ引算し、その結果の行列について第７行の各要素で他の全ての行の対応する要素をそれぞれ引算し、以下同様のことを行えば９回という少ない回数の基本変形で標準形にすることができるものである。
このような還元行列では、図３に示すように例えばｃ_７ を求めるための演算ｄ_１７（＋）ｄ_１８（＋）ｄ_７ 中のｄ_１７（＋）ｄ_１８の演算結果はｃ_６を求めるための演算ｄ_１６（＋）ｄ_１７（＋）ｄ_１８（＋）ｄ_６ 中のｄ_１７（＋）ｄ_１８の演算に流用され、またｃ_５ を求めるための演算ｄ_１５（＋）ｄ_１６（＋）ｄ_１７（＋）ｄ_１８（＋）ｄ_５ 中のｄ_１６（＋）ｄ_１７（＋）ｄ_１８の演算はｃ_６ を求めるための演算中のｄ_１６（＋）ｄ_１７（＋）ｄ_１８の演算結果が流用され、以下同様に、ある行の部分的な演算結果が他の行の演算に流用され、特に図３の例ではその流用演算手段が順次縦続的に行われているため、ここに演算する場合と比較して、全体としての演算回数が少なくなる。この還元装置１Ｃでは還元を行う為のコストは加算１８回である。一般にｋ次式ｆ（ｘ）＝ｘ^ｋ −ｘ^ｋ−１ −１が既約の場合還元を行う為のコストは加算２（ｋ−１）回であり、２項式の定数倍（ｒ倍）が加算１回より高速に行えない場合この実施例の方が高速になる。
【００３４】
この発明の拡大体乗算をコンピュータにプログラムを実行させて行うこともできる。図４にその構成を示す。入出力インターフェース１１、記憶部１２、ＣＰＵ（中央演算装置）１３、コンピュータを動作させる基本プログラムが記憶されたプログラムメモリ１４、各種応用プログラムが記憶されたハードディスク１５、ＲＡＭ１６などがバス１７に接続されている。ハードディスク１５からこの拡大体乗算を行うためのプログラムがＲＡＭ１６に転送し、そのプログラムを実行することにより、入出力インターフェース１１からＧＦ（ｑ）上の元を要素に持つｋ次元ベクトルで表されるＧＦ（ｑ^ｋ ）上の元Ａ、Ｂが入力されると、これらを取込み記憶部１２に格納する（Ｓ１）（図５参照）。
【００３５】
その後、記憶部１２から元Ａ、Ｂを取出して、ＣＰＵ１３は多項式演算処理１８を実行して、つまりａ_ｉ 及びｂ_ｉ （０＜ｉ＜ｋ）から式（１６）を満たす係数ｄ_ｊ （０＜ｊ＜２ｋ−１）を求め、これら係数ｄ_ｊを記憶部１２に格納する（Ｓ２）。
次に記憶部１２からｄ_ｊ を取出し、還元演算処理１９を実行して、式（１４）を演算することにより式（１７）を満たす係数ｃ_ｉ を求め（Ｓ３）、この結果であるＧＦ（ｑ）上の元ｃ_ｉ のベクトルからなるＧＦ（ｑ^ｋ ）上の元Ｃを出力インターフェース１１から外部へ出力する（Ｓ４）。
【００３６】
図２に示した還元装置１Ｃの演算をコンピュータにより、つまり、図５中の還元演算処理を行わせるには、例えば図６に示す手順で行えばよい。ｄ_０ とｄ_１０を記憶部１２から取出し、これらを加算してｃ_０ として記憶部１２に格納し（Ｓ１）、
記憶部１２からｄ_１ ，ｄ_１０，ｄ_１１を取出してこれらを加算してｃ_１ として記憶部１２に格納し（Ｓ２）、
記憶部１２からｄ_２ ，ｄ_１１，ｄ_１２を取出してこれらを加算してｃ_２ として記憶部１２に格納し（Ｓ３）、
記憶部１２からｄ_３ ，ｄ_１２，ｄ_１３を取出し、これらを加算してｃ_３ として記憶部１２に格納し（Ｓ４）、
記憶部１２からｄ_４ ，ｄ_１３，ｄ_１４を取出してこれらを加算してｃ_４ として記憶部１２に格納し（Ｓ５）、
記憶部１２からｄ_５ ，ｄ_１４，ｄ_１５を取出して、これらを加算してｃ_５ として記憶部１２に格納し（Ｓ６）、
記憶部１２からｄ_６ ，ｄ_１５，ｄ_１６を取出し、これらを加算してｃ_６ として記憶部１２に格納し（Ｓ７）、
記憶部１２からｄ_７ ，ｄ_１６，ｄ_１７を取出し、これらを加算してｃ_７ として記憶部１２に格納し（Ｓ８）、
記憶部１２からｄ_８ ，ｄ_１７，ｄ_１８を取出し、これらを加算してｃ_８ として記憶部１２に格納し（Ｓ９）、
記憶部１２からｄ_９ ，ｄ_１８を取出し、これらを加算してｃ_９として記憶部１２に格納する（Ｓ１０）。
【００３７】
なおこれらのステップＳ１〜Ｓ１０の順番は任意でよい。
図３に示した還元装置をコンピュータにより還元演算処理をさせるには例えば図７に示すようにすればよい。
まず記憶部１２からｄ_１８を取出し、これをｔとしてＣＰＵ１３内のレジスタに一時格納し（Ｓ１）、
記憶部１２からｄ_８ とｄ_１７を取出し、そのｄ_１７とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_８ を加算してｃ_８ として記憶部１２に記憶し（Ｓ２）、
記憶部１２からｄ_７ とｄ_１６を取出し、ｄ_１６とｔを加算し、その結果でレジスタ内のｔを更新すると共に、そのｔとｄ_７ を加算してｃ_７ として記憶部１２に格納し（Ｓ３）、
記憶部１２からｄ_６ ，ｄ_１５を取出し、ｄ_１５とｔを加算し、その結果でレジスタ内のｔを更新すると共にｄ_６ とｔを加算してｃ_６ として記憶部１２に格納し（Ｓ４）、
記憶部１２からｄ_５ ，ｄ_１４を取出し、ｄ_１４とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_５ を加算してｃ_５ として記憶部１２に格納し（Ｓ５）、
記憶部１２からｄ_４ ，ｄ_１３を取出し、ｄ_１３とｔを加算し、その結果でレジスタ内のｔを更新すると共に、そのｔとｄ_４ を加算してｃ_４ として記憶部１２に格納し（Ｓ６）、
記憶部１２からｄ_３ ，ｄ_１２を取出し、ｄ_１２とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_３ を加算してｃ_３ として記憶部１２に格納し（Ｓ７）、
記憶部１２からｄ_２ ，ｄ_１１を取出し、ｄ_１１とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_２ を加算してｃ_２ として記憶部１２に格納し（Ｓ８）、
記憶部１２からｄ_１ ，ｄ_１０を取出し、ｄ_１０とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_１ を加算してｃ_１ として記憶部１２に格納し（Ｓ９）、
記憶部１２からｄ_０ ，ｄ_９ を取出し、ｄ_９ とｔを加算し、その結果でレジスタ内のｔを更新すると共にそのｔとｄ_０ を加算してｃ_０ として記憶部１２に格納する（Ｓ１０）。
【００３８】
ｋ次拡大に用いるｋ次多項式ｆ（ｘ）としてはその最高次数の係数で各項の係数を割算した時に、つまりモニックした時に、各項の係数が±１になるものが好ましい。このようにすると、還元行列Ｒの構成要素が零要素と１要素とで構成され、定数倍演算をしなくてすみ、高速演算が可能となる。
図４において、駆動部２１を介して外部ディスク装置２２を駆動し、外部ディスク装置２２に記録されたプログラムを実行して前記処理を行うようにしてもよい。また上述ではこの発明を乗算装置に適用したが、一般にＧＦ（ｑ）上既約なｋ次多項式ｆ（ｘ）によるＧＦ（ｑ）のｋ次拡大体ＧＦ（ｑ^ｋ ）上の演算において、演算実行中にＧＦ（ｑ）上の元を要素に持つ２ｋ−１次元縦ベクトルｄをＧＦ（ｑ）上の元を要素に持つｋ次元縦ベクトルｃに、ｆ（ｘ）＝０の関係を用いて還元を行う拡大体演算装置に適用できる。
【００３９】
【発明の効果】
従来ＧＦ（ｑ）上既約２項式が存在しない場合ＧＦ（ｑ）［ｘ］／（ｆ（ｘ））上乗算において還元にｋ（ｋ−１）回のＧＦ（ｑ）上定数倍とｋ（ｋ−１）回のＧＦ（ｑ）上加算の演算が必要と考えられていたが、この発明によれば、最も効率の良い時２（ｋ−１）回のＧＦ（ｑ）上加算で還元を実行できる。上記ＧＦ（ｑ）上定倍数はＧＦ（ｑ）上加算より十分大きなコストがかかるが、ＧＦ（ｑ）上定数倍をＧＦ（ｑ）上加算の５倍と見積もっても、ｋ＝１０の場合で還元が３０倍高速化できる。ＧＦ（ｑ）上既約２項式ｘ^ｋ −ｒが存在しても、ｒ倍が必ずしも高速に実行できない場合ｒ倍をＧＦ（ｑ）上加算の５倍と見積もると、最も効率の良い場合、この発明により、還元が３倍高速化できる。
【図面の簡単な説明】
【図１】ＧＦ（ｑ^ｋ ）乗算装置の構成を示す図。
【図２】図１中の還元装置１Ｃの具体例を示す図。
【図３】図１中の還元装置１Ｃの他の具体例を示す図。
【図４】この発明装置をコンピュータにより実現する例を示すブロック図。
【図５】ＧＦ（ｑ^ｋ ）乗算の処理の流れを示す図。
【図６】還元演算処理の流れを示す図。
【図７】還元演算処理の他の例の流れを示す図。[0001]
TECHNICAL FIELD OF THE INVENTION
INDUSTRIAL APPLICABILITY The present invention is used for realizing information security technology such as elliptic curve cryptography / signature and the like. GF (q ^k ) = GF (q [x] / f (x)) device.
[0002]
[Prior art]
When implementing the elliptic curve cryptography, the elliptic curve is defined as a k-th order extension field GF (q ^k ) of a finite field GF (q) (where q is a prime number close to the word length of a computer or a power of a prime number). May be used. If faster operation on an extension field GF (q ^k), can speed up the processing speed of the defined elliptic curve cryptography over an extension field GF (q ^k). Suppose now that it is desired to configure an apparatus that executes an operation of a product C = A × B on a GF (q ^k ) of elements A and B on a ^k-th extension field GF (q ^k ) of GF (q). If the irreducible polynomial used for the expansion is f (x) on GF (q) and one of the solutions of the algebraic equation f (x) = 0 is α, the element A on GF (q ^k ) is generally GF (Q) Using a k-dimensional vector a _i (where 0 < i <k) having the above element as an element,
A = Σ _{i = 0} ^k−1 a _i α ⁱ
Can be written uniquely. A k-dimensional vector a _i having an element on GF (q) as an element is referred to as a representation of A by a polynomial basis. That is, an arithmetic device that receives the expressions a _i and b _i (where 0 < i <k) based on polynomial bases of A and B as inputs and outputs the expressions c _i (where 0 < i <k) based on polynomial bases of C In this case, in order to calculate C, first, A and B are regarded as polynomials related to α, and C = A × B is calculated by a polynomial operation. That is, Σ _{j = 0} ^2k−2 _dj α ^j = (Σ _{i = 0} ^k−1 _ai α ⁱ ) × (Σ _{i = 0} ^k−1 b _i α ⁱ ) (1)
_Dj (where 0 < j <2k-1) is obtained. At this time GF (q) 2k-1 dimensional with the original element vector _{d j} (where 0 <j <2k-1) is not a k-dimensional vector with the original on GF (q) to the element, C is not represented by a polynomial basis. In order to obtain a representation by C polynomial basis, Σ _{i = 0} ^k−1 c _i α ⁱ = Σ _{j = 0} ^2k−2 d _j α ^j (2)
C _i (where 0 < i <k) must be obtained. For this purpose, f (α) = 0 is used. Since f (x) is a k-th order polynomial of x, f (α) = P ₀ + P ₁ α + P ₂ α ² +... + P _k−1 α ^k−1 + P _k α ^k = 0
α ^k = Σ _{j = 0} ^k−1 r _j α ^j (3)
It can be. Therefore, a polynomial of α of order k or more can be converted into a polynomial of α of degree k−1 using equation (3). This operation is called reduction. If the polynomial f (x) used for enlargement is an irreducible k-th order binomial polynomial x ^k −r on GF (q), α ^k = r, and therefore α ^m = rα ^m−k for the integer m It is. Therefore, _dj (j = k〜2k−2) of each term of k−1 or more α ^k or more is multiplied by r to reduce the order to k−1 or less, and the reduced order and the corresponding order d _{j (j} = _0~k-1) and the addition to the _{c i (i = 0~k-1} ) can be obtained, that is to perform reduction with r times the sum of the k-1 times Can be done. Since the binomial polynomial x ^k -r has the above-described properties, conventionally, it is necessary to use a binomial polynomial x ^k -r for the polynomial used for enlargement in order to perform the operation on the enlargement field at high speed. (See Japanese Patent Application No. 10-255526).
[0003]
[Problems to be solved by the invention]
In the extended field operation method using the binomial polynomial, the irreducible binomial polynomial f (x) = x ^k −r does not exist on GF (q) depending on the value of q or k, or r times is not always executed at high speed. There were many cases where it was not possible. For example, in the case of k = 13, among the first 200 prime numbers larger than 2 ^12, only 12 prime numbers have an irreducible binomial polynomial satisfying −100 < r < 100. SUMMARY OF THE INVENTION An object of the present invention is to provide an extended field arithmetic device capable of executing a calculation on an extended field at high speed in any case.
[0004]
[Means for Solving the Problems]
The principle of the present invention will be described below. For the sake of simplicity, consider converting an m-th order polynomial of α into an m-1 order polynomial using f (α) = 0 (where k < m <2k). the m-th order polynomial of ^{_{α Σ i = 0 2k-1}} d i α i = Σ i = 0 k-1 d i α i + Σ i = 0 k-1 d i + k (α i · α k) (4)
It can be. In order to convert the m-th order polynomial into the (m-1) -th order polynomial, it is only necessary to lower the order of all k-order or higher powers of α from f (α) = 0 by one order. That is, using equation (3),

It should just be transformed. If the left side of Expression (5) is an m-th order expression of α (k < m <2k), the right side of Expression (5) is an m-1 order expression of α. If the right side of equation (5) is regarded as a polynomial of α and the coefficient of α ⁱ is d ′ _i , equation (5) becomes
_{^{Σ i = 0 2k-1 d}} i α i = Σ i = 0 2k-1 d 'i α i (6)
And multiply. However, when i > m, d ′ _i = 0. GF [0005] In the vertical vector 2k-dimensional vector _{d i} with the original elements on the (q)
(Equation 2)

This process uses a matrix as follows:
(Equation 3)

[0007]
(Blanks are assumed to be 0, and so on). The vertical and horizontal lines in the 2k row and 2k column matrix on the right side are given for convenience, and the upper left small matrix (unit matrix) divided by the vertical and horizontal lines is the first term on the right side of equation (5). The upper and lower small matrices on the right correspond to the second term on the right. For convenience of explanation, a name is given to the separated small matrix, and Expression (7) is expressed by the following expression.
(Equation 4)

I will express it. I is a unit matrix of k rows and k columns, and O is a zero matrix of k rows and k columns. Also,
[0009]
(Equation 5)

[0010]
And Multiplying the matrix once by the vertical vector in equation (8) is equivalent to converting the m-th order expression of α into the m-1 order expression using the relationship of f (α) = 0. Therefore, converting a 2k-1 degree expression of α into a k-1 degree expression is nothing but multiplying the matrix of Expression (8) by k times the vertical vector. That is, reduction is [0011]
(Equation 6)

None other than the (however i> _c i = 0 when k).
[0012]
(Equation 7)

Is calculated sequentially as the second power and the third power.
[0013]
(Equation 8)

[0014]
It becomes. = _R ¹ k _-I in place ^{_{(R 1 -I) (R 1}} k-1 + R 1 k-2 + ... + R 1 + I)
Since R ₁ is a matrix of the equation (10), it becomes 0 when raised to the k-th power. Thus ^{_{-I = (R 1 -I) (}} R 1 k-1 + R 1 k-2 + ... + R 1 + I)
When both sides are multiplied by (R ₁ -I) ⁻¹ ,
^{_{- (R 1 -I) -1 =}} R 1 k-1 + R 1 k-2 + ... + R 1 + R 0
(IR ₁ ) ^-1 = Σ _{i = 0} ^k-1 R ₁ ⁱ
This relationship is substituted into equation (11), and since R ₁ ^k = 0,
(Equation 9)

It becomes. If R ′ = R ₀ (I−R ₁ ) ⁻¹ , equation (10) becomes
(Equation 10)

[0017]
And multiply. Since the product of the two k-1 order polynomials is a 2k-2 order polynomial, the k-order extension of GF (q) by irreducible k-order polynomial f (x) on GF (q) GF (q ^k ) = GF When considering the multiplication of two elements on (q) [x] / (f (x)), d _2k−1 = 0. Therefore, the columns actually required in R 'are the 0th column to the (k-2) th column. The matrix R of k rows (k-1) columns from the 0th column to the (k-2) th column of the matrix R 'is called a reduction matrix, and Expression (13) is simply expressed by using R.
(Equation 11)

[0019]
Can be expressed as From equation (14), it can be seen that whether the multiplication of two elements on GF (q) [x] / (f (x)) can be calculated at high speed depends on the nature of the reduction matrix R. The reduction in the multiplication of two elements over the general extension field GF (q) [x] / (f (x)) is obtained by using k (k-1) times from equations (7), (8), and (14). An operation of multiplying by a constant on GF (q) and adding on k (k−1) times on GF (q) is required. On the other hand, in the case of an extended field GF (q) [x] / (x ^k −r) based on an irreducible binomial polynomial which has been conventionally assumed to be fast, R ′ = rI, so (k−1) times of GF Only (q) upper constant times (r times) and (k-1) times of additions on GF (q) are required. Whether the binomial expression x ^k -r is irreducible or not depends on the value of the definition field q and the extension order k. For example, when q = 65539 and k = 10, there is no irreducible binomial expression. In such a case, it was conventionally considered that an efficient multiplication device could not be constructed. Alternatively, when q = 4201 and k = 10, the irreducible binomial expression x ^k -r is r = ± 11, ± 13, ± 19,... Times addition is required, and r times is not always fast. However, even in such a case, an efficient multiplication device can be configured by following the procedure described below.
[0020]
Step 1: A reduction matrix R corresponding to all irreducible polynomials that can be searched is calculated according to the above procedure.
Step 2: Check the property related to the calculation cost of the reduction calculation by R.
Step 3: Among all irreducible polynomials that can be searched, find the irreducible polynomial f (x) with the lowest operation cost.
Step 4: The configuration of the reduction operation device at f (x) is performed to configure the multiplication device.
[0021]
Even if the irreducible polynomial that can be searched for in the above procedure includes the irreducible binomial polynomial, the procedure does not change at all. Therefore, in this way, the most efficient multiplication device can be configured for all irreducible polynomials that can be searched, including irreducible binomial polynomials.
That is, in the present invention, the irreducible polynomial determined as described above is used, and the operation cost of the reduction operation is low. That is, the reduction matrix R used in the reduction operation means has at least half the number of elements of the matrix as zero elements. In the reduction operation, the product-sum operation on the GF (q) of the zero element portion of the matrix R is omitted, and the reduction operation can be performed at high speed.
Alternatively, a general matrix of k rows and k-1 columns is transformed into a standard form by basic transformation.
(Equation 12)

[0023]
Assuming that the minimum number of basic transformations required to make M is the reduction matrix R is such that it becomes a standard form with a basic transformation of M / 2 or less, and the matrix R has such properties, Many reduction calculation means are configured to divert a partial calculation result of a certain row in a reduction calculation to a calculation of another row, so that reduction can be performed at a high speed.
With such a configuration, an irreducible polynomial of a third or higher order consisting of three terms or a fourth or higher order consisting of four terms is used.
In general, the matrix V in equation (12) is
(Equation 13)

[0025]
It can be decomposed as follows. This corresponds to decreasing the order by one using the relation of f (α) = 0 in order from the term with the highest order when performing reduction. Therefore, even if it is not a binomial polynomial, if the number of terms is small and r _i times is high, reduction can be performed at high speed. Even if the number of terms is large, the reduction can be performed at high speed if the matrix V can be decomposed into a product of a small number of sparse matrices having small absolute values of elements by some decomposition. The fact that such a decomposition can be performed is equivalent to the fact that, in the calculation of the equation (14), a partial result in the calculation process of a certain row can be used for the calculation of another row. For example q = 65539, k = 10 in the case of ^{f (x) = x 10 -x} 9 -1 or ^{f (x) = x 10 -x} -1, q = 4201, k = 10 in the case of f (x) = X ¹⁰ + x ⁹ +1 or f (x) = x ¹⁰ + x + 1 is not a binomial expression, but can reduce at high speed.
[0026]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, examples of the present invention will be described.
FIG. 1 shows a case where the present invention is applied to a multiplication device of an expanded field GF (q ^k ). The multiplication device 1A inputs elements A and B on GF (q ^k ) and outputs the product C = A × B. Elements A, B, and C on GF (q ^k ) K-dimensional vectors a _i , b _i , c _i (where 0 < i <k) having elements on GF (q) as elements, and k-th irreducible polynomial f (x) on GF (q) If one solution of = 0 is α, A = Σ _{i = 0} ^k−1 _ai α ⁱ , B = Σ _{i = 0} ^k−1 b _i α ⁱ , C = Σ _{i = 0} ^k−1 c _i α ⁱ
Means In this embodiment, for simplicity, the case of k = 10 will be described. However, in general, if the number of terms of f (x) is m, the effect of the present invention can be enjoyed even for k of m-1 or more. The device 1A includes a polynomial multiplication device 1B and a reduction device 1C.
[0027]
The polynomial multiplication device 1B receives k-dimensional vectors a _i and b _i (where 0 < i <k) having elements on GF (q) as elements, and obtains a coefficient polynomial ｘ _{j = 0} ^2k on x on GF (q). ^{_{-2 d j x j = (Σ}} i = 0 k-1 a i x i) (Σ i = 0 k-1 b i x i) (16)
Coefficients _{d j} (where 0 <j <2k-1) operation on the output of.
Reduction device 1C coefficients _{d i} is input, the equation (14) is operational, f (α) Σ _i ⁼ the alpha satisfy _{^{= 0 0 k-1 c i}} α i = Σ j = 0 2k-2 d j α ^j (17)
The coefficient c _i (where 0 < i <k) is output.
[0028]
The reduction device 1C is configured, for example, as shown in FIG. This example reduction matrix R the reducing matrix equation specifically k = 10, f (x) = x 10 -x-1 is used when more than half of its components is zero element (9), wherein The following equation is obtained from (12).
[0029]
[Equation 14]

[0030]
In other words, the matrix R has 72 zero elements out of 10 × 9 = 90, that is, 80%. The calculation of equation (14) using the reduction matrix R can be configured as shown in FIG. (+) In FIG. 2 represents addition on GF (q). In this case, both the identity matrix I and the reduction matrix R are composed of one element and zero element, d _{0 to} d ₉ are operations with the identity matrix I, and d _{10 to} d ₁₈ are operations with the reduction matrix R. In addition, for each row, d ₀ to d _{18 that} are calculated with one element in the unit matrix I and the reduction matrix R are added. For example operation of an identity matrix I in the second row is d _1, the calculation of the reduction matrix R is d ₁₀ and d _11, a c ₁ these d ₁ and d ₁₀ and d ₁₁ is added .
[0031]
Since the reduction device 1C is configured as described above, the cost for performing the reduction in this device 1C is 18 additions. In general, when the k-th order expression f (x) = x ^k −x−1 is irreducible, the cost for performing the reduction is 2 (k−1) additions, and a constant multiple (r times) of the binomial expression is added. In the case where the operation cannot be performed faster than one time, this embodiment is faster.
FIG. 3 shows another configuration example of the reduction device 1C. In this case, as described above, if the number of basic transformations required to convert a general matrix of k rows and k-1 columns into a standard form by the basic transformation is M times, the reduction matrix R becomes M / 2 times In the following basic modification, a reduction matrix R in a standard form is used. In this embodiment, the reduction matrix R is k = 10, f (x) = x ¹⁰ −x ⁹ −1. Given.
[0032]
(Equation 15)

[0033]
The matrix R is obtained by, for example, subtracting the corresponding elements of all other rows by the elements of the ninth row, and calculating the corresponding matrix of the elements of the other rows by the elements of the eighth row. Are subtracted from each other, and the corresponding elements of all other rows are respectively subtracted by the elements of the seventh row with respect to the resulting matrix, and if the same operation is performed in the following, the basic transformation is performed in a small number of times as few as nine times. It can be shaped.
In such a reduction matrix to determine the operation _{d 17 (+) d 18 (} +) c 6 operation result of _d 17 _{(+) d 18} in _{d 7} for obtaining, for example, _{c 7,} as shown in FIG. 3 operation _d 16 for _{(+) d 17 (+)} d 18 (+) d 17 in _{d 6 (+)} is diverted to the calculation of the _{d 18,} also operation _d 15 for obtaining the _{c 5 (+) d 16 (+) d 17 (+)} d 18 (+) d d 16 in _{5 (+) d 17 (+} ) calculation of _{d 18} is in operation for obtaining the _{c 6 d 16 (+) d} 17 (+ ) calculation result of the d ₁₈ is diverted, as follows, are diverted partial operation result of one row in the calculation of the other rows, especially in the example of FIG. 3 is performed sequentially in cascade manner that diverting operation means Therefore, the number of calculations as a whole is reduced as compared with the case where calculations are performed here. In the reduction device 1C, the cost for performing the reduction is 18 additions. In general, when the k-th order expression f (x) = x ^k −x ^k−1 −1 is irreducible, the cost for performing the reduction is 2 (k−1) additions, which is a constant multiple of the binomial expression (r times ) Cannot be performed faster than one addition, this embodiment is faster.
[0034]
The extended field multiplication according to the present invention can also be performed by causing a computer to execute a program. FIG. 4 shows the configuration. An input / output interface 11, a storage unit 12, a CPU (central processing unit) 13, a program memory 14 storing a basic program for operating a computer, a hard disk 15 storing various application programs, a RAM 16 and the like are connected to a bus 17. I have. A program for performing the extension field multiplication is transferred from the hard disk 15 to the RAM 16, and the program is executed, whereby the GF expressed by a k-dimensional vector having an element on GF (q) as an element is obtained from the input / output interface 11. When the elements A and B on (q ^k ) are input, they are fetched and stored in the storage unit 12 (S1) (see FIG. 5).
[0035]
Thereafter, the elements A and B are extracted from the storage unit 12, and the CPU 13 executes the polynomial operation processing 18, that is, the coefficients d _j (0) satisfying the expression (16) from a _i and b _i (0 < i <k). < J <2k-1), and store these coefficients _dj in the storage unit 12 (S2).
Then removed _{d j} from the storage unit 12, by performing the reduction processing 19 calculates the coefficients _{c i} satisfies the formula (17) by calculating the equation (14) (S3), a result GF ( The element C on GF (q ^k ) consisting of the vector of element c _i on q) is output from the output interface 11 to the outside (S4).
[0036]
The calculation of the reduction device 1C shown in FIG. 2 by a computer, that is, the reduction calculation process in FIG. 5 may be performed by, for example, the procedure shown in FIG. d ₀ and d ₁₀ are fetched from the storage unit 12, added together, and stored as c ₀ in the storage unit 12 (S 1).
D ₁ , d ₁₀ , and d ₁₁ are taken out from the storage unit 12, added, and stored as c ₁ in the storage unit 12 (S 2).
D ₂ , d ₁₁ , and d ₁₂ are extracted from the storage unit 12, added together, and stored as c ₂ in the storage unit 12 (S 3).
D ₃ , d ₁₂ , and d ₁₃ are extracted from the storage unit 12, added, and stored as c ₃ in the storage unit 12 (S 4).
D ₄ , d ₁₃ , and d ₁₄ are extracted from the storage unit 12, added together, and stored as c ₄ in the storage unit 12 (S 5).
D ₅ , d ₁₄ , and d ₁₅ are extracted from the storage unit 12, added, and stored as c ₅ in the storage unit 12 (S 6).
D ₆ , d ₁₅ , and d ₁₆ are extracted from the storage unit 12, added, and stored as c ₆ in the storage unit 12 (S 7).
D ₇ , d ₁₆ , and d ₁₇ are taken out from the storage unit 12, added together, and stored as c ₇ in the storage unit 12 (S 8).
D ₈ , d ₁₇ , and d ₁₈ are extracted from the storage unit 12, added, and stored as c ₈ in the storage unit 12 (S 9).
D ₉ and d ₁₈ are extracted from the storage unit 12, added together, and stored as c ₉ in the storage unit 12 (S 10).
[0037]
Note that the order of these steps S1 to S10 may be arbitrary.
In order for the computer shown in FIG. 3 to perform a reduction calculation process by a computer, for example, the processing shown in FIG. 7 may be performed.
First, d ₁₈ is retrieved from the storage unit 12 and temporarily stored in a register in the CPU 13 as t (S1).
D ₈ and d ₁₇ are taken out of the storage unit 12, the d ₁₇ and t are added, the t in the register is updated with the result, and the t and d ₈ are added and stored in the storage unit 12 as c _8. (S2),
D ₇ and d ₁₆ are taken out of the storage unit 12, d ₁₆ and t are added, t is updated in the register with the result, and the t and d ₇ are added and stored as c ₇ in the storage unit 12. (S3),
D ₆ and d ₁₅ are taken out of the storage unit 12, d ₁₅ and t are added, t is updated in the register with the result, and d ₆ and t are added and stored as c ₆ in the storage unit 12 (S 4). ),
D ₅ and d ₁₄ are taken out of the storage unit 12, d ₁₄ and t are added, t is updated in the register with the result, and the t and d ₅ are added and stored as c ₅ in the storage unit 12 ( S5),
D ₄ and d ₁₃ are taken out from the storage unit 12, d ₁₃ and t are added, t is updated in the register with the result, and the t and d ₄ are added and stored in the storage unit 12 as c _4. (S6),
D ₃ and d ₁₂ are taken out from the storage unit 12, d ₁₂ and t are added, t is updated in the register with the result, and the t and d ₃ are added and stored in the storage unit 12 as c ₃ ( S7),
D ₂ and d ₁₁ are extracted from the storage unit 12, d ₁₁ and t are added, t is updated in the register with the result, and the t and d ₂ are added and stored as c ₂ in the storage unit 12 ( S8),
D ₁ and d ₁₀ are extracted from the storage unit 12, d ₁₀ and t are added, t is updated in the register with the result, and the t and d ₁ are added and stored as c ₁ in the storage unit 12 ( S9),
D ₀ and d ₉ are extracted from the storage unit 12, d ₉ and t are added, t is updated in the register with the result, and the t and d ₀ are added and stored as c ₀ in the storage unit 12 ( S10).
[0038]
As the k-th order polynomial f (x) used for the k-th extension, it is preferable that the coefficient of each term becomes ± 1 when the coefficient of each term is divided by the coefficient of the highest order, that is, when monic occurs. In this way, the components of the reduction matrix R are composed of zero elements and one element, so that it is not necessary to perform a constant multiplication operation, and high-speed operation becomes possible.
In FIG. 4, the external disk device 22 may be driven via a drive unit 21 to execute a program recorded in the external disk device 22 to perform the above processing. In the above description, the present invention is applied to a multiplication device. However, in general, in an operation on a ^k-th extension field GF (q ^k ) of GF (q) by an irreducible k-th polynomial f (x) on GF (q), During execution, a 2k-1 dimensional vertical vector d having an element on GF (q) as an element is used as a k-dimensional vertical vector c having an element as an element on GF (q) using a relation of f (x) = 0. The present invention can be applied to an extended field arithmetic device that performs reduction.
[0039]
【The invention's effect】
When there is no existing irreducible binomial expression on the conventional GF (q), the reduction in the multiplication on GF (q) [x] / (f (x)) is reduced by k (k−1) times the constant times on GF (q). Although it is considered that k (k-1) addition operations on GF (q) are required, according to the present invention, 2 (k-1) addition operations on GF (q) are performed at the most efficient time. The reduction can be executed with. The above fixed multiple on GF (q) costs much more than the addition on GF (q), but even if it is estimated that the constant multiple on GF (q) is 5 times the addition on GF (q), k = 10 Can speed up the reduction 30 times. Even if there is an irreducible binomial expression x ^k -r on GF (q), when r times cannot always be executed at high speed, estimating r times as 5 times the addition on GF (q) gives the most efficient According to the present invention, reduction can be performed three times faster.
[Brief description of the drawings]
FIG. 1 is a diagram showing a configuration of a GF (q ^k ) multiplication device.
FIG. 2 is a diagram showing a specific example of a reduction device 1C in FIG.
FIG. 3 is a view showing another specific example of the reduction device 1C in FIG. 1;
FIG. 4 is a block diagram showing an example in which the present invention is realized by a computer.
FIG. 5 is a diagram showing a flow of GF (q ^k ) multiplication processing.
FIG. 6 is a diagram showing a flow of a reduction calculation process.
FIG. 7 is a diagram showing a flow of another example of the reduction operation processing.

Claims (8)

Let q be a prime number or a power of a prime number, and a k-order extension of GF (q) by an irreducible k-order polynomial f (x) on a finite field GF (q) GF (q ^k ) = GF (q) [x] / ( During execution of the original operation on f (x)), a 2k-1 dimensional vertical vector [d] having an element on GF (q) as an element is converted into a k-dimensional vertical vector [ c] is a computing device comprising reduction means for performing reduction using f (x) = 0,
The reduction means receives the vertical vector [d], and receives a k-by-k column unit matrix I having elements on GF (q) as elements and a k-th order polynomial f (x). For a matrix R of k rows and k-1 columns having elements as elements,
[C] = [I | R] [d]
And outputs the result as the vertical vector [c].
An extended field operation device, wherein the matrix R has the lowest reduction operation cost in a reduction matrix corresponding to an irreducible polynomial that can be searched . Let q be a prime number or a power of a prime number, and k-th order expansion of GF (q) by an irreducible k-order polynomial f (x) on a finite field GF (q) GF (q ^k ) = GF (q) [x] / ( During execution of the original operation on f (x)), a 2k-1 dimensional vertical vector [d] having an element on GF (q) as an element is converted into a k-dimensional vertical vector [ c] is a computing device comprising reduction means for performing reduction using f (x) = 0,
The reduction means receives the vertical vector [d], and receives a k-by-k column unit matrix I having elements on GF (q) as elements and a k-th order polynomial f (x). For a matrix R of k rows and k-1 columns having elements as elements,
[C] = [I | R] [d] (E)
And outputs the result as the vertical vector [c].
Standard k-by-k-1 matrix by basic transformation

If the minimum number of basic deformations required to satisfy the above condition is M, the matrix R becomes a standard form with a basic deformation of M / 2 or less. The device according to claim 2,
The enlargement field arithmetic device according to claim 1, wherein said reduction means includes means for diverting a partial calculation result of a certain row to another row calculation in the calculation of said equation (E). The device according to any one of claims 1 to 3,
The extended field operation device, wherein the polynomial f (x) is a third-order or fourth-order or higher polynomial composed of three or four terms. The device according to any one of claims 1 to 4,
An enlarged field arithmetic unit wherein the value of the polynomial f (x) is ± 1 when the coefficient of the other term is divided by the coefficient of the highest-order term. The product C of elements A and B on a ^k-th extension GF (q ^k ) of GF (q) by an irreducible k-th order polynomial f (x) on a finite field GF (q) (q is a prime number or a power of a prime number) = A × B as one of the solutions of f (x) = 0, a k-dimensional vector A = Σ _{i = 0} ^k−1 a _i α ⁱ having an element on GF (q) as an element, ^{_{B = Σ i = 0 k-}} 1 b i α i (0 <i <k)
To the computer of the device that calculates using
Processing for storing the input A and B in the storage means;
From the storage means determined said performing polynomial multiplication extracts the A and ^{_{B Σ i = 0 2k-2}} d i α j (0 <j <2k-1), a process of storing the coefficients _{d j} in the storage means ,
The above _dj is taken out from the storage means, and a k-row k-column unit matrix I having an element on GF (q) as an element and a k having an element on GF (q) determined by the k-th order polynomial f (x) as an element For a matrix R of row k-1 columns,
[C] = [IR] [d]
And a reduction process for calculating
Recording medium for recording a program for executing a process of outputting the operation result ^{_{Σ i = 0 k-1 c}} i as C. The recording medium according to claim 6,
A recording medium characterized in that the matrix R has the lowest reduction operation cost in a reduction matrix corresponding to an irreducible polynomial that can be searched . The recording medium according to claim 6,
A recording medium characterized in that the reduction process includes a process of cascading at least a plurality of times using a partial calculation result of a certain row for a calculation of another row.

Images