(57)【要約】【課題】  有限体での基底変換方法及び基底変換装置を提供する。【解決手段】  定義多項式が五項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１であり、指数ｎ，ｋ（３），ｋ（２），ｋ（１）が条件ｎ−ｋ（３）＞ｋ（３）−ｋ（１）を満たす基底変換行列を用いて、効率的な基底変換行列Ｄsd、Ｄds及び基底変換方法が提供されている。さらに前記基底変換を行うための基底変換装置が提供されている。定義多項式として用いられる五項式が、任意の次元で一般的な形態を有しているので、標準表現と双対表現との間の変換が効率的に行われる。したがって、双対基底乗算器が効率的に実現される。【選択図】      図２
2004166274.tif 000002
【特許請求の範囲】
【請求項１】
ｎビットからなり、基底変換行列の各行ベクトルを格納するトークンレジスタと、
ｎビットからなり、基底変換されるベクトルを格納するデータレジスタと、
前記トークンレジスタの出力と前記データレジスタの出力との間のビット乗算を行うｎ個のビット乗算器と、
前記ビット乗算器の出力端に連結され、前記ビット乗算の結果を加算する加算器とを備えた基底変換装置によって行われ、
定義多項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１を用いて、有限体ＧＦ（２n）の元Ｂの標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）が双対基底表現係数ベクトルＢ’＝（ｂ’0，ｂ’1，ｂ’2，…，ｂ’n-1）に変換される、有限体ＧＦ（２n）での標準基底を双対基底に変換する基底変換方法であって、
前記定義多項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１の指数ｎ，ｋ（３），ｋ（２），ｋ（１）を入力するステップと、
変換される前記標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）を前記データレジスタに格納するステップと、
ベクトル式
（ｂ’0，ｂ’1，ｂ’2，…，ｂ’k(1)）＝（ｂ0＋ｂk(1)，ｂk(1)-1，ｂk(1)-2，…，ｂ0）
を用いて、前記双対基底表現係数ベクトルＢ’の０番目ないしｋ（１）番目の成分を求めるステップと、
ベクトル式
（ｂ’k(1)+1，ｂ’k(1)+2，…，ｂ’k(1)+n-k(3)）＝（ｂn-1，ｂn-2，…，ｂk(3)）
を用いて、前記双対基底表現係数ベクトルＢ’の（ｋ（１）＋１）番目ないし（ｋ（１）＋ｎ−ｋ（３））番目の成分を求めるステップと、
ベクトル式
（ｂ’k(1)+1+n-k(3)，ｂ’k(1)+2+n-k(3)，…，ｂ’k(1)+n-k(2)）＝（ｂk(3)-1＋ｂn-1，ｂk(3)-2＋ｂn-2，…，ｂk(2)＋ｂn-k(3)+k(2)）
を用いて、前記双対基底表現係数ベクトルＢ’の（ｋ（１）＋１＋ｎ−ｋ（３））番目ないし（ｋ（１）＋ｎ−ｋ（２））番目の成分を求めるステップと、
ベクトル式
（ｂ’k(1)+1+n-k(2)，ｂ’k(1)+2+n-k(2)，…，ｂ’n-1）＝（ｂk(2)-1＋ｂn-1-k(3)+k(2)＋ｂn-1，ｂk(2)-2＋ｂn-2-k(3)+k(2)＋ｂn-2，…，ｂk(1)+1＋ｂn+1-k(3)+k(1)＋ｂn+1-k(2)+k(1)）
を用いて、前記双対基底表現係数ベクトルＢ’の（ｋ（１）＋１＋ｎ−ｋ（２））番目ないし（ｎ−１）番目の成分を求めるステップと、
を含むことを特徴とする有限体ＧＦ（２n）での標準表現を双対表現に変換する基底変換方法。
【請求項２】
ｎビットからなり、基底変換行列の各行ベクトルを格納するトークンレジスタと、
ｎビットからなり、基底変換されるベクトルを格納するデータレジスタと、
前記トークンレジスタの出力と前記データレジスタの出力との間のビット乗算を行うｎ個のビット乗算器と、
前記ビット乗算器の出力端に連結され、前記ビット乗算の結果を加算する加算器とを備えた基底変換装置によって行われ、
定義多項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１を用いて、有限体ＧＦ（２n）の元Ｂの標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）が双対基底表現係数ベクトルＢ’＝（ｂ’0，ｂ’1，ｂ’2，…，ｂ’n-1）に変換される、有限体ＧＦ（２n）での標準基底を双対基底に変換する基底変換方法であって、
前記定義多項式の指数ｎ，ｋ（３），ｋ（２），ｋ（１）を入力するステップと、
変換される前記双対基底表現係数ベクトルＢ’＝（ｂ’0，ｂ’1，ｂ’2，…，ｂ’n-1）を前記データレジスタに格納するステップと、
ベクトル式
（ｂ0，ｂ1，…，ｂk(1)-1，ｂk(1)）＝（ｂ’k(1)，ｂ’k(1)-1，…，ｂ’1，ｂ’0＋ｂ’k(1)）
を用いて、前記標準基底表現係数ベクトルＢの０番目ないしｋ（１）番目の成分を求めるステップと、
ベクトル式
（ｂk(1)+1，ｂk(1)+2，…，ｂk(2)-1）＝（ｂ’k(2)-1＋ｂ’k(3)-1＋ｂ’n-1，ｂ’k(2)-2＋ｂ’k(3)-2＋ｂ’n-2，…，ｂ’k(1)+1＋ｂ’k(1)+1+k(3)-k(2)＋ｂ’n+1+k(1)-k(2)）
を用いて、前記標準基底表現係数ベクトルＢの（ｋ（１）＋１）番目ないし（ｋ（２）−１）番目の成分を求めるステップと、
ベクトル式
（ｂk(2)，ｂk(2)+1，…，ｂk(3)-1）＝（ｂ’k(1)+k(3)-k(2)＋ｂ’n+k(1)-k(2)，ｂ’k(1)+k(3)-k(2)-1＋ｂ’n+k(1)-k(2)-1，…，ｂ’k(1)+1＋ｂ’n+1+k(1)-k(3)）
を用いて、前記標準基底表現係数ベクトルＢのｋ（２）番目ないし（ｋ（３）−１）番目の成分を求めるステップと、
ベクトル式
（ｂk(3)，ｂk(3)+1，…，ｂn-1）＝（ｂ’n+k(1)-k(3)，ｂ’n+k(1)-k(3)-1，…，ｂ’k(1)+1）
を用いて、前記標準基底表現係数ベクトルＢのｋ（３）番目ないし（ｎ−１）番目の成分を求めるステップと、
を含むことを特徴とする有限体ＧＦ（２n）での双対表現を標準表現に変換する基底変換方法。
【請求項３】
定義多項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１にしたがう基底変換行列を用いて、有限体ＧＦ（２n）の元Ｂの標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）と双対基底表現係数ベクトルＢ’＝（ａ’0，ａ’1，ａ’2，…，ａ’n-1）との間の変換が行われる、有限体ＧＦ（２n）での標準基底と双対基底との間の基底変換を行う基底変換装置であって、
（ｋ（１）＋１）ビットの上位トークンレジスタ及び（ｎ−ｋ（１）−１）ビットの下位トークンレジスタに分類されるｎ個のシフトレジスタからなり、前記シフトレジスタはそれぞれ、イネーブル信号及びクロックに応答してクロック毎に入力データを１ビットずつ左側にシフトし、前記シフトレジスタの出力は、それぞれ前記基底変換行列の各行の成分に対応しているトークンレジスタと、
前記定義多項式の成分ｎ，ｋ（３），ｋ（２），ｋ（１）が入力されて、（ｎ−１）ビットの選択線の制御信号、前記トークンレジスタのシフト動作を起動させるイネーブル信号、前記トークンレジスタのクロック、前記上位トークンレジスタ及び前記下位トークンレジスタの初期値、前記トークンレジスタのｋ（１）番目レジスタのデータ入力信号及び前記トークンレジスタの（ｎ−１）番目レジスタのデータ入力信号を出力するトークン制御部と、
前記選択線の制御信号に応答して前記ｋ（１）値にしたがい上位トークンレジスタと下位トークンレジスタとを分離し、前記トークンレジスタのデータ入力経路を選択するマルチプレクサと、
変換される係数ベクトルを格納するデータレジスタと、
前記トークンレジスタの出力と前記データレジスタの出力との間のビット間乗算を行うＡＮＤゲート部と、
前記ＡＮＤゲート部の全ての出力を加算するＸＯＲゲートと、
前記ＸＯＲゲートに連結され、前記ＸＯＲゲートの出力をクロックに同期させる出力レジスタと、
を備えたことを特徴とする有限体ＧＦ（２n）での基底変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は有限体ＧＦ（２n）での基底変換に関し、特に標準基底による標準表現と双対基底による双対表現相互間の基底変換方法及び基底変換装置に関する。
【背景技術】
【０００２】
有限体ＧＦ（２n）は、２n個の元（elements）を含む数体系（number system）である。有限体の各元がｎビットで表現可能である事実に基づき、有限体を有用に利用することが可能である。エラー訂正コード（error correction codes）や、ハードウエアにおける楕円曲線暗号システム（elliptic curve cryptosystem）の実装等、有用な利用法はＧＦ（２n）に関する計算を多く使用している。リードソロモンコード（Reed-Solomon codes）を暗号化／復号化する装置は、ＧＦ（２n）に関する計算を行う必要があり、楕円曲線暗号システムの暗号／解読装置は、「ｎ」が大きい値であるＧＦ（２n）に関する計算を行う必要がある。
【０００３】
有限体ＧＦ（２）は、式（１）によって定義される加算則及び乗算則を有しており、その元として二つの数０，１のみを有する数体系である。
【数１】
2004166274.tif 000003
【０００４】
すなわち、加算はビット排他的論理和演算（eXclusive OR operation）であり、乗算はビット論理積演算（AND operation）である。
【０００５】
有限体ＧＦ（２n）（ｎ＞１）は、２n個の元を含む数体系である。この数体系において加算及び乗算は、ＧＦ（２）の係数（coefficient）を有する既約ｎ次多項式（irreducible n-degree polynomial）に関する算術モジュロ（arithmetic modulo）に対応している。この既約ｎ次多項式は、定義多項式（defining polynomial）とよばれている。この定義多項式の根をαとするとき、有限体の元は式（２）によって定義される標準表現（standard representation）を有している。
【数２】
2004166274.tif 000004
【０００６】
ＧＦ（２n）の二つの元の乗算は、αに関する多項式乗算（polynomial multiplication）に続く、定義多項式によるモジュロ演算（modulo operation）によって行われる。ＧＦ（２n）の二つの元の加算は、αに関する多項式加算（polynomial addition）によって行われる。
【０００７】
有限体ＧＦ（２n）の元を表すのには、代表的な三つの方法がある。これらの方法は、それぞれ異なる基底によって定義されている。標準表現では、有限体ＧＦ（２n）の元は標準基底（standard basis）（polynomial basisともいう）｛１，α，α2，α3，…，αn-1｝を用いて表される。さらに、双対基底（dual basis）及び正規基底（normal basis）がある。
【０００８】
式（３）は、互いに双対性を有する二つの基底｛βi｝及び｛γj｝を定義している。
【数３】
2004166274.tif 000005
【０００９】
言い換えれば、式（３）を満たす二つの基底｛β0，β1，β2，…，βn-1｝及び｛γ0，γ1，γ2，…，γn-1｝それぞれが、Ｔｒ（δ）の双対基底である。
【００１０】
また、次に示されるＧＦ（２n）の部分集合が基底であるとき、この基底は正規基底とよばれる。
【数４】
2004166274.tif 000006
【００１１】
ＧＦ（２n）での演算を行うのに必要な論理回路の複雑性は、有限体の元によって表される特定の方法に密接に依存している。代表的な有限体乗算器には、「双対基底乗算器（dual basis multiplier）」（例えば、非特許文献１参照。）と、「正規基底乗算器（normal basis multiplier）」（例えば、非特許文献２参照。）と、「標準基底乗算器（standard basis multiplier）」（例えば、非特許文献３参照。）と、がある。双対基底乗算器は線形帰還シフトレジスタ（linear feedback shift register）を利用して実現可能であり、基底変換を含まない場合には最も少ないチップ領域を必要とするものとして知られている。正規基底を用いた有限体演算は除算、自乗及びべき乗計算を行うのに非常に効率的であるが、高い次元でのチップ領域の減少（reduction）が要求される。また、一般的に標準基底乗算器は基底変換を要求せず、高い次元の有限体への拡張及びデザインが双対／正規基底乗算器に比べて容易である（例えば、非特許文献４参照。）。
【００１２】
双対基底乗算器において高い次元の有限体への拡張が標準基底乗算器よりも難しいのは、基底変換行列の複雑性のためである。それに対して本発明は、双対基底乗算器に用いられる基底変換行列及び基底変換方法を提供するものである。
【００１３】
以下、双対基底乗算器によって行われるアルゴリズムについて説明する。
【００１４】
多項式ｘn＋ｘk(s)＋ｘk(s-1)＋…＋ｘk(1)＋１はＧＦ（２n）の定義多項式、Ａ及びＢはＧＦ（２n）の元、基底｛β0，β1，β2，…，βn-1｝は標準基底｛１，α，α2，…，αn-1｝の双対基底である、と仮定する。行列Ｄsdは標準表現（standard representation）を双対表現（dual representation）に変換する行列であり、行列Ｄdsは双対表現を標準表現に変換する行列である。乗算演算Ｃ＝ＡＢを計算するために、入出力がいずれも双対表現である場合と、いずれも標準表現である場合とに分けて説明する。
【００１５】
まず式（４）に示すように、入出力がいずれも双対表現である場合について説明する。
【数５】
2004166274.tif 000007
【００１６】
双対基底乗算器のアルゴリズムに従い、入力が双対表現である場合であっても、基底変換が行われる。入力された元Ｂに対する基底変換を行ってＤdsＢを求めた後、行列演算Ｃ＝ＭＤdsＢが行われる。ここで、行列Ｍは式（５）によって定義されている。
【数６】
2004166274.tif 000008
【００１７】
ここで、ａn+i＝ａi＋ａi+k(1)＋ａi+k(2)＋ａi+k(3)＋…＋ａi+k(s)（ｉ＞＝０）である。
【００１８】
次に式（６）に示すように、入出力がいずれも標準表現である場合について説明する。
【数７】
2004166274.tif 000009
【００１９】
この場合には、計算がさらに複雑になる。双対基底乗算器において、標準表現が双対表現に変換される。すなわち、基底変換行列Ｄsdを用いた基底変換によって、式（７）に示すＤsdＡが求められる。
【数８】
2004166274.tif 000010
【００２０】
次にＤsdＡに基づき、式（８）に表される行列Ｍが求められる。
【数９】
2004166274.tif 000011
【００２１】
ここで、ａ’n+i＝ａ’i＋ａ’i+k(1)＋ａ’i+k(2)＋ａ’i+k(3)＋…＋ａ’i+k(s)（ｉ≧０）である。
【００２２】
次に行列演算を用いて、双対表現ＭＢが得られる。乗算結果である出力Ｃは再び双対表現にならなければいけないので、基底変換行列Ｄdsを用いてＣ＝ＤdsＭＢが求められる。
【００２３】
基底変換は、基底変換行列ＤsdまたはＤdsとベクトル（有限体の元）との乗算によって行われる。双対基底乗算器での基底変換は、特別な場合を除き、行列の複雑度が非常に高く、高い次元の有限体への拡張及びデザインが非常に難しい。
【００２４】
この基底変換に関しては、三つの従来技術がある。
【００２５】
特許文献１には、特定次元における効率的な基底変換行列と、双対基底変換器の入出力がいずれも双対表現である場合に演算ＭＤdsを効率的に行う方法とが開示されている（以下、第一の従来技術と記載する。）。
【００２６】
また非特許文献５には、特定の定義多項式における効率的な基底変換行列が開示されている（以下、第二の従来技術と記載する。）。
【００２７】
また非特許文献６には、基底変換行列を計算する方法が開示されている（以下、第三の従来技術と記載する。）。
【００２８】
本発明を明らかにするため、まずは前記従来技術の特徴について簡単に説明する。
【００２９】
特定次元における効率的な基底変換行列に関する第一の先行技術は、特定次元ｎの双対表現を標準表現に変換するために、式（９）によって定義される行列を提供している。
【数１０】
2004166274.tif 000012
【００３０】
ここでＤdsは、いずれも２ｎ個の「１」からなる基底変換行列である。行列の大きさ（size）がｎ＋１であるので、Ｃ＝ＭＤdsＢの演算における行列Ｃ，Ｍ，Ｂの大きさは、いずれもｎ＋１にあわせなければならない。行列Ｃは（ｃ0，ｃ1，ｃ2，…，ｃn-1，ｃ）の形態（form）を有しており、その最終出力は（ｃ0，ｃ1，ｃ2，…，ｃn-1）である。また行列Ｂは（ｂ0，ｂ1，ｂ2，…，ｂn-1，ｓ［Ｂ］）の形態であり、行列Ｍは式（１０）によって表される。
【数１１】
2004166274.tif 000013
【００３１】
ここで、
ｓ［Ａ］＝ａ0＋ａ1＋ａ2＋…＋ａn-1
ｓ［Ｂ］＝ｂ0＋ｂ1＋ｂ2＋…＋ｂn-1
である。
【００３２】
第一の従来技術において、特定次元ｎは式（１１）に示すものが用いられる。
【数１２】
2004166274.tif 000014
【００３３】
特定のｎ次元の定義多項式は、式（１２）によって表される。
【数１３】
2004166274.tif 000015
【００３４】
Ｃ＝ＭＤdsＢ＝ＢＭ’において式（１３）によって表される行列Ｍ’を提供することによって、第一の従来技術は効率的な双対基底乗算器を提供し、基底変換を省略する。
【数１４】
2004166274.tif 000016
【００３５】
しかし式（１１）に示すように、第一の従来技術は特定次元に限定されており、一般的な形態の代わりに、式（１２）によって表される特定形態を有する定義多項式を用いている。それに対して本発明は、特定次元に制限されず、一般的な形態を有する定義多項式、すなわち五項式（pentanomial）に適用される方法を提供するものである。
【００３６】
特定の定義多項式における効率的な基底変換行列に関する第二の従来技術は、特定形態を有する定義多項式を用いた有限体ＧＦ（２n）での、単純でかつ拡張が容易な基底変換行列を提供している。また第二の従来技術は、定義多項式が式（１４）によって表される三項式である場合及び式（１５）によって表される五項式である場合における基底変換行列を提供している。
【数１５】
2004166274.tif 000017
【数１６】
2004166274.tif 000018
【００３７】
定義多項式が式（１４）によって表される特定形態を有する三項式（trinomial）であるときには、基底変換行列Ｄds及びＤsdは式（１６）によって表される。
【数１７】
2004166274.tif 000019
【００３８】
すなわち、基底変換行列Ｄds，Ｄsdはそれぞれｎ×ｎ行列であり、ｎ個の「１」からなる。
【００３９】
定義多項式が式（１５）によって表される特定形態を有する五項式であるときには、基底変換行列Ｄds及びＤsdはそれぞれ、式（１７）及び式（１８）によって表される。
【数１８】
2004166274.tif 000020
【数１９】
2004166274.tif 000021
【００４０】
すなわち、基底変換行列Ｄds，Ｄsdはそれぞれｎ×ｎ行列であり、ｎ＋２個の「１」からなる。
【００４１】
実際のアプリケーションに用いられる有限体において、大抵の場合、三項式または五項式が定義多項式として用いられるので、第二の従来技術によって提供される基底変換行列は非常に有用である。しかし、これら基底変換行列は式（１４）及び式（１５）によって表される特定形態をそれぞれ有する三項式または五項式に使用可能であるが、一般的な形態を有する五項式には使用不可能である。それに対して本発明は、一般的な形態の五項式のための基底変換行列及び基底変換方法を提供するものである。
【００４２】
基底変換行列を計算する方法に関する第三の従来技術は、任意の有限体ＧＦ（２n）での基底変換行列を計算する方法を提供している。ここで、｛１，α，α2，…，αn-1｝はＧＦ（２n）の標準基底であり、定義多項式は式（１９）によって表される。
【数２０】
2004166274.tif 000022
【００４３】
まず、式（２０）に示されるようにβを求めた後、式（２１）を用いて、双対表現を標準表現に変換する基底変換行列Ｄdsが求められる。
【数２１】
2004166274.tif 000023
【数２２】
2004166274.tif 000024
【００４４】
しかし、βはｋ（ｉ）に対して非線形的な方法で生成されるので、基底変換行列Ｄdsはｋ（ｉ）に関して容易に表すことができない。さらに基底変換行列Ｄdsは、その逆行列Ｄsdの複雑性を考慮せずに作られているために、場合によっては逆行列Ｄsdが非常に複雑になる。それに対して本発明は、ｋ（ｉ）に対して線形的な方法で選択された基底変換行列Ｄsdを提供し、定義多項式が五項式である場合にｋ（ｉ）によって容易に定義される基底変換行列Ｄds及びＤsdを提供するものである。
【特許文献１】韓国特許出願公開第２０００−２６２５０号明細書
【非特許文献１】Ｅ．Ｒ．Ｂｅｒｌｅｋａｍｐ，“Ｂｉｔ−Ｓｅｒｉａｌ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  Ｅｎｃｏｄｅｒｓ”，ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ，Ｎｏｖ．１９８２，ｖｏｌ．ＩＴ−２８，ｐｐ．８６９−８７４
【非特許文献２】Ｃ．Ｃ．Ｗａｎｇ，Ｔ．Ｋ．Ｔｒｕｏｎｇ，Ｈ．Ｍ．Ｓｈａｏ，Ｌ．Ｊ．Ｄｅｕｔｓｃｈ，Ｊ．Ｋ．Ｏｍｕｒａ  ａｎｄ  Ｉ．Ｓ．Ｒｅｅｄ，“ＶＬＳＩ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｃｏｍｐｕｔｉｎｇ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓ  ａｎｄ  Ｉｎｖｅｒｓｅｓ  ｉｎ  ＧＦ（２ｍ）”，ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｐｕｔ．，Ａｕｇ．１９８５，ｖｏｌ．Ｃ−３４
【非特許文献３】Ｐ．Ａ．Ｓｃｏｔｔ，Ｓ．Ｅ．Ｔｒａｖａｒｅｓ  ａｎｄ  Ｌ．Ｅ．Ｐｅｐｐａｒｄ，“Ａ  Ｆａｓｔ  Ｍｕｌｔｉｐｌｉｅｒ  ｆｏｒ  ＧＦ（２ｍ）”，ＩＥＥＥ  Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ  Ｃｏｍｍｕｎ．，Ｊａｎ．１９８６，ｖｏｌ．ＳＡＣ−４
【非特許文献４】Ｉ．Ｓ．Ｈｓｕ，Ｔ．Ｋ．Ｔｒｕｏｎｇ，Ｌ．Ｊ．Ｄｅｕｔｓｃｈ  ａｎｄ  Ｉ．Ｓ．Ｒｅｅｄ，“Ａ  Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ＶＬＳＩ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｏｆ  Ｆｉｎｉｔｅ  Ｆｉｅｌｄ  Ｍｕｌｔｉｐｌｉｅｒｓ  Ｕｓｉｎｇ  Ｄｕａｌ，Ｎｏｒｍａｌ，ｏｒ  Ｓｔａｎｄａｒｄ  Ｂａｓｅｓ”，ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｃｏｍｐｕｔｅｒｓ，Ｊｕｎｅ １９８８，ｖｏｌ．３７，ｎｏ．６，ｐ．７３５−７３９
【非特許文献５】Ｍ．Ｍｏｒｉ，Ｍ．Ｋａｓａｈａｒａ  ａｎｄ  Ｄ．Ｌ．Ｗｈｉｔｉｎｇ，“Ｅｆｆｉｃｉｅｎｔ  Ｂｉｔ−Ｓｅｒｉａｌ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ａｎｄ  ｔｈｅ  Ｄｉｓｃｒｅｔｅ  Ｔｉｍｅ  Ｗｉｅｎｅｒ−Ｈｏｐｆｔ  Ｅｑｕａｔｉｏｎ  ｏｖｅｒ  Ｆｉｎｉｔｅ  Ｆｉｅｌｄｓ”，ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ，Ｎｏｖ．１９８９，ｖｏｌ．３５，ｐｐ．１１７７−１１８３
【非特許文献６】Ｄ．Ｒ．Ｓｔｉｎｓｏｎ，“Ｏｎ  Ｂｉｔ−Ｓｅｒｉａｌ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ａｎｄ  Ｄｕａｌ  Ｂａｓｅｓ  ｉｎ  ＧＦ（２ｍ）”，ＩＥＥＥ Ｔｒａｎｓ．ｏｎ Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ，Ｎｏｖ．１９９１，ｖｏｌ．３７，ｎｏ．６，ｐｐ．１７３３−１７３６
【発明の開示】
【発明が解決しようとする課題】
【００４５】
したがって本発明は、任意の次元で、定義多項式として特定形態ではない一般的な形態の五項式に適用される基底変換行列及び基底変換方法を提供することを課題とする。
【００４６】
さらに本発明は、前記基底変換方法を行う基底変換装置を提供することを課題とする。
【課題を解決するための手段】
【００４７】
前記課題を解決するために本発明は、ｎビットからなり、基底変換行列の各行ベクトルを格納するトークンレジスタと、ｎビットからなり、基底変換されるベクトルを格納するデータレジスタと、前記トークンレジスタの出力と前記データレジスタの出力との間のビット乗算を行うｎ個のビット乗算器と、前記ビット乗算器の出力端に連結され、前記ビット乗算の結果を加算する加算器とを備えた基底変換装置によって行われ、定義多項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１を用いて、有限体ＧＦ（２n）の元Ｂの標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）が双対基底表現係数ベクトルＢ’＝（ｂ’0，ｂ’1，ｂ’2，…，ｂ’n-1）に変換される、有限体ＧＦ（２n）での標準基底を双対基底に変換する基底変換方法であって、前記定義多項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１の指数ｎ，ｋ（３），ｋ（２），ｋ（１）を入力するステップと、変換される前記標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）を前記データレジスタに格納するステップと、ベクトル式（ｂ’0，ｂ’1，ｂ’2，…，ｂ’k(1)）＝（ｂ0＋ｂk(1)，ｂk(1)-1，ｂk(1)-2，…，ｂ0）を用いて、前記双対基底表現係数ベクトルＢ’の０番目ないしｋ（１）番目の成分を求めるステップと、ベクトル式（ｂ’k(1)+1，ｂ’k(1)+2，…，ｂ’k(1)+n-k(3)）＝（ｂn-1，ｂn-2，…，ｂk(3)）を用いて、前記双対基底表現係数ベクトルＢ’の（ｋ（１）＋１）番目ないし（ｋ（１）＋ｎ−ｋ（３））番目の成分を求めるステップと、ベクトル式（ｂ’k(1)+1+n-k(3)，ｂ’k(1)+2+n-k(3)，…，ｂ’k(1)+n-k(2)）＝（ｂk(3)-1＋ｂn-1，ｂk(3)-2＋ｂn-2，…，ｂk(2)＋ｂn-k(3)+k(2)）を用いて、前記双対基底表現係数ベクトルＢ’の（ｋ（１）＋１＋ｎ−ｋ（３））番目ないし（ｋ（１）＋ｎ−ｋ（２））番目の成分を求めるステップと、ベクトル式（ｂ’k(1)+1+n-k(2)，ｂ’k(1)+2+n-k(2)，…，ｂ’n-1）＝（ｂk(2)-1＋ｂn-1-k(3)+k(2)＋ｂn-1，ｂk(2)-2＋ｂn-2-k(3)+k(2)＋ｂn-2，…，ｂk(1)+1＋ｂn+1-k(3)+k(1)＋ｂn+1-k(2)+k(1)）を用いて、前記双対基底表現係数ベクトルＢ’の（ｋ（１）＋１＋ｎ−ｋ（２））番目ないし（ｎ−１）番目の成分を求めるステップと、を含むことを特徴とする。
【００４８】
また、本発明の別の態様は、ｎビットからなり、基底変換行列の各行ベクトルを格納するトークンレジスタと、ｎビットからなり、基底変換されるベクトルを格納するデータレジスタと、前記トークンレジスタの出力と前記データレジスタの出力との間のビット乗算を行うｎ個のビット乗算器と、前記ビット乗算器の出力端に連結され、前記ビット乗算の結果を加算する加算器とを備えた基底変換装置によって行われ、定義多項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１を用いて、有限体ＧＦ（２n）の元Ｂの標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）が双対基底表現係数ベクトルＢ’＝（ｂ’0，ｂ’1，ｂ’2，…，ｂ’n-1）に変換される、有限体ＧＦ（２n）での標準基底を双対基底に変換する基底変換方法であって、前記定義多項式の指数ｎ，ｋ（３），ｋ（２），ｋ（１）を入力するステップと、変換される前記双対基底表現係数ベクトルＢ’＝（ｂ’0，ｂ’1，ｂ’2，…，ｂ’n-1）を前記データレジスタに格納するステップと、ベクトル式（ｂ0，ｂ1，…，ｂk(1)-1，ｂk(1)）＝（ｂ’k(1)，ｂ’k(1)-1，…，ｂ’1，ｂ’0＋ｂ’k(1)）を用いて、前記標準基底表現係数ベクトルＢの０番目ないしｋ（１）番目の成分を求めるステップと、ベクトル式（ｂk(1)+1，ｂk(1)+2，…，ｂk(2)-1）＝（ｂ’k(2)-1＋ｂ’k(3)-1＋ｂ’n-1，ｂ’k(2)-2＋ｂ’k(3)-2＋ｂ’n-2，…，ｂ’k(1)+1＋ｂ’k(1)+1+k(3)-k(2)＋ｂ’n+1+k(1)-k(2)）を用いて、前記標準基底表現係数ベクトルＢの（ｋ（１）＋１）番目ないし（ｋ（２）−１）番目の成分を求めるステップと、ベクトル式（ｂk(2)，ｂk(2)+1，…，ｂk(3)-1）＝（ｂ’k(1)+k(3)-k(2)＋ｂ’n+k(1)-k(2)，ｂ’k(1)+k(3)-k(2)-1＋ｂ’n+k(1)-k(2)-1，…，ｂ’k(1)+1＋ｂ’n+1+k(1)-k(3)）を用いて、前記標準基底表現係数ベクトルＢのｋ（２）番目ないし（ｋ（３）−１）番目の成分を求めるステップと、ベクトル式（ｂk(3)，ｂk(3)+1，…，ｂn-1）＝（ｂ’n+k(1)-k(3)，ｂ’n+k(1)-k(3)-1，…，ｂ’k(1)+1）を用いて、前記標準基底表現係数ベクトルＢのｋ（３）番目ないし（ｎ−１）番目の成分を求めるステップと、を含むことを特徴とする。
【００４９】
また、本発明のさらに別の態様は、定義多項式Ｘn＋Ｘk(3)＋Ｘk(2)＋Ｘk(1)＋１にしたがう基底変換行列を用いて、有限体ＧＦ（２n）の元Ｂの標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）と双対基底表現係数ベクトルＢ’＝（ａ’0，ａ’1，ａ’2，…，ａ’n-1）との間の変換が行われる、有限体ＧＦ（２n）での標準基底と双対基底との間の基底変換を行う基底変換装置であって、（ｋ（１）＋１）ビットの上位トークンレジスタ及び（ｎ−ｋ（１）−１）ビットの下位トークンレジスタに分類されるｎ個のシフトレジスタからなり、前記シフトレジスタはそれぞれ、イネーブル信号及びクロックに応答してクロック毎に入力データを１ビットずつ左側にシフトし、前記シフトレジスタの出力は、それぞれ前記基底変換行列の各行の成分に対応しているトークンレジスタと、前記定義多項式の成分ｎ，ｋ（３），ｋ（２），ｋ（１）が入力されて、（ｎ−１）ビットの選択線の制御信号、前記トークンレジスタのシフト動作を起動させるイネーブル信号、前記トークンレジスタのクロック、前記上位トークンレジスタ及び前記下位トークンレジスタの初期値、前記トークンレジスタのｋ（１）番目レジスタのデータ入力信号及び前記トークンレジスタの（ｎ−１）番目レジスタのデータ入力信号を出力するトークン制御部と、前記選択線の制御信号に応答して前記ｋ（１）値にしたがい上位トークンレジスタと下位トークンレジスタとを分離し、前記トークンレジスタのデータ入力経路を選択するマルチプレクサと、変換される係数ベクトルを格納するデータレジスタと、前記トークンレジスタの出力と前記データレジスタの出力との間のビット間乗算を行うＡＮＤゲート部と、前記ＡＮＤゲート部の全ての出力を加算するＸＯＲゲートと、前記ＸＯＲゲートに連結され、前記ＸＯＲゲートの出力をクロックに同期させる出力レジスタと、を備えたことを特徴とする。
【発明の効果】
【００５０】
本発明に係る有限体ＧＦ（２n）での基底変換方法及び基底変換装置によれば、特定次元に制限されない任意の次元で特定形態ではない一般的な形態の五項式である定義多項式によって、標準表現と双対表現間の基底変換が効率的に行われる。したがって、双対基底乗算器が効率的に実現可能である。
【発明を実施するための最良の形態】
【００５１】
以下の説明では、ｎ×ｎ正方行列において、０番目行から（ｎ−１）番目行が次のように順次配列されているものとする。
【数２３】
2004166274.tif 000025
【００５２】
有限体ＧＦ（２n）の任意の二つの元（element）同士の乗算を行うために、まず各元が、ある基底に関して表されている必要がある。それには様々な表現方法があるが、代表的な方法は前記したとおりである。αが有限体ＧＦ（２n）の元であるとき、標準基底（standard basis）ＳＢは式（２２）によって表される。ＤＢは、標準基底ＳＢのトレース関数（trace function）ｆ（＝Ｔｒ（δ））に関する双対基底（dual basis）であり、式（２３）によって表される。
【数２４】
2004166274.tif 000026
【数２５】
2004166274.tif 000027
【００５３】
有限体ＧＦ（２n）の標準基底ＳＢに関する元Ａ及び元Ｂの係数ベクトルＡ＝（ａ0，ａ1，ａ2，…，ａn-1）及びＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）と、有限体ＧＦ（２n）の双対基底ＤＢに関する元Ａ及び元Ｂの係数ベクトルＡ’＝（ａ’0，ａ’1，ａ’2，…，ａ’n）及びＢ’＝（ｂ’0，ｂ’1，ｂ’2，…，ｂ’n）との間の基底変換において、元Ａ及び元Ｂは式（２４）によって表される。
【数２６】
2004166274.tif 000028
【００５４】
式（２４）に基づいて有限体の二つの元Ａ及び元Ｂの乗算を行うとき、双対表現におけるＣ＝ＡＢのｉ番目の係数は、式（２５）によって表される。
【数２７】
2004166274.tif 000029
【００５５】
すなわち、双対表現におけるＣ＝ＡＢのｉ番目の係数は、元Ｂの標準基底ＳＢの係数とαjＡの双対基底ＤＢの係数との積の和として表される。したがって、双対表現におけるＣ＝ＡＢは、式（２６）によって表される。
【数２８】
2004166274.tif 000030
【００５６】
前記したように、二つの元Ａ及び元Ｂの乗算に関し、標準基底ＳＢにおける元Ｂの係数と、双対基底ＤＢにおける元Ａの係数が必要である。そして、その結果が双対基底ＤＢの係数となる。したがって、入力値及び出力値が標準表現であるか双対表現であるかに関わらず、基底変換が必要である。この基底変換は行列の乗算（multiplication）によって行われる。ここで、双対表現を標準表現に変換する行列と標準表現を双対表現に変換する行列とは、互いに逆行列となる関係である。元Ａが１であるとき、元Ｂの標準表現が双対表現に変換される。言い換えれば、「ｆ」に関する元Ｂの双対表現Ｂ’は、式（２７）に示されるように行列の乗算によって求められる。
【数２９】
2004166274.tif 000031
【００５７】
本発明は、「標準基底ＳＢ＝｛αi｜ｉ＝０，１，…，ｎ−１｝と任意のベクトルｖ∈｛０，１｝nとが与えられたとき、ｖ＝（ｆ（１），ｆ（α），…，ｆ（αn-1））を満たす一次関数（linear function）ｆが存在する」という補助定理（lemma）に基づいた効率的な基底変換行列を提供するものである。
【００５８】
基底変換行列は、式（２７）の第１列ベクトルによって決定される。したがって「１」の数が少ない行列を得るために、第１列ベクトルは前記補助定理に基づき適当に選択可能である。式（２８）によって表される定義多項式を備えた有限体ＧＦ（２n）において、基底変換行列の第１列ベクトルは式（２９）として示される。
【数３０】
2004166274.tif 000032
【数３１】
2004166274.tif 000033
【００５９】
ベクトルｖの成分が式（２９）にしたがい選択されるとき、標準表現を双対表現に変換する基底変換行列Ｄsdは式（３０）によって表される。
【数３２】
2004166274.tif 000034
【００６０】
また双対表現を標準表現に変換する、行列Ｄsdの逆行列Ｄdsも式（３０）によって表される。
【００６１】
図１は、本発明に係る標準表現を双対表現に変換する基底変換方法の一実施形態を示すフローチャートである。ステップＳ１０では、定義多項式の指数ｎ、ｋ（３），ｋ（２），ｋ（１）が入力される。ステップＳ１２では、基底変換される係数ベクトルＢが格納される。ステップＳ１４〜Ｓ２０では、係数ベクトルＢが双対基底表現係数ベクトルＢ’に変換される。
【００６２】
本発明は、定義多項式が式（３１）によって定義される五項式であり、式（３２）に示される条件を満たす場合における基底変換行列Ｄsd，Ｄds及び基底変換方法を提供する。
【数３３】
2004166274.tif 000035
【数３４】
2004166274.tif 000036
【００６３】
より詳細には、まずステップＳ１０では、式（３１）によって定義される定義多項式の指数ｎ，ｋ（３），ｋ（２），ｋ（１）が入力される。
【００６４】
実際に用いられる有限体ＧＦ（２n）のほとんどにおいて、三項式または五項式が定義多項式として用いられる。さらに大抵の場合、ｋ（１），ｋ（２），ｋ（３）はｎの値よりも小さいので、式（３２）に示されるｋ（ｉ）に関する条件は、本発明の実用性にほとんど影響しない。
【００６５】
式（３０）に示される基底変換行列Ｄsdは、式（３３）によって簡略に書き直し可能である。
【数３５】
2004166274.tif 000037
【００６６】
式（３１）及び式（３２）にしたがい有限体ＧＦ（２n）の定義多項式が決定されるとき、式（２９）に基づき［Ｄsd］U及び［Ｄsd］Lはそれぞれ、式（３４）及び式（３５）によって定義される。
【数３６】
2004166274.tif 000038
【数３７】
2004166274.tif 000039
【００６７】
［Ｄsd］Lの全ての元のうち、式（３５）に示す「１」以外は、いずれも「０」である。［Ｄsd］Lには、（ｎ−ｋ（１）−１）個の「１」が最も長い反対角線（longest anti-diagonal）に存在し、（ｋ（３）−ｋ（１）−１）個の「１」及び（ｋ（２）−ｋ（１）−１）個の「１」が、残る二つの反対角線（remaining two anti-diagonals）に各々存在している。したがって基底変換行列Ｄsdは、式（３４）及び式（３５）に示される前記正方行列の「１」の数を合わせて、合計（ｎ＋ｋ（３）−ｋ（１）＋ｋ（２）−ｋ（１）−１）個の「１」を有している。また［Ｄsd］Lの反対角線は、基底変換行列Ｄsdの（ｋ（１）＋１）番目行、（ｋ（１）＋１＋ｎ−ｋ（３））番目行、（ｋ（１）＋１＋ｎ−ｋ（２））番目行から始まっている。もしｋ（２）−ｋ（１）＝１であれば、（ｋ（２）−ｋ（１）−１）個の「１」を有する最も短い三番目の反対角線は現れない。前記したように、基底変換行列Ｄsdはｋ（ｉ）及びｎに関する一次式として容易に表される。これは基底変換行列が格納される必要がないことを意味している。
【００６８】
したがってステップＳ１０では、五項式である定義多項式の指数ｎ，ｋ（３），ｋ（２），ｋ（１）を入力することによって、前記理論に基づき基底変換行列Ｄsdが決定される。
【００６９】
ステップＳ１２では、有限体の元Ｂの、標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）がレジスタに格納される。
【００７０】
続くステップＳ１４〜Ｓ２０は、双対規定表現係数ベクトルの成分を得るための変換に関するステップである。ステップＳ１４〜Ｓ２０で用いられる変換式は、ステップＳ１０で決定された基底変換行列Ｄsdに基づき決定される。
【００７１】
標準基底表現係数ベクトルを双対基底表現係数ベクトルに変換する演算について以下に示す。式（３６）は、有限体ＧＦ（２n）の標準基底表現係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）と双対基底表現係数ベクトルＢ’＝（ｂ’0，ｂ’1，ｂ’2，…，ｂ’k(1)）との関係を示している。
【数３８】
2004166274.tif 000040
【００７２】
基底変換行列Ｄsdの行は、０番目ないしｋ（１）番目行からなり、サイズが（ｋ（１）＋１）×（ｋ（１）＋１）の正方行列［Ｄsd］Uと、（ｋ（１）＋１）番目ないし（ｎ−１）番目行からなり、サイズが（ｎ−ｋ（１）−１）×（ｎ−ｋ（１）−１）の正方行列［Ｄsd］Lとに分けられる。
【００７３】
ステップＳ１４では、式（３７）を用いて、双対基底表現係数ベクトルＢ’の０番目ないしｋ（１）番目成分［ｂ’0，ｂ’1，…，ｂ’k(1)］Tが求められる。ここで［Ｄsd］Uは、式（３４）に示されるものと同一である。
【数３９】
2004166274.tif 000041
【００７４】
ステップＳ１４が行われた結果、式（３７）の演算結果が式（３８）によって表される。
【数４０】
2004166274.tif 000042
【００７５】
ステップＳ１６〜Ｓ２０では、式（３９）を用いて、双対基底表現係数ベクトルＢ’の（ｋ（１）＋１）番目ないし（ｎ−１）番目の成分が求められる。ここで［Ｄsd］Lは、式（３５）に示されるものと同一である。
【数４１】
2004166274.tif 000043
【００７６】
式（３５）に示されるように、［Ｄsd］Lの行は、「１」が１個の行と、「１」が２個の行と、「１」が３個の行とに分類可能である。したがって、変換式（３９）の右辺を実行するためのステップは、項が１個であるステップＳ１６と、項が２個であるステップＳ１８と、項が３個であるステップＳ２０とに分類可能である。言い換えると、ステップＳ１４では双対表現係数ベクトルＢ’の０番目ないしｋ（１）番目の成分が求められ、ステップＳ１６では双対表現係数ベクトルＢ’の（ｋ（１）＋１）番目ないし（ｋ（１）＋ｎ−ｋ（３））番目の成分が求められ、ステップＳ１８では双対表現係数ベクトルＢ’の（ｋ（１）＋１＋ｎ−ｋ（３））番目ないし（ｋ（１）＋ｎ−ｋ（２））番目の成分が得られ、ステップＳ２０では双対表現係数ベクトルＢ’の（ｋ（１）＋１＋ｎ−ｋ（２））番目ないし（ｎ−１）番目の成分が求められる。したがって、ステップＳ１４ないしＳ２０を行うことによって求められる基底変換の結果は式（４０）によって表される。
【数４２】
2004166274.tif 000044
【００７７】
本発明に係る基底変換方法が、式（４１）によって表される定義多項式を備えた有限体ＧＦ（２13）の係数ベクトルＢ＝（ｂ0，ｂ1，…，ｂ12）にどのようにして適用されるか、について以下に示す。
【数４３】
2004166274.tif 000045
【００７８】
ここで標準表現を双対表現に変換する基底変換行列Ｄsdは、式（４２）によって表される、１３×１３の正方行列である。
【数４４】
2004166274.tif 000046
【００７９】
ここで、２×２行列の［Ｄsd］Uと１１×１１行列の［Ｄsd］Lとが、式（４３）及び式（４４）に示される行列演算にしたがい分けられる。式（４４）において、行列［Ｄsd］L内に示されていない成分（element）は、いずれも０である。
【数４５】
2004166274.tif 000047
【数４６】
2004166274.tif 000048
【００８０】
図２は、本発明に係る、図１の基底変換方法を行う基底変換装置の一実施形態を示す図である。基底変換装置は、ｎビットからなり、基底変換行列の各行の成分を出力するトークンレジスタ２０と、トークンレジスタ２０を制御する制御信号ＳＥＬ＜０：ｎ−２＞，ＥＮu，ＥＮl及びトークンレジスタ２０に入力されるデータＤ＜０：ｎ−１＞を出力するトークン制御部１０と、ｎビットからなり、変換されるベクトルの成分を格納するデータレジスタ３０と、トークンレジスタ２０のｎビット出力とデータレジスタ３０のｎビットの出力とのビット乗算を行うｎ個のＡＮＤゲート（AND gate）からなるＡＮＤゲート部４０と、ＡＮＤゲート部４０に連結され、ＡＮＤゲート部４０のｎ個の出力のビット加算（bit addition）を行うＸＯＲゲート（eXclusive OR gate）５０と、選択的に設けられ、基底変換の結果をクロック信号（clock signal）に同期化して出力する出力レジスタ６０とを備えている。
【００８１】
ＡＮＤゲート部４０、ＸＯＲゲート５０及び出力レジスタ６０は、図４に詳細に図示されている。
【００８２】
図３は、図２のトークンレジスタ２０の内部構造の一実施形態を示す図である。トークンレジスタ２０は、（ｋ（１）＋１）ビットからなる上位トークンレジスタ（upper token register）２０ａと、（ｎ−ｋ（１）−１）ビットからなる下位トークレジスタ２０ｂ（lower token register）と、トークンレジスタ２０を上位トークンレジスタ２０ａと下位トークンレジスタ２０ｂとに分け、トークンレジスタ２０のデータ入力経路を選択する（ｎ−１）個のマルチプレクサ（multiplexer）２１とを備えている。
【００８３】
図２及び図３によると、トークンレジスタ２０はｎ個のシフトレジスタからなり、上位トークンレジスタ２０ａと下位トークンレジスタ２０ｂとに分類される。トークンレジスタ２０では、トークン制御部１０からのイネーブル信号（enable signals）ＥＮu，ＥＮl及びシフトクロックＣＫに応答し、シフトクロックＣＫ毎に１ビットずつ左側にデータがシフトされて出力される。シフトクロックＣＫ毎のｎ個のシフトレジスタの出力Ｔ＜０：ｎ−１＞は、基底変換行列ＤsdまたはＤdsの各行の成分の値である。
【００８４】
マルチプレクサ２１は、選択線ＳＥＬ＜０：ｎ−２＞に応答してｋ（１）の値にしたがい、トークンレジスタ２０を上位トークンレジスタ２０ａと下位トークンレジスタ２０ｂとに分ける。
【００８５】
トークン制御部１０は、五項式である定義多項式の指数ｎ，ｋ（３），ｋ（２），ｋ（１）値が入力され、（ｎ−１）ビットのマルチプレクサ２１の選択線ＳＥＬ＜０：ｎ−２＞と、トークンレジスタ２０のシフト動作（shift operation）を起動させるイネーブル信号ＥＮu，ＥＮlと、トークンレジスタ２０のシフトクロックＣＫと、上位トークンレジスタ２０ａ及び下位トークンレジスタ２０ｂにシフトクロックＣＫ毎に格納されるデータＤ＜０：ｎ−１＞とを出力する。
【００８６】
データレジスタ３０は、変換される元の係数ベクトルＢ＝（ｂ0，ｂ1，ｂ2，…，ｂn-1）を格納する。
【００８７】
基底変換行列と係数ベクトルとの間の乗算は、ＡＮＤゲート部４０及びＸＯＲゲート５０によって行われる。ＡＮＤゲート部４０は、Ｔ＜０：ｎ−１＞及びＤ＜０：ｎ−１＞のビット乗算を行う。ＸＯＲゲート５０は、ＡＮＤゲート部４０によって行われたビット乗算の結果を加算する。
【００８８】
出力レジスタ６０は、出力同期を合わせるために選択的に備えられる構成要素である。例えば、各行の成分が第０ないし第１２クロックによって決定されるときには、出力レジスタ６０は、これら成分を入力され、第１ないし第１３クロックによってベクトル成分を出力する。
【００８９】
本発明に係る、前記構成要素を有する基底変換装置によって行われる、標準表現から双対表現への変換について、以下に示す。
【００９０】
入力されたｋ（１）の値にしたがい、０番目ないしｋ（１）番目のレジスタが上位トークンレジスタ２０ａに分類され、（ｋ（１）＋１）番目ないし（ｎ−１）番目のレジスタが下位トークンレジスタ２０ｂに分類される。したがって、上位トークンレジスタ２０ａ及び下位トークンレジスタ２０ｂは分けて制御される。ここでビットｋ（１）は、上位トークンレジスタの最上位ビット（Most Significant Bit、以下ＭＳＢと記載する。）である。言い換えると、ｋ（１）番目マルチプレクサ２１の選択線ＳＥＬ＜ｋ（１）＞は、基底変換の間に外部経路を通じてｋ（１）番目のレジスタの入力値が決定されるように制御される。さらに下位トークンレジスタ２０ｂのＭＳＢに対応する（ｎ−１）番目のレジスタは、マルチプレクサ２１に連結されず、常に外部データが入力される。ｎ＝１３かつｋ（１）＝１であるときには、上位トークンレジスタ２０ａは２個のシフトレジスタからなり、下位トークンレジスタ２０ｂは１１個のシフトレジスタからなり、そして下位トークンレジスタ２０ｂのＭＳＢを除き、１２個のマルチプレクサ２１が設けられる。
【００９１】
第０クロックでは、マルチプレクサ２１の選択線ＳＥＬ＜０：ｋ（１）＞には全部１が入力され、上位トークンレジスタ２０ａは外部から入力される。また第１クロックないし第ｋ（１）クロックでは、第ｋ（１）マルチプレクサ２１の選択線ＳＥＬ＜ｋ（１）＞にのみ１が入力され、ｋ（１）番目レジスタは連続的に外部の値を入力され、ＳＥＬ＜０：ｋ（１）−１＞には全部０が入力され、第０レジスタないし第（ｋ（１）−１）レジスタは各々次のレジスタからの１ビット出力をシフトする。例えばｋ（１）＝１であるときには、第０クロックで（１  １）がマルチプレクサ２１の選択線ＳＥＬ＜０：１＞に入力され、第１クロックで（０  １）がマルチプレクサ２１の選択線ＳＥＬ＜０：１＞に入力される。第（ｋ（１）＋１）クロック以降、上位トークンレジスタ２０ａの出力はイネーブル制御（enable control）によって維持されるので、上位トークンレジスタ２０ａのマルチプレクサ２１の選択線ＳＥＬ＜０：ｋ（１）＞は、第（ｋ（１）＋２）クロックからの「don't care」である。
【００９２】
また、下位トークンレジスタ２０ｂの（ｎ−１）番目ビットを除く全てのビットに設けられるマルチプレクサ２１の選択線ＳＥＬ＜ｋ（１）＋１：ｎ−２＞は、第（ｋ（１）＋１）クロックでは、例えば全部「１」であり、下位トークンレジスタ２０ｂは第（ｋ（１）＋１）クロックでは外部入力Ｄ＜ｋ（１）＋１：ｎ−１＞に接続される。第（ｋ（１）＋２）クロック以降には、全てのマルチプレクサ２１の選択線ＳＥＬ＜ｋ（１）＋１：ｎ−２＞には、「０」が入力されて、下位トークンレジスタ２０ｂの各レジスタは次のレジスタから出力された値をシフトする。
【００９３】
上位トークンレジスタ２０ａ及び下位トークンレジスタ２０ｂの出力は、イネーブル信号（enable signal）ＥＮu，ＥＮlによって制御される。クロックＣＫに応答して所望の値が出力されている間、イネーブル信号ＥＮu，ＥＮlは、トークンレジスタ２０をイネーブル可能となるように制御されている。トークンレジスタ２０のイネーブル制御の例を以下に示す。
【００９４】
上位トークンレジスタ２０ａのイネーブル制御において、上位トークンレジスタ２０ａはイネーブル信号ＥＮuに応答して第０クロックでイネーブルされ、第（ｋ（１）＋１）クロックまでイネーブルされた状態を維持し、第（ｋ（１）＋１）クロックでの上位トークンレジスタ２０ａのシフト出力の後にディセーブル（disable）される。例えばｋ（１）＝１のときには、上位トークンレジスタ２０ａは第０クロックでイネーブルされ、外部入力に応答して（１  １）を出力する。第１クロックでは、上位トークンレジスタ２０ａは０番目ビットとしてシフトされた出力「１」を出力し、ｋ（１）番目すなわち外部入力に応答する１番目のビットとして「０」を出力する。したがって、上位トークンレジスタ２０ａは（１  ０）を出力する。第２クロックでは、シフトされた出力「０」が０番目ビットとして出力され、「０」が外部入力に応答する１番目ビットとして出力され、上位トークンレジスタ２０ａは（０  ０）を出力する。第３クロック以降、上位トークンレジスタ２０ａはディセーブルされ、出力（０  ０）が維持される。［Ｄsd］Uの成分は、それぞれ上位トークンレジスタ２０ａから出力されたビットに対応している。
【００９５】
下位トークンレジスタ２０ｂのイネーブル制御において、下位トークンレジスタ２０ｂの全ての出力は、第０クロックないし第ｋ（１）クロックで０である。下位トークンレジスタ２０ｂは、第（ｋ（１）＋１）クロックでイネーブルされるように設計されている。装置内のレジスタが動作を開始するときには、例えば下位トークンレジスタ２０ｂの全ての出力はグローバルリセット（global reset）によって０である。第（ｋ（１）＋１）クロックで、下位トークンレジスタ２０ｂがイネーブルされ、シフト動作を開始する。例えば定義多項式が五項式ｘ13＋ｘ6＋ｘ4＋ｘ＋１，ｎ＝１３，ｋ（３）＝６，ｋ（２）＝４，ｋ（１）＝１であるときには、下位トークンレジスタ２０ｂは第０クロック及び第１クロックで０を出力し、第２クロックで外部入力に応答する（０  ０…０  １）を出力するためにイネーブルされる。イネーブル状態（enabled state）は、基底変換が第１２クロックで完了されるまで維持される。第３クロックで、下位トークンレジスタ２０ｂは、左側への１ビットシフトを行うことによって（０  ０…１  ０）を出力する。左側への１ビットシフトは、各クロックで行われる。第（ｋ（１）＋１＋ｎ−ｋ（３）＝９）クロック及び第（ｋ（１）＋１＋ｎ−ｋ（２）＝１１）クロックで、１が下位トークンレジスタ２０ｂの第（ｎ−１）番目のレジスタに入力され、他のクロックでは０が入力される。それによって、シフトクロックが進行するにつれて上位トークンレジスタ２０ａ及び下位トークンレジスタ２０ｂは次のような値を有する。ここで、前の括弧内の２ビットは上位トークンレジスタ２０ａの出力であり、後の括弧内の１１ビットは下位トークンレジスタ２０ｂの出力である。
【数４７】
2004166274.tif 000049
【００９６】
一方で、基底変換行列演算は、トークンレジスタ２０の出力及びデータレジスタ３０の出力間の各ビット乗算（bit-by-bit multiplication）と、各ビット乗算結果のあらゆるビットの加算とによって行われる。基底変換行列Ｄsdの各行の成分Ｔ＜０：ｎ−１＞は、シフトクロックに応答してトークンレジスタ２０から出力され、ＡＮＤゲート部４０に備えられたｎ個のＡＮＤゲートによってデータレジスタ３０から出力される値ｂ＜０：ｎ−１＞とそれぞれ乗算される。ＡＮＤゲート部４０の出力は、ＸＯＲゲート５０によって加算される。ＸＯＲゲート５０の出力は、出力レジスタ６０によってクロックＣＫに同期されている。
【００９７】
図５は、本発明に係る双対表現を標準表現に変換する基底変換方法の一実施形態を示すフローチャートである。ステップＳ３０では、定義多項式の指数ｎ，ｋ（３），ｋ（２），ｋ（１）が入力される。ステップＳ３２では、基底変換される係数ベクトルＢ’が格納される。ステップＳ３４〜Ｓ４０では、係数ベクトルＢ’が標準基底表現係数ベクトルＢに変換される。図５に示される基底変換は、図１に示されたものに類似しているが、異なる基底変換行列が用いられている。
【００９８】
双対表現を標準表現に変換する基底変換行列Ｄdsは基底変換行列Ｄsdの逆行列であり、式（４５）ないし式（４７）によって表される。
【数４８】
2004166274.tif 000050
【数４９】
2004166274.tif 000051
【数５０】
2004166274.tif 000052
【００９９】
式（４７）に示される［Ｄds］Lにおいて、各反対角線の「１」の数及び隣接する反対角線間の間隔は、基底変換行列Ｄsdの場合と同じである。基底変換行列Ｄdsの（ｋ（１）＋１）番目行で、反対角線はそれぞれ、（ｋ（２）−１）番目列、（ｋ（３）−１）番目列、（ｎ−１）番目列から始まっている。もしｋ（２）−ｋ（１）＝１であれば、最も短い反対角線は現れない。
【０１００】
標準表現から双対表現への基底変換と同様、双対表現から標準表現への基底変換は、式（４８）ないし式（５２）によって示される逐次計算によって行われる。
【数５１】
2004166274.tif 000053
【数５２】
2004166274.tif 000054
【０１０１】
式（４６）が式（４９）に適用されるとき、式（５０）が求められる。
【数５３】
2004166274.tif 000055
【０１０２】
ステップＳ３６〜Ｓ４０では、式（５１）を用いて標準基底表現係数ベクトルＢの（ｋ（１）＋１）番目ないし（ｎ−１）番目の成分が得られる。ここで［Ｄds］Lは、式（４７）に示されるものと同一である。
【数５４】
2004166274.tif 000056
【０１０３】
式（４７）に示されるように、［Ｄds］Lの行は、「１」が３個の行と、「１」が２個の行と、「１」が１個の行とに分類可能である。したがって、変換式（５０）の右辺を実行するステップは、項が３個であるステップＳ３６と、項が２個であるステップＳ３８と、項が１個であるステップＳ４０とに分類可能である。言い換えると、ステップＳ３４では標準基底表現係数ベクトルＢの０番目ないしｋ（１）番目の成分が得られ、ステップＳ３６では標準基底表現係数ベクトルＢの（ｋ（１）＋１）番目ないし（ｋ（１）＋ｎ−ｋ（３））番目の成分が得られ、ステップＳ３８では標準基底表現係数ベクトルＢの（ｋ（１）＋１＋ｎ−ｋ（３））番目ないし（ｋ（１）＋ｎ−ｋ（２））番目の成分が得られ、ステップＳ４０では標準基底表現係数ベクトルＢの（ｋ（１）＋１＋ｎ−ｋ（２））番目ないし（ｎ−１）番目の成分が得られる。したがって、ステップＳ３６〜Ｓ４０を行うことによって得られる基底変換の結果は式（５２）によって表される。
【数５５】
2004166274.tif 000057
【０１０４】
有限体ＧＦ（２13）の定義多項式が式（５３）によって表されるとき、基底変換行列は式（５４）及び式（５５）によって与えられ、変換式及び変換結果は式（５６）及び式（５７）によって表される。
【数５６】
2004166274.tif 000058
【数５７】
2004166274.tif 000059
【数５８】
2004166274.tif 000060
【数５９】
2004166274.tif 000061
【数６０】
2004166274.tif 000062
【０１０５】
双対表現を標準表現に変換する基底変換装置は、基本的に図２に示される装置を備えている。そして、図２に示される装置と同様の制御及び演算を行うが、トークン制御部１０から出力され、上位トークンレジスタ２０ａ及び下位トークンレジスタ２０ｂに格納されるデータ信号Ｄ＜０：ｎ−１＞は、図２に示される装置で用いられているものと異なっている。
【０１０６】
定義多項式がｘ13＋ｘ6＋ｘ4＋ｘ＋１であるとき、［Ｄds］Uの成分値に対応する上位トークンレジスタ２０ａには、第０クロックで初期値がセットされた後、各クロックでｋ（１）番目ビットとして０が入力される。上位トークンレジスタ２０ａは、各クロックで左側に１ビットずつシフトするように設計されている。第ｋ（１）クロックで、上位トークンレジスタ２０ａのｋ（１）番目ビットに１が入力される。例えばｋ（１）＝１であるとき、上位トークンレジスタ２０ａは第０クロックで（０  １）を出力し、第１クロックで（１  １）を出力する。
【０１０７】
［Ｄds］Lの成分に対応する下位トークンレジスタ２０ｂには、第（ｋ（１）＋１）クロックで初期値がセットされた後、第（ｋ（１）＋２）クロック以降の各クロックで第（ｎ−１）レジスタに０が入力される。下位トークンレジスタ２０ｂは、各クロックで左側に１ビットずつシフトするように設計されている。ｎ＝１３、ｋ（３）＝６、ｋ（２）＝４、ｋ（１）＝１であるとき、下位トークンレジスタ２０ｂは（ｎ−ｋ（１）−１＝１１）個のシフトレジスタからなり、１１個のシフトレジスタの初期値は（０  １  ０  １  ０  ０  ０  ０  ０  ０  １）である。格納された初期値は、各クロックで左側に１ビットずつシフトされる。初期値がシフトされた後、各クロックで第１２レジスタに０が入力される。それゆえ、シフトクロックが進行するにつれて上位トークンレジスタ２０ａ及び下位トークンレジスタ２０ｂは次のような値を有している。
【数６１】
2004166274.tif 000063
【０１０８】
一方で、基底変換行列の計算は、トークンレジスタ２０の出力及びデータレジスタ３０の出力間のビット乗算と、ビット乗算の結果の全てのビットの加算とによって行われる。基底変換行列Ｄsdの各行の成分Ｔ＜０：ｎ−１＞は、シフトクロックに応答するトークンレジスタ２０からの出力であり、ＡＮＤゲート部４０に備えられたｎ個のＡＮＤゲートによってそれぞれデータレジスタ３０からの出力ｂ＜０：ｎ−１＞と乗算される。ＡＮＤゲート部４０の出力は、ＸＯＲゲート５０によって加算される。ＸＯＲゲート５０の出力は、出力レジスタ６０によってクロックＣＫに同期されて出力される。
【０１０９】
本発明は前記実施形態に限定されず、特許請求の範囲によって定義された発明の要旨を
逸脱しない範囲でより多くの変形及び変用例が可能であることはもちろんである。
【産業上の利用可能性】
【０１１０】
本発明で提案した双対基底と標準基底との間の基底変換は、実際次のように使用できる。スマートカードのようにリソースの少ない携帯用端末機内で、電子署名などの機能を具現するためには、できるだけリソースの使用が少ないアルゴリズムが必要である。ゆえに、キー長の短いＥＣＣ（楕円曲線暗号システム）が有用である。電子署名時間、具現されたアルゴリズムの領域などＥＣＣの性能を左右するもののひとつが有限体乗算である。双対基底を使用して有限体積算を具現すれば、アルゴリズムの領域側面では有利であると知られている。しかし、ほとんどの通信プロトコルの場合において、標準基底が用いられている。したがって、双対基底を用いた積算装置と標準基底を用いたプロトコルとの互換のためには、基底変換が必要である。本発明は、このときに使用される効率的な基底変換方法を提案するものである。
【図面の簡単な説明】
【０１１１】
【図１】本発明に係る標準表現を双対表現に変換する基底変換方法の一実施形態を示すフローチャートである。
【図２】本発明に係る、図１の基底変換方法を行う基底変換装置の一実施形態を示す図である。
【図３】図３は、図２のトークンレジスタ２０の内部構造の一実施形態を示す図である。
【図４】図２のＡＮＤゲート、ＸＯＲゲート及び出力レジスタの構造の一実施形態を示す図である。
【図５】図５は、本発明に係る双対表現を標準表現に変換する基底変換方法の一実施形態を示すフローチャートである。
【符号の説明】
【０１１２】
１０    トークン制御部
２０    トークンレジスタ
２０ａ  上位トークンレジスタ
２０ｂ  下位トークンレジスタ
２１    マルチプレクサ
３０    データレジスタ
４０    ＡＮＤゲート部
６０    出力レジスタ
５０    ＸＯＲゲート
ＳＥＬ＜０：ｎ−２＞  マルチプレクサ２１の選択線
ＥＮu，ＥＮl    トークンレジスタ１０のシフト動作を起動させるイネーブル信号
Ｄ＜０：ｎ−１＞  トークンレジスタ２０に入力されるデータ
ＣＫ    レジスタのクロック
【図１】
2004166274.tif 000064
【図２】
2004166274.tif 000065
【図３】
2004166274.tif 000066
【図４】
2004166274.tif 000067
【図５】
2004166274.tif 000068