ガロア体上の元の除算演算回路
【課題】除数の制限がなく、標数Ｐと標数２の何れの除算演算処理も回路規模を増加させずに実現できるようにする。
【解決手段】シフトレジスタ１２に格納された被除数Ａの上位桁から順にシフトしていって、被除数Ａの上位５ビットを見る。レジスタ３０は、現在の最高次の値であり、これが「１」となった時に減算が実行される。レジスタ３０の値が「１」になると、論理積素子３２〜３８は、レジスタ１４〜２２からの除数Ｂの値を出力し、排他的論理和素子４０〜４６において減算が実行される。レジスタ３０の出力は、そのままシフトレジスタ４８に格納され、これが商となる。このような処理動作は、被除数Ａの全ビットが出力されるまで実行され、被除数Ａがｍビットであればｍクロックで動作を止める。その時のレジスタ２４〜３０の値が剰余となり、レジスタ３０の値が最上位桁（ＭＳＢ）となる。
【解決手段】シフトレジスタ１２に格納された被除数Ａの上位桁から順にシフトしていって、被除数Ａの上位５ビットを見る。レジスタ３０は、現在の最高次の値であり、これが「１」となった時に減算が実行される。レジスタ３０の値が「１」になると、論理積素子３２〜３８は、レジスタ１４〜２２からの除数Ｂの値を出力し、排他的論理和素子４０〜４６において減算が実行される。レジスタ３０の出力は、そのままシフトレジスタ４８に格納され、これが商となる。このような処理動作は、被除数Ａの全ビットが出力されるまで実行され、被除数Ａがｍビットであればｍクロックで動作を止める。その時のレジスタ２４〜３０の値が剰余となり、レジスタ３０の値が最上位桁（ＭＳＢ）となる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア体上の元の除算演算回路およびその演算回路を含む演算装置に係り、特に、符号・暗号回路等に用いられるガロア体上の元の除算演算回路およびその演算回路を含む演算装置に関する。
【背景技術】
【０００２】
近年、情報のディジタル化によって様々なサービスが提供され、快適な生活環境が整備されつつある。
例えば、インターネットの普及によって、我々はネットワークに接続された世界中のサーバが提供するサービスの恩恵を受けることができる。また、ディジタル携帯電話の普及によって、必要なときにすぐにコミュニケーションをとることが可能となり、通話以外の付加サービスを利用することができる。さらに、クレジットカードやプリペイトカードなどは、現金のやりとりによる煩わしさを解消してくれるという利点がある。
このような情報のディジタル化は、我々に利便性を提供してくれる反面、不正利用による被害を受け易いという問題を有する。例えば、盗聴によるプライバシーの侵害や個人情報の流出、複写・改ざん・なりすましによるシステムの不正利用などがそれである。そこで、これらの問題の解決策として、最近では暗号技術が注目されており、その中でもガロア体上の演算を利用した暗号技術の一つである楕円曲線暗号の研究開発が盛んに行われている。
この楕円曲線暗号は、楕円曲線上の離散対数問題に安全性の根拠を置く公開鍵暗号系であり、ＩＥＥＥ Ｐ１３６３で標準化の検討がなされている。
このように、従来の符号・暗号の分野では、ガロア体上の演算が利用されている。ガロア体ＧＦ（２m）は、２m個の元からなる集合であり、その表現方法としてベクトル表現がよく用いられる。上記のベクトル表現においては、ガロア体ＧＦ（２m）上の元ａはＧＦ（２）の元
を用いて、ｍ次元ベクトル
として表現する。ベクトル表現においては、元の表現はベクトル空間の基底によって決定される。
【０００３】
特に、多項式基底では、ＧＦ（２）上のｍ次既約多項式ｆを生成多項式とし、ｆの根である元αを用いて、
を基底とする。また、このとき、ガロア体ＧＦ（２m）上の元ａの多項式表現は、ｘを変数として、
となる。ガロア体ＧＦ（２m）上の元同士の演算は、上記多項式表現を用いると容易に理解することができる。
例えば、ＧＦ（２6）上の２つの元を
Ａ＝（１，０，０，１，１，１）
Ｂ＝（１，１，０，０，０，１）
とし、それらの加算式Ｃ＝Ａ＋Ｂは、多項式表現を用いると、
となる。即ち、
Ｃ＝（１＋１，０＋１，０＋０，１＋０，１＋０，１＋１）
＝（０，１，０，１，１，０）
である。ここに、＋はＧＦ（２）上の演算であるから、排他的論理和演算となる。
これと同様に、ＧＦ（２6）上の２つの元
Ａ＝（１，０，０，１，１，１）
Ｂ＝（１，１，０，０，０，１）
の減算式Ｃ＝Ａ−Ｂは、
Ｃ＝（１−１，０−１，０−０，１−０，１−０，１−１）＝（０，１，０，１，１，０）
である。ここに、−もＧＦ（２）上の演算であるから、排他的論理和演算となる。
また、ＧＦ（２6）上の２つの元の乗算式Ｄ＝Ａ・Ｂは、多項式表現を用いると、次式（１）のように計算することができる。
…………（１）
【０００４】
今、このガロア体ＧＦ（２6）の既約多項式を
Ｆ＝（１，０，１，０，１，０，１）
とする。すなわち、
である。この既約多項式によって、上記（１）式を５次以下の多項式へと変形する。即ち、Ｆ（ｘ）を０とおき、次式（２）のように６次以上の項に繰り返し適用して、５次以下にする。
…………（２）
まず、（１）式の最高次が１０次なので、（２）式にｘ4を乗じると、
となる。この式を（１）式の１０次の項に代入すると、
のようになり、この時点での最高次が９次なので、同様の計算を行う。これを繰り返して、５次以下にすると最終的な結果は、
となり、乗算結果のベクトル表現は、
Ｄ＝（１，０，０，１，１，１）
となる。
このように、乗算演算では、（１）式を（２）式の既約多項式Ｆで５次以下とする演算処理を行う際に、途中の演算結果の桁数を増やさない（次数を落とす）ための除算を行いその剰余を求めている点に着目し、本発明者らは除算演算を行う際にも同様の演算回路を利用することができないかを検討している。
また、従来の除算演算回路では、乗算と加算とを一定の条件に従って繰り返し演算処理することにより除算演算を行っていた。
さらに、通常のＣＰＵ等の演算回路には、一般的に用いられる除算演算回路（以下、標数Ｐの除算演算回路という）が内蔵されている。一方で、符号・暗号処理等を行う際には、上記したガロア体ＧＦ（２m）上のベクトルで表される２つの元の除算演算回路（以下、標数２の除算演算回路という）を必要とする場合があった。そこで、これら両者の除算演算処理を必要とする場合、従来はそれぞれ別個の演算回路を用意していた。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、このような従来の演算回路にあっては、上記した乗算演算において、（１）式を（２）式の既約多項式Ｆで５次以下にする処理は、除算を行いその剰余を求めているが、この除算は途中の演算結果の桁数を増やさない（次数を落とす）ための処理であり、除数が既約多項式に制限されてしまうことから、これまでの乗算回路をそのまま除算回路として転用するのは困難であるという問題があった。
また、従来の除算演算回路における除算演算は、乗算と加算とが一定の条件に従って繰り返し行われるため、計算量が膨大となり、計算時間が長くかかるという問題があった。
さらに、一般的に用いられる標数Ｐの除算演算回路と、符号・暗号処理等を行うための標数２の除算演算回路の両方が必要な場合は、従来はそれぞれ別個の演算回路を使用していたため、回路規模が増加し、コスト増になるという問題があった。
本発明は、上記課題に鑑みてなされたものであり、除数の制限がなく、演算速度が速い上、標数Ｐと標数２の両方の除算演算処理を行う場合であっても回路規模を増加させずに、低コストに実現することができるガロア体上の元の除算演算方法および除算演算回路を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の目的を達成するため、請求項１記載の発明は、ガロア体上のｍビットとｎビット（ｍ、ｎは共に自然数で、ｍ＞ｎ）のベクトルで表現される２つの元である被除数Ａ＝（ａ０，…，ａｍ−１）と除数Ｂ＝（ｂ０，…，ｂｎ−１）に対してＡ／Ｂを演算し、最大でｍビットで表現される商Ｃ＝（ｃ０，…，ｃｍ−１）と、最大でｎ−１ビットで表現される剰余Ｄ＝（ｄ０，…，ｄｎ−２）とを求めるためのガロア体上の元の除算演算回路であって、ｍビットから成る前記被除数Ａを格納し、上位ビットから順次出力する被除数格納出力手段と、ｎビットから成る前記除数Ｂを各桁毎に格納し、それぞれ個別に出力する除数格納出力手段と、各桁毎の演算データをそれぞれ格納し、その演算データを次桁へ出力する演算データ格納出力手段と、前記被除数格納出力手段から出力される被除数あるいは前記演算データ格納出力手段から出力される各桁の演算データを前記除数格納出力手段から出力される除数の値に基づいて、そのまま出力するか、一つ下の桁の出力を上位桁へ渡すかを選択して前記除数の有効桁数を検出する有効桁数検出手段と、前記有効桁数検出手段からの出力と、前記除数格納出力手段から出力される各桁の除数Ｂとの論理積をとって減算処理するか否かを選択する論理積手段と、前記論理積手段からの論理積出力と、前記被除数格納出力手段から出力される被除数あるいは前記演算データ格納出力手段から出力される演算データとの排他的論理和をとって減算処理を実行する排他的論理和手段と、前記有効桁数検出手段からの出力を順次入力して格納する演算結果格納手段と、を備え、前記被除数Ａの全ビットが出力されるまで演算処理を実行することにより、前記演算結果格納手段に前記商Ｃが格納され、前記演算データ格納出力手段に剰余Ｄが格納されるものである。
【発明の効果】
【０００７】
以上説明したように、請求項１記載のガロア体上の元の除算演算回路によれば、ガロア体上の元の除算および剰余算を除数Ｂのビット数に制限されることなく実現することができる。
【図面の簡単な説明】
【０００８】
【図１】本実施の形態１に係るガロア体上の元の除算演算回路の構成例を示す図である。
【図２】図１の除算演算回路による演算処理状態を示す図である。
【図３】図１の除算演算回路を用いて除算演算を行う場合の処理動作を説明する図である。
【図４】本実施の形態２に係るガロア体上の元の除算演算回路の構成例を示す図である。
【図５】除数のビット数の制限を受けない図４の除算演算回路による演算処理状態を示す図である。
【図６】図４の除算演算回路を用いて除算演算を行う場合の処理動作を説明する図である。
【図７】本実施の形態３に係る除算演算回路の構成例を示す図である。
【図８】（ａ）（ｂ）（ｃ）（ｄ）は、図７の除算演算用モジュールの内部構造を示す図である。
【図９】図８（ｃ）のボロー計算部への入力信号の組み合わせと出力信号との関係を一覧に示した図である。
【図１０】図７の除算演算回路による標数Ｐの演算処理過程を説明する図である。
【図１１】図７の除算演算回路による標数２の演算処理過程を説明する図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
（実施の形態１）
この実施の形態１は、本発明のガロア体ＧＦ（２m）上の元の除算を実現する除算演算回路を説明するものである。
図１は、本実施の形態１に係るガロア体上の元の除算演算回路１０の構成例を示す図である。この構成例では、除数を５ビットとし、最上位桁が常に１である必要がある。つまり、除数が４ビットや３ビットでは計算することのできない構成である。
図１に示す除算演算回路１０は、被除数格納出力手段としてのシフトレジスタ１２、除数格納出力手段としてのレジスタ１４〜２２、演算データ格納出力手段としてのレジスタ２４〜３０、論理積手段としての論理積素子３２〜３８、排他的論理和手段としての排他的論理和素子４０〜４６、演算結果格納手段としてのシフトレジスタ４８などにより構成されている。
シフトレジスタ１２には、被除数Ａが格納され、１クロック毎に上位桁から出力するものである。ここでは、一例として被除数Ａ＝（１，１，０，１，０，０，１，１，１）とすると、１，１，１，０，０，１，０，１，１の順に出力される。
レジスタ１４〜２２は、除数Ｂを格納するもので、レジスタ２２に最上位桁（ＭＳＢ）、そしてレジスタ２０、１８、１６…と順に格納してゆき、レジスタ１４に最下位桁（ＬＳＢ）を格納する。ここでは、一例として除数Ｂ＝（１，０，０，１，１）とすると、レジスタ１４〜２２には順に１，０，０，１，１が格納される。
レジスタ２４〜３０は、演算用のレジスタであって、レジスタ３０が最上位桁となる。レジスタ２４〜３０は、演算前に全て「０」にリセットされる。各レジスタ２４〜３０には、対応する桁のレジスタ１４〜２２からの除数Ｂと、レジスタ３０からの出力との論理積（論理積素子３２〜３８による）出力と、一つ下位の桁の出力（例えば、最下位桁のレジスタ２４にはシフトレジスタ１２からの出力）との排他的論理和（排他的論理和素子４０〜４６による）出力がそれぞれ入力される。
排他的論理和素子４０〜４６は、減算を実行する素子である。
論理積素子３２〜３８は、論理積を実行する素子であり、ここに入力されるレジスタ３０からの出力は、減算するかしないかの選択信号である。通常、この値は「０」（減算をしない）であり、演算用のレジスタ２４〜３０の値をそのまま次桁へシフトさせる。
以上のように、本実施の形態１の除算演算回路１０が構成されており、シフトレジスタ１２に格納された被除数Ａの上位桁から順にシフトしていって、被除数Ａの上位５桁を常に見ている。
【００１０】
レジスタ３０は、現在の最高次の値であり、これが「１」となった時に減算処理が実行される。レジスタ３０の値が「１」になると、論理積素子３２〜３８は、レジスタ１４〜２２からの除数Ｂの値を出力して、排他的論理和素子４０〜４６において減算が実行される。
また、レジスタ３０の出力は、そのままシフトレジスタ４８にも格納され、これが商となる。このような処理動作は、被除数Ａの全ビットが出力されるまで実行される。例えば、被除数Ａがｍビットであればｍクロックで動作を止めるようにする。そして、この時にレジスタ２４〜３０に格納されている値が剰余となり、レジスタ３０に格納されている値が最上位桁（ＭＳＢ）となる。
図２は、図１の除算演算回路１０による演算処理状態を示す図である。ここでは、被除数Ａ＝（１，１，０，１，０，０，１，１，１）、除数Ｂ＝（１，０，０，１，１）として、実際にＡ／Ｂを計算したものである。
ここでは、被除数Ａが９ビットであるため、図２に示すように、９クロック目まで演算処理が行われる。その結果、商が１０１１０となり、剰余が１１０１となる。
【００１１】
次に、その除算演算の処理動作を説明する。
図３は、図１の除算演算回路１０を用いて除算演算を行う場合の処理動作を説明する図である。
図３に示すように、被除数Ａ＝（１，１，０，１，０，０，１，１，１）が格納されたシフトレジスタ１２からレジスタ２４〜３０へ被除数Ａの最上位ビットから順にシフトさせて、４クロック目で上位４ビットを格納し、５ビット目がシフトレジスタ１２の最上位桁に位置する状態として、除数Ｂと同じ５ビット（ｎビット）数分だけ被除数Ａから抽出して、これを演算対象Ａ´とする。
ここで、レジスタ３０に格納された演算対象Ａ´の最上位ビットの「１」を商ｃ４＝１とする。
このように、演算対象Ａ´の最上位ビットが「１」であれば、演算対象Ａ´から除数Ｂを減算し、それを減算結果Ａ″として抽出する。
その減算結果Ａ″の最上位ビットが「０」ならば、その最上位ビットを除く４ビット（ｎ−１ビット）列を抽出すると共に、その４ビット列に被除数Ａのａ３の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その最上位ビットの「０」を商ｃ３＝０とする。
上記と同様の手順に従い、演算対象Ａ´の最上位ビットが「０」であるので、最上位ビットを除く４ビット列を抽出し、その４ビット列に被除数Ａのａ２の「０」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その最上位ビットの「１」を商ｃ２＝１とする。
この新たな演算対象Ａ´は、最上位ビットが「１」であるので除数Ｂを減算し、それを減算結果Ａ″として抽出する。
その減算結果Ａ″の最上位ビットが「０」であるので、最上位ビットを除く４ビット列を抽出し、被除数Ａのａ１の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出し、その最上位ビットの「１」を商ｃ１＝１とする。
新たな演算対象Ａ´は、最上位ビットが「１」であるので除数Ｂを減算し、それを減算結果Ａ″として抽出する。
減算結果Ａ″の最上位ビットが「０」であるので、最上位ビットを除く４ビット列を抽出し、被除数Ａのａ０の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その最上位ビットの「０」を商ｃ０＝０とする。
このときの新たな演算対象Ａ´の最上位ビットを除く４ビット列が剰余Ｄとなる。
その結果、商Ｃは、「１０１１０」となり、剰余Ｄが「１１０１」となる。
以上説明したように、本実施の形態１によれば、除数が既約多項式のみに制限されることなく、迅速にガロア体上の元の除算演算を行うことができる。
【００１２】
（実施の形態２）
本実施の形態２は、ガロア体ＧＦ（２m）上の除数のビット数が制限されない除算を実現するものである。
図４は、本実施の形態２に係るガロア体上の元の除算演算回路５０の構成例を示す図である。この構成例では、除数の最大ビット数を５ビットとする。つまり、除数としては１〜５ビットまでを使用することができる。
図４に示す除算演算回路５０は、被除数格納出力手段としてのシフトレジスタ５２、除数格納出力手段としてのレジスタ５４〜６２、演算データ格納出力手段としてのレジスタ６４〜７０、論理積手段としての論理積素子７２〜７８、排他的論理和手段としての排他的論理和素子８０〜８６、有効桁数検出手段としてのセレクタ８８〜９６、演算結果格納手段としてのシフトレジスタ９８などにより構成されている。
シフトレジスタ５２には、被除数Ａが格納され、１クロック毎に上位桁から出力するものである。ここでは、一例として被除数Ａ＝（１，１，０，１，０，０，１，１，１）とすると、１，１，１，０，０，１，０，１，１の順に出力される。
レジスタ５４〜６２は、除数Ｂを格納するもので、レジスタ６２に最上位桁（ＭＳＢ）、そしてレジスタ６０、５８、５６…と順に格納してゆき、レジスタ５４に最下位桁（ＬＳＢ）を格納する。ここでは、一例として５ビットの除数Ｂ＝（１，０，１，０，０）とすると、レジスタ５４〜６２には順に１，０，１，０，０が格納される。
レジスタ６４〜７０は、演算用のレジスタであって、レジスタ７０が最上位桁となる。レジスタ６４〜７０は、演算前に全て「０」にリセットされる。各レジスタ６４〜７０には、対応する桁のレジスタ５４〜６２からの除数Ｂと、セレクタ９６からの出力信号１００との論理積（論理積素子７２〜７８による）出力と、一つ下位の桁の出力（例えば、最下位桁のレジスタ６４にはシフトレジスタ５２からの出力）との排他的論理和（排他的論理和素子８０〜８６による）出力が入力される。
【００１３】
排他的論理和素子８０〜８６は、減算を実行する素子である。
論理積素子７２〜７８は、論理積を実行する素子であり、ここに入力されるセレクタ９６からの出力信号１００は、減算するかしないかの選択信号である。この選択信号は、レジスタ５４〜６２からの除数Ｂと、シフトレジスタ５２からの出力、およびレジスタ６４〜７０の各出力と、セレクタ８８〜９６とによって制御される。
この各セレクタ８８〜９６を制御する制御信号は、レジスタ５４〜６２から出力される除数Ｂのそれぞれの値である。この制御信号の値が「１」の時は、その次数に対応する演算用のレジスタ６４〜７０の出力がそのままセレクタ出力となり、制御信号の値が「０」の時は、一つ下の次数のセレクタ出力を上位次数のセレクタへ渡すようにする。
最終的な出力信号１００は、除数Ｂの値が「１」である次数の中で最高次のセレクタ９６の出力となる。これにより、除数Ｂの有効ビット数を検出している。本実施の形態２では、除数Ｂ＝（１，０，１，０，０）であるので、レジスタ５８からセレクタ９２に除数Ｂの最高次の「１」が出力されて、レジスタ６６の出力が出力信号１００となる。また、例えば、除数Ｂ＝（１，０，０，１，１）の場合は、レジスタ７０の出力が出力信号１００となる。
通常、出力信号１００の値は「０」である（図５の１クロック目参照）。すなわち、減算をせずに演算用のレジスタ６４〜７０をそのままシフトさせる。このようにして、被除数Ａの上位桁から順にシフトしていって、有効ビットの次の値が「１」となった時に減算が実行される。
また、出力信号１００の値が「１」になった場合は（図５の２〜３クロック目参照）、論理積素子７２〜７８がレジスタ５４〜６０からの除数Ｂの値を出力し、排他的論理和素子８０〜８６において減算が実行される。
そして、出力信号１００は、そのままシフトレジスタ９８にも格納され、これが商Ｃとなる。このような処理動作は、被除数Ａの全ビットが出力されるまで行われる。すなわち、被除数Ａがｍビットであれば、ｍクロックで処理動作を止め、この時のレジスタ６４〜７０に格納されている値が剰余Ｄとなる。その時のレジスタ７０の値が最上位桁（ＭＳＢ）である。
また、図５は、除数のビット数の制限を受けない図４の除算演算回路５０による演算処理状態を示す図である。ここでは、除数Ｂ＝（１，０，１，０，０）が３ビットであっても、除算演算回路５０でＡ／Ｂを計算することにより、商が１１０１０００となり、剰余Ｄが１１となる。
【００１４】
次に、その除算演算の処理動作を説明する。
図６は、図４の除算演算回路５０を用いて除算演算を行う場合の処理動作を説明する図である。
図６に示すように、被除数Ａ＝（１，１，０，１，０，０，１，１，１）がシフトレジスタ５２に格納され、その上位のレジスタ６４〜７０に４（ｎ−１）ビット分の「０」を置いて、これを被除数Ａとし、その被除数Ａの上位５（ｎ）ビット列「１００００」を演算対象Ａ´として抽出する。ここで、除数Ｂ＝（１，０，１，０，０）であるので、０次から「１」の値を持つ次数の中で最高次までの有効ビット数をｔとすると、ｔ＝３となる。このため、上記した演算対象Ａ´「１００００」の３ビット目の「０」が商ｃ８＝０となる。
この演算対象Ａ´の３ビット目が「０」であれば、演算対象Ａ´の最上位ビットを除く４ビット（ｎ−１ビット）列を抽出すると共に、その４ビット列に被除数Ａのａ７の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「０」を商ｃ７＝０とする。
同様に演算対象Ａ´の３ビット目が「０」であるので、その演算対象Ａ´の最上位ビットを除く４ビット列を抽出すると共に、その４ビット列に被除数Ａのａ６の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「１」を商ｃ６＝１とする
新たな演算対象Ａ´の３ビット目が「１」ならば、除数Ｂを減算して、その減算結果Ａ″として抽出し、その減算結果Ａ″の最上位ビットを除く４（ｎ−１）ビット列を抽出し、被除数Ａのａ５の「０」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出する。そして、この新たな演算対象Ａ´の３ビット目の「１」を商ｃ５＝１とする。
この新たな演算対象Ａ´の３ビット目は、「１」であるので除数Ｂを減算し、それを新たな減算結果Ａ″として抽出し、その減算結果Ａ″の最上位ビットを除く４ビット列を抽出して、被除数Ａのａ４の「０」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出する。そして、この新たな演算対象Ａ´の３ビット目の「０」を商ｃ４＝０とする。
【００１５】
新たな演算対象Ａ´の３ビット目は、「０」であるので、その演算対象Ａ´の最上位ビットを除く４ビット列を抽出すると共に、被除数Ａのａ３の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「１」を商ｃ３＝１とする
この新たな演算対象Ａ´の３ビット目が「１」であるので除数Ｂを減算し、それを新たな減算結果Ａ″として抽出し、減算結果Ａ″の最上位ビットを除く４ビット列を抽出して、被除数Ａのａ２の「０」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出する。そして、この新たな演算対象Ａ´の３ビット目の「０」を商ｃ２＝０とする。
新たな演算対象Ａ´の３ビット目は、「０」であるので、その演算対象Ａ´の最上位ビットを除く４ビット列を抽出すると共に、被除数Ａのａ１の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「０」を商ｃ１＝０とする。
同様に、新たな演算対象Ａ´の３ビット目が「０」であるので、その演算対象Ａ´の最上位ビットを除く４ビット列を抽出すると共に、被除数Ａのａ０の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「０」を商ｃ０＝０とする。
この商Ｃのｃ０までを求めた時の新たな演算対象Ａ´の最上位ビットを除いた４（ｎ−１）ビット列が剰余Ｄとなる。
このように、本実施の形態２では、被除数Ａ＝（１，１，０，１，０，０，１，１，１）とし、除数Ｂ＝（１，０，１，０，０）として、図４の除算演算回路５０により実際にＡ／Ｂを計算すると、その時の商Ｃが「０００１０１１」となり、その剰余Ｄを「１１」と求めることができる。
以上説明したように、本実施の形態２によれば、ガロア体上の元の除算および剰余算を除数Ｂのビット制限なく実現することができる。
【００１６】
（実施の形態３）
本実施の形態３は、ガロア体ＧＦ（２m）上ベクトルで表わされる２つの元の除算演算（標数２の除算）と、一般的に用いられる除算演算（標数Ｐの演算）のどちらの除算演算をも可能とする除算演算回路を実現するものである。
図７は、本実施の形態３に係る除算演算回路１１０の構成例を示す図である。この構成例では、除数の最大ビット数を４ビットとする。つまり、除数としては１〜４ビットまでを使用することができる。
図７に示す除算演算回路１１０は、シフトレジスタ１１２、レジスタ１１４〜１２０、除算演算用モジュール１２２〜１３０、レジスタ１３２〜１３８、インバータ１４０、セレクタ１４２、シフトレジスタ１４４などにより構成されている。
シフトレジスタ１１２には、被除数Ａが格納され、１クロック毎に上位桁から出力するものである。
レジスタ１１４〜１２０は、除数Ｂを格納するもので、レジスタ１２０に最上位桁（ＭＳＢ）、そしてレジスタ１１８、１１６…と順に格納してゆき、レジスタ１１４に最下位桁（ＬＳＢ）を格納する。
今、ここでは一例として標数Ｐにおいて７５÷１２を計算しようとすると、被除数７５の２進表現１００１０１１がシフトレジスタ１１２に格納され、１，１，０，１，０，０，１の順に出力されて、除数１２の２進表現１１００がレジスタ１１４〜１２０に順番に０，０，１，１と格納される。
同様に標数２においても、ベクトルで表現されるガロア体上の２つの元、被除数Ａ＝（１，１，０，１，０，１，０，０，１）、除数Ｂ＝（１，０，１，１）の除算演算時には、シフトレジスタ１１２に被除数Ａが格納され、１，０，０，１，０，１，０，１，１の順に出力されて、レジスタ１１４〜１２０に除数Ｂが順番に１，０，１，１と格納される。
レジスタ１３２〜１３８は、演算用のレジスタであり、レジスタ１３８が最上位桁となり、演算前に全て「０」にリセットされる。
【００１７】
除算演算用モジュール１２２〜１３０は、除算演算用の回路をモジュール化したものである。図８（ａ）は、図７の除算演算用モジュールを示す図であり、（ｂ）は、除算演算用モジュール内の演算部の構造を示す図であり、（ｃ）は、標数Ｐ用のボロー計算部の構造を示す図であり、（ｄ）は、標数２用の演算制御部を示す図である。
図８（ａ）に示した除算演算用モジュール１２２（１２４〜１３０も同様）の左側のＡ〜Ｆは、入力信号であり、右側のＬ〜Ｎは出力信号である。その除算演算用モジュール１２２の内部は、図８（ｂ）〜（ｄ）に示すように、３つのブロックにそれぞれ分かれている。
図８（ｂ）は、除算演算の為の演算（減算）を行う演算部である。入力信号Ｆは、減算処理を実行するか否かの実行／非実行の選択信号であり、「１」で実行、「０」で非実行となる。この減算非実行時は、前段のレジスタからの入力信号Ａがそのままセレクタ１５４を通って出力される（出力信号Ｌ）。また、減算実行時には、入力信号Ａ、除数Ｂの対応桁の値、前段からのボロー信号の３つの値がエクスクル−シブオアゲート１５２により排他的論理和演算がなされ、セレクタ１５４を通って出力される。但し、標数２の演算時には、ボロー信号は不要となるので、標数Ｐ／標数２の選択信号Ｅ（「１」で標数Ｐを選択、「０」で標数２を選択）によって、アンドゲート１５０の出力がエクスクル−シブオアゲート１５２に入力され、マスクされる。そして、レジスタ１３２〜１３８の入力には、この演算部の出力信号Ｌが入力される。
図８（ｃ）は、標数Ｐ用の演算制御部であるボロー計算部であり、前段の除算演算用モジュールの標数Ｐ用のボロー計算部の出力信号Ｍがボロー信号Ｃとして入力される。このボロー信号Ｃと除数Ｂの対応桁の値がオアゲート１５８に入力され、その出力信号と前段からのレジスタからの入力信号Ａの反転信号がアンドゲート１６０に入力される。また、ボロー信号Ｃと除数Ｂの対応桁の値をアンドゲート１５６に入力し、その出力信号と前記アンドゲート１６０の出力信号とをオアゲート１６２に入力し、その出力信号Ｍが次段の除算演算用モジュール等に出力される。この図８（ｃ）のボロー計算部へのＡ、Ｂ、Ｃの入力信号の組み合わせと、出力信号Ｍとの関係を一覧に示したのが図９である。
図８（ｄ）は、標数２用の演算制御部であり、セレクタ１６４を備えている。このセレクタ１６４に入力される入力信号Ｂは、除数Ｂに対応する桁の値であり、これが「１」の時は前段レジスタの出力Ａを出力し、「０」の時は標数２の制御信号Ｄを出力する。前段の標数２用の演算制御部の出力信号Ｎは、次段の標数２の制御信号Ｄとして入力される。
【００１８】
標数Ｐ／標数２のそれぞれの場合において、演算制御部の最終段の出力（標数Ｐの場合はＭ、標数２の場合はＮ、但し、標数ＰはＭの論理反転出力）が減算処理を実行するか否かを選択する減算実行／非実行選択信号となる。信号１４６の標数Ｐ／標数２の選択信号によって実行する除算演算が選択され、これに対応する減算実行／非実行選択信号が信号１４８となり、各除算演算用モジュール１２２〜１３０のＦ端子へ入力される。
通常、信号１４８の値は「０」、すなわち、減算処理をせずに演算用のレジスタ１３２〜１３８をそのままシフトさせる。このようにして、シフトレジスタ１１２に格納されている被除数Ａの上位桁から順にシフトしていき、信号１４８の減算実行／非実行選択信号が「１」となった時に減算処理が実行される。信号１４８の出力は、そのままシフトレジスタ１４４に格納され、これが商となる。
上記の動作をシフトレジスタ１１２の被除数Ａの全ビットが出力されるまで、すなわち、被除数Ａがｍビットであればｍクロックで動作を止めるようにする。また、この時のレジスタ１３２〜１３８の値が剰余となり、そのうちのレジスタ１３８の値が最高位桁（ＭＳＢ）となる。
図１０は、図７の除算演算回路１１０による標数Ｐの演算処理過程を説明する図である。図１０に示されるように、標数Ｐにおける７５÷＋９を実際に計算すると、商が８（２進数表現で１０００）、剰余が３（２進表現で１１）と求めることができる。
また、図１１は、図７の除算演算回路１１０による標数２の演算処理過程を説明する図であり、被除数Ａ＝（１，１，０，１，０，１，０，０，１）、除数Ｂ＝（１，０，１，１）の場合であって、Ａ／Ｂを実際に計算すると、商が１０１０１０、剰余が１０１というように求めることができる。
以上説明したように、本実施の形態３によれば、標数Ｐと標数２のどちらの場合の除算演算であっても、それぞれ別に回路を設けることなく、低コストの除算演算回路を実現することができる。
【符号の説明】
【００１９】
１０ 除算演算回路、１２ シフトレジスタ、１４〜２２ レジスタ、２４〜３０ レジスタ、３２〜３８ 論理積素子、４０〜４６ 排他的論理和素子、４８ シフトレジスタ、５０ 除算演算回路、５２ シフトレジスタ、５４〜６２ レジスタ、６４〜７０ レジスタ、７２〜７８ 論理積素子、８０〜８６ 排他的論理和素子、８８〜９６ セレクタ８８〜９６、９８ シフトレジスタ、１１０ 除算演算回路、１１２ シフトレジスタ、１１４〜１２０ レジスタ、１２２〜１３０ 除算演算用モジュール、１３２〜１３８ レジスタ、１４０ インバータ、１４２ セレクタ、１４４ シフトレジスタ、１４６、１４８ 信号、１５０ アンドゲート、１５２ エクスクル−シブオアゲート、１５４ セレクタ、１５６ アンドゲート、１５８ オアゲート、１６０ アンドゲート、１６２ オアゲート、１６４ セレクタ
【技術分野】
【０００１】
本発明は、ガロア体上の元の除算演算回路およびその演算回路を含む演算装置に係り、特に、符号・暗号回路等に用いられるガロア体上の元の除算演算回路およびその演算回路を含む演算装置に関する。
【背景技術】
【０００２】
近年、情報のディジタル化によって様々なサービスが提供され、快適な生活環境が整備されつつある。
例えば、インターネットの普及によって、我々はネットワークに接続された世界中のサーバが提供するサービスの恩恵を受けることができる。また、ディジタル携帯電話の普及によって、必要なときにすぐにコミュニケーションをとることが可能となり、通話以外の付加サービスを利用することができる。さらに、クレジットカードやプリペイトカードなどは、現金のやりとりによる煩わしさを解消してくれるという利点がある。
このような情報のディジタル化は、我々に利便性を提供してくれる反面、不正利用による被害を受け易いという問題を有する。例えば、盗聴によるプライバシーの侵害や個人情報の流出、複写・改ざん・なりすましによるシステムの不正利用などがそれである。そこで、これらの問題の解決策として、最近では暗号技術が注目されており、その中でもガロア体上の演算を利用した暗号技術の一つである楕円曲線暗号の研究開発が盛んに行われている。
この楕円曲線暗号は、楕円曲線上の離散対数問題に安全性の根拠を置く公開鍵暗号系であり、ＩＥＥＥ Ｐ１３６３で標準化の検討がなされている。
このように、従来の符号・暗号の分野では、ガロア体上の演算が利用されている。ガロア体ＧＦ（２m）は、２m個の元からなる集合であり、その表現方法としてベクトル表現がよく用いられる。上記のベクトル表現においては、ガロア体ＧＦ（２m）上の元ａはＧＦ（２）の元
を用いて、ｍ次元ベクトル
として表現する。ベクトル表現においては、元の表現はベクトル空間の基底によって決定される。
【０００３】
特に、多項式基底では、ＧＦ（２）上のｍ次既約多項式ｆを生成多項式とし、ｆの根である元αを用いて、
を基底とする。また、このとき、ガロア体ＧＦ（２m）上の元ａの多項式表現は、ｘを変数として、
となる。ガロア体ＧＦ（２m）上の元同士の演算は、上記多項式表現を用いると容易に理解することができる。
例えば、ＧＦ（２6）上の２つの元を
Ａ＝（１，０，０，１，１，１）
Ｂ＝（１，１，０，０，０，１）
とし、それらの加算式Ｃ＝Ａ＋Ｂは、多項式表現を用いると、
となる。即ち、
Ｃ＝（１＋１，０＋１，０＋０，１＋０，１＋０，１＋１）
＝（０，１，０，１，１，０）
である。ここに、＋はＧＦ（２）上の演算であるから、排他的論理和演算となる。
これと同様に、ＧＦ（２6）上の２つの元
Ａ＝（１，０，０，１，１，１）
Ｂ＝（１，１，０，０，０，１）
の減算式Ｃ＝Ａ−Ｂは、
Ｃ＝（１−１，０−１，０−０，１−０，１−０，１−１）＝（０，１，０，１，１，０）
である。ここに、−もＧＦ（２）上の演算であるから、排他的論理和演算となる。
また、ＧＦ（２6）上の２つの元の乗算式Ｄ＝Ａ・Ｂは、多項式表現を用いると、次式（１）のように計算することができる。
…………（１）
【０００４】
今、このガロア体ＧＦ（２6）の既約多項式を
Ｆ＝（１，０，１，０，１，０，１）
とする。すなわち、
である。この既約多項式によって、上記（１）式を５次以下の多項式へと変形する。即ち、Ｆ（ｘ）を０とおき、次式（２）のように６次以上の項に繰り返し適用して、５次以下にする。
…………（２）
まず、（１）式の最高次が１０次なので、（２）式にｘ4を乗じると、
となる。この式を（１）式の１０次の項に代入すると、
のようになり、この時点での最高次が９次なので、同様の計算を行う。これを繰り返して、５次以下にすると最終的な結果は、
となり、乗算結果のベクトル表現は、
Ｄ＝（１，０，０，１，１，１）
となる。
このように、乗算演算では、（１）式を（２）式の既約多項式Ｆで５次以下とする演算処理を行う際に、途中の演算結果の桁数を増やさない（次数を落とす）ための除算を行いその剰余を求めている点に着目し、本発明者らは除算演算を行う際にも同様の演算回路を利用することができないかを検討している。
また、従来の除算演算回路では、乗算と加算とを一定の条件に従って繰り返し演算処理することにより除算演算を行っていた。
さらに、通常のＣＰＵ等の演算回路には、一般的に用いられる除算演算回路（以下、標数Ｐの除算演算回路という）が内蔵されている。一方で、符号・暗号処理等を行う際には、上記したガロア体ＧＦ（２m）上のベクトルで表される２つの元の除算演算回路（以下、標数２の除算演算回路という）を必要とする場合があった。そこで、これら両者の除算演算処理を必要とする場合、従来はそれぞれ別個の演算回路を用意していた。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、このような従来の演算回路にあっては、上記した乗算演算において、（１）式を（２）式の既約多項式Ｆで５次以下にする処理は、除算を行いその剰余を求めているが、この除算は途中の演算結果の桁数を増やさない（次数を落とす）ための処理であり、除数が既約多項式に制限されてしまうことから、これまでの乗算回路をそのまま除算回路として転用するのは困難であるという問題があった。
また、従来の除算演算回路における除算演算は、乗算と加算とが一定の条件に従って繰り返し行われるため、計算量が膨大となり、計算時間が長くかかるという問題があった。
さらに、一般的に用いられる標数Ｐの除算演算回路と、符号・暗号処理等を行うための標数２の除算演算回路の両方が必要な場合は、従来はそれぞれ別個の演算回路を使用していたため、回路規模が増加し、コスト増になるという問題があった。
本発明は、上記課題に鑑みてなされたものであり、除数の制限がなく、演算速度が速い上、標数Ｐと標数２の両方の除算演算処理を行う場合であっても回路規模を増加させずに、低コストに実現することができるガロア体上の元の除算演算方法および除算演算回路を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の目的を達成するため、請求項１記載の発明は、ガロア体上のｍビットとｎビット（ｍ、ｎは共に自然数で、ｍ＞ｎ）のベクトルで表現される２つの元である被除数Ａ＝（ａ０，…，ａｍ−１）と除数Ｂ＝（ｂ０，…，ｂｎ−１）に対してＡ／Ｂを演算し、最大でｍビットで表現される商Ｃ＝（ｃ０，…，ｃｍ−１）と、最大でｎ−１ビットで表現される剰余Ｄ＝（ｄ０，…，ｄｎ−２）とを求めるためのガロア体上の元の除算演算回路であって、ｍビットから成る前記被除数Ａを格納し、上位ビットから順次出力する被除数格納出力手段と、ｎビットから成る前記除数Ｂを各桁毎に格納し、それぞれ個別に出力する除数格納出力手段と、各桁毎の演算データをそれぞれ格納し、その演算データを次桁へ出力する演算データ格納出力手段と、前記被除数格納出力手段から出力される被除数あるいは前記演算データ格納出力手段から出力される各桁の演算データを前記除数格納出力手段から出力される除数の値に基づいて、そのまま出力するか、一つ下の桁の出力を上位桁へ渡すかを選択して前記除数の有効桁数を検出する有効桁数検出手段と、前記有効桁数検出手段からの出力と、前記除数格納出力手段から出力される各桁の除数Ｂとの論理積をとって減算処理するか否かを選択する論理積手段と、前記論理積手段からの論理積出力と、前記被除数格納出力手段から出力される被除数あるいは前記演算データ格納出力手段から出力される演算データとの排他的論理和をとって減算処理を実行する排他的論理和手段と、前記有効桁数検出手段からの出力を順次入力して格納する演算結果格納手段と、を備え、前記被除数Ａの全ビットが出力されるまで演算処理を実行することにより、前記演算結果格納手段に前記商Ｃが格納され、前記演算データ格納出力手段に剰余Ｄが格納されるものである。
【発明の効果】
【０００７】
以上説明したように、請求項１記載のガロア体上の元の除算演算回路によれば、ガロア体上の元の除算および剰余算を除数Ｂのビット数に制限されることなく実現することができる。
【図面の簡単な説明】
【０００８】
【図１】本実施の形態１に係るガロア体上の元の除算演算回路の構成例を示す図である。
【図２】図１の除算演算回路による演算処理状態を示す図である。
【図３】図１の除算演算回路を用いて除算演算を行う場合の処理動作を説明する図である。
【図４】本実施の形態２に係るガロア体上の元の除算演算回路の構成例を示す図である。
【図５】除数のビット数の制限を受けない図４の除算演算回路による演算処理状態を示す図である。
【図６】図４の除算演算回路を用いて除算演算を行う場合の処理動作を説明する図である。
【図７】本実施の形態３に係る除算演算回路の構成例を示す図である。
【図８】（ａ）（ｂ）（ｃ）（ｄ）は、図７の除算演算用モジュールの内部構造を示す図である。
【図９】図８（ｃ）のボロー計算部への入力信号の組み合わせと出力信号との関係を一覧に示した図である。
【図１０】図７の除算演算回路による標数Ｐの演算処理過程を説明する図である。
【図１１】図７の除算演算回路による標数２の演算処理過程を説明する図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
（実施の形態１）
この実施の形態１は、本発明のガロア体ＧＦ（２m）上の元の除算を実現する除算演算回路を説明するものである。
図１は、本実施の形態１に係るガロア体上の元の除算演算回路１０の構成例を示す図である。この構成例では、除数を５ビットとし、最上位桁が常に１である必要がある。つまり、除数が４ビットや３ビットでは計算することのできない構成である。
図１に示す除算演算回路１０は、被除数格納出力手段としてのシフトレジスタ１２、除数格納出力手段としてのレジスタ１４〜２２、演算データ格納出力手段としてのレジスタ２４〜３０、論理積手段としての論理積素子３２〜３８、排他的論理和手段としての排他的論理和素子４０〜４６、演算結果格納手段としてのシフトレジスタ４８などにより構成されている。
シフトレジスタ１２には、被除数Ａが格納され、１クロック毎に上位桁から出力するものである。ここでは、一例として被除数Ａ＝（１，１，０，１，０，０，１，１，１）とすると、１，１，１，０，０，１，０，１，１の順に出力される。
レジスタ１４〜２２は、除数Ｂを格納するもので、レジスタ２２に最上位桁（ＭＳＢ）、そしてレジスタ２０、１８、１６…と順に格納してゆき、レジスタ１４に最下位桁（ＬＳＢ）を格納する。ここでは、一例として除数Ｂ＝（１，０，０，１，１）とすると、レジスタ１４〜２２には順に１，０，０，１，１が格納される。
レジスタ２４〜３０は、演算用のレジスタであって、レジスタ３０が最上位桁となる。レジスタ２４〜３０は、演算前に全て「０」にリセットされる。各レジスタ２４〜３０には、対応する桁のレジスタ１４〜２２からの除数Ｂと、レジスタ３０からの出力との論理積（論理積素子３２〜３８による）出力と、一つ下位の桁の出力（例えば、最下位桁のレジスタ２４にはシフトレジスタ１２からの出力）との排他的論理和（排他的論理和素子４０〜４６による）出力がそれぞれ入力される。
排他的論理和素子４０〜４６は、減算を実行する素子である。
論理積素子３２〜３８は、論理積を実行する素子であり、ここに入力されるレジスタ３０からの出力は、減算するかしないかの選択信号である。通常、この値は「０」（減算をしない）であり、演算用のレジスタ２４〜３０の値をそのまま次桁へシフトさせる。
以上のように、本実施の形態１の除算演算回路１０が構成されており、シフトレジスタ１２に格納された被除数Ａの上位桁から順にシフトしていって、被除数Ａの上位５桁を常に見ている。
【００１０】
レジスタ３０は、現在の最高次の値であり、これが「１」となった時に減算処理が実行される。レジスタ３０の値が「１」になると、論理積素子３２〜３８は、レジスタ１４〜２２からの除数Ｂの値を出力して、排他的論理和素子４０〜４６において減算が実行される。
また、レジスタ３０の出力は、そのままシフトレジスタ４８にも格納され、これが商となる。このような処理動作は、被除数Ａの全ビットが出力されるまで実行される。例えば、被除数Ａがｍビットであればｍクロックで動作を止めるようにする。そして、この時にレジスタ２４〜３０に格納されている値が剰余となり、レジスタ３０に格納されている値が最上位桁（ＭＳＢ）となる。
図２は、図１の除算演算回路１０による演算処理状態を示す図である。ここでは、被除数Ａ＝（１，１，０，１，０，０，１，１，１）、除数Ｂ＝（１，０，０，１，１）として、実際にＡ／Ｂを計算したものである。
ここでは、被除数Ａが９ビットであるため、図２に示すように、９クロック目まで演算処理が行われる。その結果、商が１０１１０となり、剰余が１１０１となる。
【００１１】
次に、その除算演算の処理動作を説明する。
図３は、図１の除算演算回路１０を用いて除算演算を行う場合の処理動作を説明する図である。
図３に示すように、被除数Ａ＝（１，１，０，１，０，０，１，１，１）が格納されたシフトレジスタ１２からレジスタ２４〜３０へ被除数Ａの最上位ビットから順にシフトさせて、４クロック目で上位４ビットを格納し、５ビット目がシフトレジスタ１２の最上位桁に位置する状態として、除数Ｂと同じ５ビット（ｎビット）数分だけ被除数Ａから抽出して、これを演算対象Ａ´とする。
ここで、レジスタ３０に格納された演算対象Ａ´の最上位ビットの「１」を商ｃ４＝１とする。
このように、演算対象Ａ´の最上位ビットが「１」であれば、演算対象Ａ´から除数Ｂを減算し、それを減算結果Ａ″として抽出する。
その減算結果Ａ″の最上位ビットが「０」ならば、その最上位ビットを除く４ビット（ｎ−１ビット）列を抽出すると共に、その４ビット列に被除数Ａのａ３の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その最上位ビットの「０」を商ｃ３＝０とする。
上記と同様の手順に従い、演算対象Ａ´の最上位ビットが「０」であるので、最上位ビットを除く４ビット列を抽出し、その４ビット列に被除数Ａのａ２の「０」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その最上位ビットの「１」を商ｃ２＝１とする。
この新たな演算対象Ａ´は、最上位ビットが「１」であるので除数Ｂを減算し、それを減算結果Ａ″として抽出する。
その減算結果Ａ″の最上位ビットが「０」であるので、最上位ビットを除く４ビット列を抽出し、被除数Ａのａ１の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出し、その最上位ビットの「１」を商ｃ１＝１とする。
新たな演算対象Ａ´は、最上位ビットが「１」であるので除数Ｂを減算し、それを減算結果Ａ″として抽出する。
減算結果Ａ″の最上位ビットが「０」であるので、最上位ビットを除く４ビット列を抽出し、被除数Ａのａ０の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その最上位ビットの「０」を商ｃ０＝０とする。
このときの新たな演算対象Ａ´の最上位ビットを除く４ビット列が剰余Ｄとなる。
その結果、商Ｃは、「１０１１０」となり、剰余Ｄが「１１０１」となる。
以上説明したように、本実施の形態１によれば、除数が既約多項式のみに制限されることなく、迅速にガロア体上の元の除算演算を行うことができる。
【００１２】
（実施の形態２）
本実施の形態２は、ガロア体ＧＦ（２m）上の除数のビット数が制限されない除算を実現するものである。
図４は、本実施の形態２に係るガロア体上の元の除算演算回路５０の構成例を示す図である。この構成例では、除数の最大ビット数を５ビットとする。つまり、除数としては１〜５ビットまでを使用することができる。
図４に示す除算演算回路５０は、被除数格納出力手段としてのシフトレジスタ５２、除数格納出力手段としてのレジスタ５４〜６２、演算データ格納出力手段としてのレジスタ６４〜７０、論理積手段としての論理積素子７２〜７８、排他的論理和手段としての排他的論理和素子８０〜８６、有効桁数検出手段としてのセレクタ８８〜９６、演算結果格納手段としてのシフトレジスタ９８などにより構成されている。
シフトレジスタ５２には、被除数Ａが格納され、１クロック毎に上位桁から出力するものである。ここでは、一例として被除数Ａ＝（１，１，０，１，０，０，１，１，１）とすると、１，１，１，０，０，１，０，１，１の順に出力される。
レジスタ５４〜６２は、除数Ｂを格納するもので、レジスタ６２に最上位桁（ＭＳＢ）、そしてレジスタ６０、５８、５６…と順に格納してゆき、レジスタ５４に最下位桁（ＬＳＢ）を格納する。ここでは、一例として５ビットの除数Ｂ＝（１，０，１，０，０）とすると、レジスタ５４〜６２には順に１，０，１，０，０が格納される。
レジスタ６４〜７０は、演算用のレジスタであって、レジスタ７０が最上位桁となる。レジスタ６４〜７０は、演算前に全て「０」にリセットされる。各レジスタ６４〜７０には、対応する桁のレジスタ５４〜６２からの除数Ｂと、セレクタ９６からの出力信号１００との論理積（論理積素子７２〜７８による）出力と、一つ下位の桁の出力（例えば、最下位桁のレジスタ６４にはシフトレジスタ５２からの出力）との排他的論理和（排他的論理和素子８０〜８６による）出力が入力される。
【００１３】
排他的論理和素子８０〜８６は、減算を実行する素子である。
論理積素子７２〜７８は、論理積を実行する素子であり、ここに入力されるセレクタ９６からの出力信号１００は、減算するかしないかの選択信号である。この選択信号は、レジスタ５４〜６２からの除数Ｂと、シフトレジスタ５２からの出力、およびレジスタ６４〜７０の各出力と、セレクタ８８〜９６とによって制御される。
この各セレクタ８８〜９６を制御する制御信号は、レジスタ５４〜６２から出力される除数Ｂのそれぞれの値である。この制御信号の値が「１」の時は、その次数に対応する演算用のレジスタ６４〜７０の出力がそのままセレクタ出力となり、制御信号の値が「０」の時は、一つ下の次数のセレクタ出力を上位次数のセレクタへ渡すようにする。
最終的な出力信号１００は、除数Ｂの値が「１」である次数の中で最高次のセレクタ９６の出力となる。これにより、除数Ｂの有効ビット数を検出している。本実施の形態２では、除数Ｂ＝（１，０，１，０，０）であるので、レジスタ５８からセレクタ９２に除数Ｂの最高次の「１」が出力されて、レジスタ６６の出力が出力信号１００となる。また、例えば、除数Ｂ＝（１，０，０，１，１）の場合は、レジスタ７０の出力が出力信号１００となる。
通常、出力信号１００の値は「０」である（図５の１クロック目参照）。すなわち、減算をせずに演算用のレジスタ６４〜７０をそのままシフトさせる。このようにして、被除数Ａの上位桁から順にシフトしていって、有効ビットの次の値が「１」となった時に減算が実行される。
また、出力信号１００の値が「１」になった場合は（図５の２〜３クロック目参照）、論理積素子７２〜７８がレジスタ５４〜６０からの除数Ｂの値を出力し、排他的論理和素子８０〜８６において減算が実行される。
そして、出力信号１００は、そのままシフトレジスタ９８にも格納され、これが商Ｃとなる。このような処理動作は、被除数Ａの全ビットが出力されるまで行われる。すなわち、被除数Ａがｍビットであれば、ｍクロックで処理動作を止め、この時のレジスタ６４〜７０に格納されている値が剰余Ｄとなる。その時のレジスタ７０の値が最上位桁（ＭＳＢ）である。
また、図５は、除数のビット数の制限を受けない図４の除算演算回路５０による演算処理状態を示す図である。ここでは、除数Ｂ＝（１，０，１，０，０）が３ビットであっても、除算演算回路５０でＡ／Ｂを計算することにより、商が１１０１０００となり、剰余Ｄが１１となる。
【００１４】
次に、その除算演算の処理動作を説明する。
図６は、図４の除算演算回路５０を用いて除算演算を行う場合の処理動作を説明する図である。
図６に示すように、被除数Ａ＝（１，１，０，１，０，０，１，１，１）がシフトレジスタ５２に格納され、その上位のレジスタ６４〜７０に４（ｎ−１）ビット分の「０」を置いて、これを被除数Ａとし、その被除数Ａの上位５（ｎ）ビット列「１００００」を演算対象Ａ´として抽出する。ここで、除数Ｂ＝（１，０，１，０，０）であるので、０次から「１」の値を持つ次数の中で最高次までの有効ビット数をｔとすると、ｔ＝３となる。このため、上記した演算対象Ａ´「１００００」の３ビット目の「０」が商ｃ８＝０となる。
この演算対象Ａ´の３ビット目が「０」であれば、演算対象Ａ´の最上位ビットを除く４ビット（ｎ−１ビット）列を抽出すると共に、その４ビット列に被除数Ａのａ７の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「０」を商ｃ７＝０とする。
同様に演算対象Ａ´の３ビット目が「０」であるので、その演算対象Ａ´の最上位ビットを除く４ビット列を抽出すると共に、その４ビット列に被除数Ａのａ６の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「１」を商ｃ６＝１とする
新たな演算対象Ａ´の３ビット目が「１」ならば、除数Ｂを減算して、その減算結果Ａ″として抽出し、その減算結果Ａ″の最上位ビットを除く４（ｎ−１）ビット列を抽出し、被除数Ａのａ５の「０」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出する。そして、この新たな演算対象Ａ´の３ビット目の「１」を商ｃ５＝１とする。
この新たな演算対象Ａ´の３ビット目は、「１」であるので除数Ｂを減算し、それを新たな減算結果Ａ″として抽出し、その減算結果Ａ″の最上位ビットを除く４ビット列を抽出して、被除数Ａのａ４の「０」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出する。そして、この新たな演算対象Ａ´の３ビット目の「０」を商ｃ４＝０とする。
【００１５】
新たな演算対象Ａ´の３ビット目は、「０」であるので、その演算対象Ａ´の最上位ビットを除く４ビット列を抽出すると共に、被除数Ａのａ３の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「１」を商ｃ３＝１とする
この新たな演算対象Ａ´の３ビット目が「１」であるので除数Ｂを減算し、それを新たな減算結果Ａ″として抽出し、減算結果Ａ″の最上位ビットを除く４ビット列を抽出して、被除数Ａのａ２の「０」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出する。そして、この新たな演算対象Ａ´の３ビット目の「０」を商ｃ２＝０とする。
新たな演算対象Ａ´の３ビット目は、「０」であるので、その演算対象Ａ´の最上位ビットを除く４ビット列を抽出すると共に、被除数Ａのａ１の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「０」を商ｃ１＝０とする。
同様に、新たな演算対象Ａ´の３ビット目が「０」であるので、その演算対象Ａ´の最上位ビットを除く４ビット列を抽出すると共に、被除数Ａのａ０の「１」を最下位ビットとして付加し、これを新たな演算対象Ａ´として抽出して、その３ビット目の「０」を商ｃ０＝０とする。
この商Ｃのｃ０までを求めた時の新たな演算対象Ａ´の最上位ビットを除いた４（ｎ−１）ビット列が剰余Ｄとなる。
このように、本実施の形態２では、被除数Ａ＝（１，１，０，１，０，０，１，１，１）とし、除数Ｂ＝（１，０，１，０，０）として、図４の除算演算回路５０により実際にＡ／Ｂを計算すると、その時の商Ｃが「０００１０１１」となり、その剰余Ｄを「１１」と求めることができる。
以上説明したように、本実施の形態２によれば、ガロア体上の元の除算および剰余算を除数Ｂのビット制限なく実現することができる。
【００１６】
（実施の形態３）
本実施の形態３は、ガロア体ＧＦ（２m）上ベクトルで表わされる２つの元の除算演算（標数２の除算）と、一般的に用いられる除算演算（標数Ｐの演算）のどちらの除算演算をも可能とする除算演算回路を実現するものである。
図７は、本実施の形態３に係る除算演算回路１１０の構成例を示す図である。この構成例では、除数の最大ビット数を４ビットとする。つまり、除数としては１〜４ビットまでを使用することができる。
図７に示す除算演算回路１１０は、シフトレジスタ１１２、レジスタ１１４〜１２０、除算演算用モジュール１２２〜１３０、レジスタ１３２〜１３８、インバータ１４０、セレクタ１４２、シフトレジスタ１４４などにより構成されている。
シフトレジスタ１１２には、被除数Ａが格納され、１クロック毎に上位桁から出力するものである。
レジスタ１１４〜１２０は、除数Ｂを格納するもので、レジスタ１２０に最上位桁（ＭＳＢ）、そしてレジスタ１１８、１１６…と順に格納してゆき、レジスタ１１４に最下位桁（ＬＳＢ）を格納する。
今、ここでは一例として標数Ｐにおいて７５÷１２を計算しようとすると、被除数７５の２進表現１００１０１１がシフトレジスタ１１２に格納され、１，１，０，１，０，０，１の順に出力されて、除数１２の２進表現１１００がレジスタ１１４〜１２０に順番に０，０，１，１と格納される。
同様に標数２においても、ベクトルで表現されるガロア体上の２つの元、被除数Ａ＝（１，１，０，１，０，１，０，０，１）、除数Ｂ＝（１，０，１，１）の除算演算時には、シフトレジスタ１１２に被除数Ａが格納され、１，０，０，１，０，１，０，１，１の順に出力されて、レジスタ１１４〜１２０に除数Ｂが順番に１，０，１，１と格納される。
レジスタ１３２〜１３８は、演算用のレジスタであり、レジスタ１３８が最上位桁となり、演算前に全て「０」にリセットされる。
【００１７】
除算演算用モジュール１２２〜１３０は、除算演算用の回路をモジュール化したものである。図８（ａ）は、図７の除算演算用モジュールを示す図であり、（ｂ）は、除算演算用モジュール内の演算部の構造を示す図であり、（ｃ）は、標数Ｐ用のボロー計算部の構造を示す図であり、（ｄ）は、標数２用の演算制御部を示す図である。
図８（ａ）に示した除算演算用モジュール１２２（１２４〜１３０も同様）の左側のＡ〜Ｆは、入力信号であり、右側のＬ〜Ｎは出力信号である。その除算演算用モジュール１２２の内部は、図８（ｂ）〜（ｄ）に示すように、３つのブロックにそれぞれ分かれている。
図８（ｂ）は、除算演算の為の演算（減算）を行う演算部である。入力信号Ｆは、減算処理を実行するか否かの実行／非実行の選択信号であり、「１」で実行、「０」で非実行となる。この減算非実行時は、前段のレジスタからの入力信号Ａがそのままセレクタ１５４を通って出力される（出力信号Ｌ）。また、減算実行時には、入力信号Ａ、除数Ｂの対応桁の値、前段からのボロー信号の３つの値がエクスクル−シブオアゲート１５２により排他的論理和演算がなされ、セレクタ１５４を通って出力される。但し、標数２の演算時には、ボロー信号は不要となるので、標数Ｐ／標数２の選択信号Ｅ（「１」で標数Ｐを選択、「０」で標数２を選択）によって、アンドゲート１５０の出力がエクスクル−シブオアゲート１５２に入力され、マスクされる。そして、レジスタ１３２〜１３８の入力には、この演算部の出力信号Ｌが入力される。
図８（ｃ）は、標数Ｐ用の演算制御部であるボロー計算部であり、前段の除算演算用モジュールの標数Ｐ用のボロー計算部の出力信号Ｍがボロー信号Ｃとして入力される。このボロー信号Ｃと除数Ｂの対応桁の値がオアゲート１５８に入力され、その出力信号と前段からのレジスタからの入力信号Ａの反転信号がアンドゲート１６０に入力される。また、ボロー信号Ｃと除数Ｂの対応桁の値をアンドゲート１５６に入力し、その出力信号と前記アンドゲート１６０の出力信号とをオアゲート１６２に入力し、その出力信号Ｍが次段の除算演算用モジュール等に出力される。この図８（ｃ）のボロー計算部へのＡ、Ｂ、Ｃの入力信号の組み合わせと、出力信号Ｍとの関係を一覧に示したのが図９である。
図８（ｄ）は、標数２用の演算制御部であり、セレクタ１６４を備えている。このセレクタ１６４に入力される入力信号Ｂは、除数Ｂに対応する桁の値であり、これが「１」の時は前段レジスタの出力Ａを出力し、「０」の時は標数２の制御信号Ｄを出力する。前段の標数２用の演算制御部の出力信号Ｎは、次段の標数２の制御信号Ｄとして入力される。
【００１８】
標数Ｐ／標数２のそれぞれの場合において、演算制御部の最終段の出力（標数Ｐの場合はＭ、標数２の場合はＮ、但し、標数ＰはＭの論理反転出力）が減算処理を実行するか否かを選択する減算実行／非実行選択信号となる。信号１４６の標数Ｐ／標数２の選択信号によって実行する除算演算が選択され、これに対応する減算実行／非実行選択信号が信号１４８となり、各除算演算用モジュール１２２〜１３０のＦ端子へ入力される。
通常、信号１４８の値は「０」、すなわち、減算処理をせずに演算用のレジスタ１３２〜１３８をそのままシフトさせる。このようにして、シフトレジスタ１１２に格納されている被除数Ａの上位桁から順にシフトしていき、信号１４８の減算実行／非実行選択信号が「１」となった時に減算処理が実行される。信号１４８の出力は、そのままシフトレジスタ１４４に格納され、これが商となる。
上記の動作をシフトレジスタ１１２の被除数Ａの全ビットが出力されるまで、すなわち、被除数Ａがｍビットであればｍクロックで動作を止めるようにする。また、この時のレジスタ１３２〜１３８の値が剰余となり、そのうちのレジスタ１３８の値が最高位桁（ＭＳＢ）となる。
図１０は、図７の除算演算回路１１０による標数Ｐの演算処理過程を説明する図である。図１０に示されるように、標数Ｐにおける７５÷＋９を実際に計算すると、商が８（２進数表現で１０００）、剰余が３（２進表現で１１）と求めることができる。
また、図１１は、図７の除算演算回路１１０による標数２の演算処理過程を説明する図であり、被除数Ａ＝（１，１，０，１，０，１，０，０，１）、除数Ｂ＝（１，０，１，１）の場合であって、Ａ／Ｂを実際に計算すると、商が１０１０１０、剰余が１０１というように求めることができる。
以上説明したように、本実施の形態３によれば、標数Ｐと標数２のどちらの場合の除算演算であっても、それぞれ別に回路を設けることなく、低コストの除算演算回路を実現することができる。
【符号の説明】
【００１９】
１０ 除算演算回路、１２ シフトレジスタ、１４〜２２ レジスタ、２４〜３０ レジスタ、３２〜３８ 論理積素子、４０〜４６ 排他的論理和素子、４８ シフトレジスタ、５０ 除算演算回路、５２ シフトレジスタ、５４〜６２ レジスタ、６４〜７０ レジスタ、７２〜７８ 論理積素子、８０〜８６ 排他的論理和素子、８８〜９６ セレクタ８８〜９６、９８ シフトレジスタ、１１０ 除算演算回路、１１２ シフトレジスタ、１１４〜１２０ レジスタ、１２２〜１３０ 除算演算用モジュール、１３２〜１３８ レジスタ、１４０ インバータ、１４２ セレクタ、１４４ シフトレジスタ、１４６、１４８ 信号、１５０ アンドゲート、１５２ エクスクル−シブオアゲート、１５４ セレクタ、１５６ アンドゲート、１５８ オアゲート、１６０ アンドゲート、１６２ オアゲート、１６４ セレクタ
【特許請求の範囲】
【請求項１】
ガロア体上のｍビットとｎビット（ｍ、ｎは共に自然数で、ｍ＞ｎ）のベクトルで表現される２つの元である被除数Ａ＝（ａ０，…，ａｍ−１）と除数Ｂ＝（ｂ０，…，ｂｎ−１）に対してＡ／Ｂを演算し、最大でｍビットで表現される商Ｃ＝（ｃ０，…，ｃｍ−１）と、最大でｎ−１ビットで表現される剰余Ｄ＝（ｄ０，…，ｄｎ−２）とを求めるためのガロア体上の元の除算演算回路であって、
ｍビットから成る前記被除数Ａを格納し、上位ビットから順次出力する被除数格納出力手段と、
ｎビットから成る前記除数Ｂを各桁毎に格納し、それぞれ個別に出力する除数格納出力手段と、
各桁毎の演算データをそれぞれ格納し、その演算データを次桁へ出力する演算データ格納出力手段と、
前記被除数格納出力手段から出力される被除数あるいは前記演算データ格納出力手段から出力される各桁の演算データを前記除数格納出力手段から出力される除数の値に基づいて、そのまま出力するか、一つ下の桁の出力を上位桁へ渡すかを選択して前記除数の有効桁数を検出する有効桁数検出手段と、
前記有効桁数検出手段からの出力と、前記除数格納出力手段から出力される各桁の除数Ｂとの論理積をとって減算処理するか否かを選択する論理積手段と、
前記論理積手段からの論理積出力と、前記被除数格納出力手段から出力される被除数あるいは前記演算データ格納出力手段から出力される演算データとの排他的論理和をとって減算処理を実行する排他的論理和手段と、
前記有効桁数検出手段からの出力を順次入力して格納する演算結果格納手段と、
を備え、前記被除数Ａの全ビットが出力されるまで演算処理を実行することにより、前記演算結果格納手段に前記商Ｃが格納され、前記演算データ格納出力手段に剰余Ｄが格納されることを特徴とするガロア体上の元の除算演算回路。
【請求項１】
ガロア体上のｍビットとｎビット（ｍ、ｎは共に自然数で、ｍ＞ｎ）のベクトルで表現される２つの元である被除数Ａ＝（ａ０，…，ａｍ−１）と除数Ｂ＝（ｂ０，…，ｂｎ−１）に対してＡ／Ｂを演算し、最大でｍビットで表現される商Ｃ＝（ｃ０，…，ｃｍ−１）と、最大でｎ−１ビットで表現される剰余Ｄ＝（ｄ０，…，ｄｎ−２）とを求めるためのガロア体上の元の除算演算回路であって、
ｍビットから成る前記被除数Ａを格納し、上位ビットから順次出力する被除数格納出力手段と、
ｎビットから成る前記除数Ｂを各桁毎に格納し、それぞれ個別に出力する除数格納出力手段と、
各桁毎の演算データをそれぞれ格納し、その演算データを次桁へ出力する演算データ格納出力手段と、
前記被除数格納出力手段から出力される被除数あるいは前記演算データ格納出力手段から出力される各桁の演算データを前記除数格納出力手段から出力される除数の値に基づいて、そのまま出力するか、一つ下の桁の出力を上位桁へ渡すかを選択して前記除数の有効桁数を検出する有効桁数検出手段と、
前記有効桁数検出手段からの出力と、前記除数格納出力手段から出力される各桁の除数Ｂとの論理積をとって減算処理するか否かを選択する論理積手段と、
前記論理積手段からの論理積出力と、前記被除数格納出力手段から出力される被除数あるいは前記演算データ格納出力手段から出力される演算データとの排他的論理和をとって減算処理を実行する排他的論理和手段と、
前記有効桁数検出手段からの出力を順次入力して格納する演算結果格納手段と、
を備え、前記被除数Ａの全ビットが出力されるまで演算処理を実行することにより、前記演算結果格納手段に前記商Ｃが格納され、前記演算データ格納出力手段に剰余Ｄが格納されることを特徴とするガロア体上の元の除算演算回路。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１０−２１７９２１（Ｐ２０１０−２１７９２１Ａ）
【公開日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願番号】特願２０１０−１４０１３１（Ｐ２０１０−１４０１３１）
【出願日】平成２２年６月２１日（２０１０．６．２１）
【分割の表示】特願平１１−３７１９６５の分割
【原出願日】平成１１年１２月２７日（１９９９．１２．２７）
【出願人】（３０５０２７４５６）ネッツエスアイ東洋株式会社 (200)
【Ｆターム（参考）】
【公開日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願日】平成２２年６月２１日（２０１０．６．２１）
【分割の表示】特願平１１−３７１９６５の分割
【原出願日】平成１１年１２月２７日（１９９９．１２．２７）
【出願人】（３０５０２７４５６）ネッツエスアイ東洋株式会社 (200)
【Ｆターム（参考）】
[ Back to top ]