(57)【要約】【課題】標数３の有限体ＧＦ（３）の乗算と加減算が高速に行える有限体ＧＦ（３）の演算方法及び演算装置の実現。【解決手段】２グループ11X,11Yで構成され、各グループが３個のレジスタR0-R2,R3-R5で構成される合計６個のレジスタ群と、６個のレジスタの２個の値を入力としてＡＮＤ、ＯＲ、ＸＯＲ及びコピー処理を行い、処理結果を前記２個の入力の一方のレジスタに格納するように構成された演算回路12-15と、を備える標数が３の有限体ＧＦ（３）の演算装置であって、乗算、加算及び減算の少なくとも１つの演算は、有限体ＧＦ（３）の３個の元０、１、２を、３ビットで表し、第１の入力の０−２ビットを第１のグループの第０から第２レジスタにそれぞれ格納し、第２の入力の０−２ビットを第２のグループの第３から第５レジスタにそれぞれ格納して演算を行う。【選択図】図２
2008134812.tif 000002
【特許請求の範囲】
【請求項１】
標数が３の有限体ＧＦ（３）の演算方法であって、
前記有限体ＧＦ（３）の３個の元０、１、２を、３ビットで表し、
乗算、加算及び減算の少なくとも１つの演算を、３ビットで表された元で行う、ことを特徴とする有限体ＧＦ（３）の演算方法。
【請求項２】
２グループで構成され、各グループが３個のレジスタで構成される合計６個のレジスタ群と、前記６個のレジスタの２個の値を入力としてＡＮＤ、ＯＲ、ＸＯＲ及びコピー処理を行い、処理結果を前記２個の入力の一方のレジスタに格納するように構成された演算回路と、を備える標数が３の有限体ＧＦ（３）の演算装置であって、
乗算、加算及び減算の少なくとも１つの演算は、有限体ＧＦ（３）の３個の元０、１、２を、３ビットで表し、
第１の入力の０−２ビットを第１のグループの第０から第２レジスタにそれぞれ格納し、
第２の入力の０−２ビットを第２のグループの第３から第５レジスタにそれぞれ格納して演算を行うことを特徴とする有限体ＧＦ（３）の演算装置。
【請求項３】
乗算は、入力と出力の３ビット表現が異なる請求項２に記載の有限体ＧＦ（３）の演算装置。
【請求項４】
乗算と加算及び減算で、３個の元の３ビット表現が異なる請求項２に記載の有限体ＧＦ（３）の演算装置。
【請求項５】
第１の入力と第２の入力の乗算は、
前記３個の元０、１、２を、”０００”、”０１１”、”１１０”で表現し、
前記第１の入力の０−２ビットをそれぞれ第０から第２レジスタに格納し、
前記第２の入力の０−２ビットをそれぞれ第３から第５レジスタに格納し、
前記第３レジスタと前記第０レジスタの値のＡＮＤを演算して第３レジスタに格納し、
前記第４レジスタと前記第１レジスタの値のＡＮＤを演算して第４レジスタに格納し、
前記第５レジスタと前記第２レジスタの値のＡＮＤを演算して第５レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＯＲを演算して第３レジスタに格納し、
前記３及び第４レジスタの値を、前記３個の元０、１、２を、”００”、”１１”、”１０”で表現する出力の０−１ビットとして出力する請求項２または３に記載の有限体ＧＦ（３）の演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、標数が３の有限体（ガロア体）ＧＦ（３）の演算方法および演算装置に関し、特に乗算、加算及び減算の演算方法および演算装置に関する。
【背景技術】
【０００２】
有限体（ガロア体）の演算は，デジタルオーディオ機器などのエラー訂正方式、公開鍵暗号方式などの技術分野で広く行われており、前者では主に標数２の有限体、後者では標数２以上の有限体が用いられる．有限体（ガロア体）ＧＦ（３）の演算は、標数３の有限体ＧＦ（３m）の計算過程で多数回行うことが必要である（ｍは正の整数）。ＧＦ（３m）の計算を必要とする例としては、楕円曲線暗号におけるペアリングの高速演算などが挙げられる。ペアリングの高速演算については、例えば、非特許文献１、２および特許文献１などに記載されている。非特許文献１は、ペアリングを用いることでＩＤベース暗号などの新しい暗号システムが可能になることも記載している。
【０００３】
有限体（ガロア体）ＧＦ（３）の演算自体については、広く知られているので、これ以上の説明は省略する。
【０００４】
【非特許文献１】白勢・高木・岡本，「Ｔａｔｅペアリングの効率的なアルゴリズム」信学技報ISEC2006-12,0019-26，電子情報通信学会
【非特許文献２】G. Granger, D. Page & M. Stam, "Hardware and Software Normal Basis Arithmetic for Pairing Based Cryptography in Characteristic Three*", Cryptology ePrint Archive 2004/157
【特許文献１】特開２００６−１７８１２５
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ペアリングの計算は演算量が多いため、非特許文献１、２および特許文献１に記載されているように計算を効率化する手法が求められる。
【０００６】
本発明は、標数３の有限体ＧＦ（３）の乗算と加減算が高速に行える有限体ＧＦ（３）の演算方法及び演算装置の実現を目的とする。
【課題を解決するための手段】
【０００７】
上記目的を実現するため、本発明の有限体ＧＦ（３）の演算方法及び演算装置は、２ビットで表現することが可能であり、通常は２ビットで表現されていた３個の元０、１、２を３ビットで表現し、ビット同士の論理演算のみで、乗算・加減算・表現の相互変換演算を行うことを特徴とする。
【０００８】
本発明によれば、３ビットの外へのキャリー／ボローが発生せず、ＧＦ（３）の各元に共通のアルゴリズムで演算が可能であり、実質的に演算ステップ数を減少させることができる。
【０００９】
演算装置では、３ビット表現の各ビットを異なるレジスタに割り当てるように、少なくとも６個のレジスタを設ける。各レジスタのビット幅は、適宜設定され、ビット幅と同じ個数の演算が並列に行える。
【００１０】
上記のように、本発明では、通常は２ビットで表現されていた３個の元を３ビットで表現するため、必要に応じて、演算の入力を２ビット表現から３ビット表現に変換し、演算の出力を３ビット表現から２ビット表現に変換する処理を行う。表現の変換処理が簡単に行える表現を使用する。
【００１１】
乗算においては、入力と出力の３ビット表現が異なるようにしてもよい。
【００１２】
また、乗算と加算及び減算とで、３個の元の３ビット表現が異なるようにしてもよい。
【００１３】
ＧＦ（３）の演算では、０の減算は０の加算とし、１の減算は２の加算とし、２の減算は１の加算として行うことが可能であり、本発明でも同様である。
【００１４】
多項式の積の演算は、乗算結果を加減算するので、乗算結果の出力表現と、加算または減算の入力表現を一致させると変換処理が不要である。
【発明の効果】
【００１５】
本発明によれば、３ビットの外へのキャリー／ボローが発生しないので、乗算と加減算とでそれぞれ演算が効率的に実行でき、実質的に演算ステップ数を減少させて高速化が図れる。また、３ビットの外へのキャリー／ボローが発生せず、ＧＦ（３）の各元に共通のアルゴリズムで演算が可能であるので、演算装置の構成を簡単にできる。
【００１６】
また、演算装置の構成が簡単であるので、各レジスタのビット幅を大きくすることが容易であり、演算の並列度を高くして高速化が可能である。
【発明を実施するための最良の形態】
【００１７】
本発明の実施例を説明する前に有限体（ガロア体）ＧＦ（３）の演算について簡単に説明する。
【００１８】
図１は、有限体ＧＦ（３）の演算規則を示す図である。本発明は、有限体ＧＦ（３）の四則演算のうちの、加算、減算、乗算を対象とする。
【００１９】
図２は、本発明の実施例のＧＦ（３）演算装置のハードウェア構成図である。図示のように、演算装置は、３２ビットのビット幅を有する９個のレジスタＲ０−Ｒ８、３２ビット並列ＡＮＤ回路１２と、３２ビット並列ＯＲ回路１３と、３２ビット並列ＸＯＲ回路１４と、３２ビット並列ＣＯＰＹ回路１５と、各部を制御する制御部１６と、３つのバス１７−１８と、を有する。レジスタＲ０−Ｒ２が第１レジスタグループ１１Ｘを、レジスタＲ３−Ｒ５が第２レジスタグループ１１Ｙを、レジスタＲ６−Ｒ８が第３レジスタグループ１１Ｚを、構成する。レジスタＲ０−Ｒ８のそれぞれは、記憶しているデータをバス１７および１８に出力し、バス１９からのデータを記憶するように構成されている。３２ビット並列ＡＮＤ回路１２、３２ビット並列ＯＲ回路１３および３２ビット並列ＸＯＲ回路１４は、バス１７および１８のデータを入力として、ＡＮＤ（論理積）、ＯＲ（論理和）、ＸＯＲ（排他的論理和）演算を行い、演算結果をバス１９に出力する。従って、３２ビット並列ＡＮＤ回路１２、３２ビット並列ＯＲ回路１３および３２ビット並列ＸＯＲ回路１４は、レジスタＲ０−Ｒ８のいずれか２つに記憶されたデータを入力として演算を行い、演算結果はレジスタＲ０−Ｒ８のいずれかに格納される。また、３２ビット並列ＣＯＰＹ回路１５は、バス１７のデータを入力して、バス１９にそのまま出力する。従って、レジスタＲ０−Ｒ８のいずれかに記憶されたデータが、３２ビット並列ＣＯＰＹ回路１５を介して、レジスタＲ０−Ｒ８のいずれかにコピーされる。
【００２０】
ここでは、レジスタ、演算回路およびバスのビット幅を３２ビットとしたが、これに限定されず、任意のビット数に設定可能である。また、第３レジスタグループ１１Ｚを構成するレジスタＲ６−Ｒ８を設けたが、このレジスタＲ６−Ｒ８を必要とするのはある加減算を行う時のみであり、この加減算を行わない時には設ける必要はない。また、他のレジスタグループと同じ構成にするために第３レジスタグループ１１Ｚにも３個のレジスタＲ６−Ｒ８を設けたが、この加減算を行う時でもレジスタＲ８は使用しないので、Ｒ８を除くことが可能である。
【００２１】
図３は、演算装置の各演算回路の動作およびレジスタのデータ格納動作を説明する図である。各演算回路は、任意の２個のレジスタ（同一でもよい）Ｒｉ、Ｒｊに格納されているデータを入力として、それらのビットごとの指示された論理演算を、１ステップ（１クロックサイクル）で行い、演算結果は最初に指定したレジスタＲｉに上書きされる。各演算回路の処理を式で表せば、図３の（Ａ）から（Ｃ）のようになる。ここで、０≦ｉ≦８および０≦ｊ≦８である。また、３２ビット並列ＣＯＰＹ回路１５は、任意のレジスタＲｉの値を任意のレジスタＲｊに１ステップでコピーする。この処理を式で表せば、図３の（Ｄ）のようになる。ここで、０≦ｉ≦８および０≦ｊ≦８である。
【００２２】
次に、レジスタにおけるデータの格納方法を説明する。３ビットで表現された元は、ビットごとに各グループの別のレジスタに格納する。レジスタのビット幅（ここでは３２ビット）と同じ個数の元について、それらの３ビット表現を、（Ｘｃ−３２，Ｘｂ−３２，Ｘａ−３２），・・・，（Ｘｃ−１，Ｘｂ−１，Ｘａ−１）とすると、それを第１レジスタグループ１１ＸのレジスタＲ０−Ｒ２に格納すると、図２に示すようになる。第２レジスタグループ１１Ｙ、第３レジスタグループ１１Ｚについても、同様に図２に示すようになる。
【００２３】
演算回路のうち、例えばＡＮＤ回路をＲ３←ＡＮＤ（Ｒ３，Ｒ０）で動作させると、
Ｙａ−ｉ←Ｙａ−ｉ  ＡＮＤ  Ｘａ−ｉ
が、１ステップでｉ＝１から３２まで同時に実行される。
【００２４】
以下、乗算、加算および減算の各演算についての処理を説明する。
【００２５】
実施例の演算装置では、乗算処理は、２つの処理方法で行うことが可能である。
【００２６】
図４は、第１の乗算処理におけるレジスタの値の変化を示す第１の乗算処理の説明図であり、図５は第１の乗算処理を示すフローチャートである。３２ビット幅の各データについて、図示のような処理が行われる。
【００２７】
図４に示すように、第１の乗算処理では、元０、１、２はそれぞれ”０００”、”０１１”、”１１０”で表現される。図４に示した処理では、入力の一方は、第１レジスタグループ１１ＸのレジスタＲ０−Ｒ２に格納されたデータであり、入力の他方は第２レジスタグループ１１ＹのレジスタＲ３−Ｒ５に格納されたデータであり、演算結果は第２レジスタグループ１１ＹのレジスタＲ３−Ｒ５に格納される。第１の入力の３ビットのうち、ＸａビットがＲ０に、ＸｂビットがＲ１に、ＸｃビットがＲ２に格納され、第２の入力の３ビットのうち、ＹａビットがＲ３に、ＹｂビットがＲ４に、ＹｃビットがＲ５に格納される。
【００２８】
図４において、各列は、図示した入力に対するレジスタの値の変化を示し、上段が第１レジスタグループ１１ＸのレジスタＲ０−Ｒ２に格納されたデータを、下段が第２レジスタグループ１１ＹのレジスタＲ３−Ｒ５に格納されたデータを示す。
【００２９】
図５に示すように、ステップ１０１では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ３の値とレジスタＲ０の値のＡＮＤを演算し、演算結果がレジスタＲ３に格納される。
【００３０】
ステップ１０２では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ４の値とレジスタＲ１の値のＡＮＤを演算し、演算結果がレジスタＲ４に格納される。
【００３１】
ステップ１０３では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ５の値とレジスタＲ２の値のＡＮＤを演算し、演算結果がレジスタＲ５に格納される。
【００３２】
ステップ１０４では、３２ビット並列ＯＲ回路１３が、レジスタＲ３の値とレジスタＲ５の値のＯＲを演算し、演算結果がレジスタＲ３に格納される。
【００３３】
ステップ１０５では、３２ビット並列ＯＲ回路１３が、レジスタＲ５の値とレジスタＲ４の値のＯＲを演算し、演算結果がレジスタＲ５に格納される。
【００３４】
ステップ１０６では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ５の値とレジスタＲ３の値のＸＯＲを演算し、演算結果がレジスタＲ５に格納される。
【００３５】
各ステップで、各レジスタの値は図示のように変化する。
【００３６】
以上の処理により、入力のそれぞれの組合せに対して、ＧＦ（３）乗算に即した演算結果が得られる。演算結果は、入力と同じ形で表現される。
【００３７】
第１の乗算処理では、入力および出力において、元０、１、２はそれぞれ”０００”、”０１１”、”１１０”で表現されるが、これは通常使用される表現、すなわち元０、１、２を”００”、”０１”、”１０”で表現する形式と異なる。そのため、通常の表現のデータを本発明の演算装置に入力する場合、および本発明の演算装置で演算した結果を通常の表現のデータとして出力する場合には、表現形式の変換処理が必要である。
【００３８】
図６の（Ａ）は、通常表現から第１の乗算処理の表現に変換する変換処理におけるレジスタの値の変化を示す変換処理の説明図であり、図６の（Ｂ）は、第１の乗算処理の表現から通常表現に変換する変換処理におけるレジスタの値の変化を示す変換処理の説明図であり、図７の（Ａ）は通常表現から第１の乗算処理の表現に変換する変換処理を示すフローチャートであり、図７の（Ｂ）は第１の乗算処理の表現から通常表現に変換する変換処理を示すフローチャートである。
【００３９】
図６の（Ａ）に示すように、通常表現では、元０、１、２は”００”、”０１”、”１０”で表現されるので、これを”０００”、”０１１”、”１１０”に変換する。変換に第１レジスタグループ１１Ｘを使用する場合には、通常表現の２ビットの値をそれぞれレジスタＲ０、Ｒ１に入力する。この時、レジスタＲ３の値は何でもよい。図７の（Ａ）に示すように、ステップ２０１では、３２ビット並列ＣＯＰＹ回路１５が、レジスタＲ１の値をレジスタＲ２にコピーする。ステップ２０２では、３２ビット並列ＯＲ回路１３がレジスタＲ１の値とレジスタＲ０の値のＯＲを演算して、演算結果がレジスタＲ１に格納される。この時の各レジスタの値の変化は図６の（Ａ）の通りであり、第１レジスタグループ１１ＸのレジスタＲ０−Ｒ２に第１の乗算処理の表現のデータが格納される。
【００４０】
図６の（Ｂ）に示すように、第１の乗算処理の出力の元０、１、２は”０００”、”０１１”、”１１０”で表現されるので、これを通常表現の”００”、”０１”、”１０”に変換する。ここでは、第１レジスタグループ１１Ｘのデータを変換するとする。図７の（Ｂ）に示すように、ステップ２１１では、３２ビット並列ＸＯＲ回路１４がレジスタＲ０の値とレジスタＲ１の値のＸＯＲを演算して、演算結果がレジスタＲ０に格納される。この時の各レジスタの値の変化は図６の（Ｂ）の通りであり、第１レジスタグループ１１ＸのレジスタＲ０、Ｒ１に通常表現のデータが格納される。
【００４１】
次に実施例のＧＦ（３）の演算装置が行う第２の乗算処理について説明する。
【００４２】
図８は、第２の乗算処理におけるレジスタの値の変化を示す第２の乗算処理の説明図であり、図９は第１の乗算処理を示すフローチャートである。３２ビット幅の各データについて、図示のような処理が行われる。
【００４３】
図８に示すように、第２の乗算処理の入力データの表現は第１の乗算処理と同じであるが、出力（演算結果）の表現は異なり、元０、１、２はそれぞれ”Ｘ００”、”Ｘ１１”、”Ｘ１０”で表現される（ここで、Ｘは０または１のどちらでもよい）。図４の説明と同様に、図８に示した処理では、入力の一方は、第１レジスタグループ１１ＸのレジスタＲ０−Ｒ２に格納されたデータであり、入力の他方は第２レジスタグループ１１ＹのレジスタＲ３−Ｒ５に格納されたデータであり、演算結果は第２レジスタグループ１１ＹのレジスタＲ３−Ｒ５に格納される。
【００４４】
図９に示すように、ステップ３０１では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ３の値とレジスタＲ０の値のＡＮＤを演算し、演算結果がレジスタＲ３に格納される。
【００４５】
ステップ２０２では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ４の値とレジスタＲ１の値のＡＮＤを演算し、演算結果がレジスタＲ４に格納される。
【００４６】
ステップ２０３では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ５の値とレジスタＲ２の値のＡＮＤを演算し、演算結果がレジスタＲ５に格納される。
【００４７】
ステップ３０４では、３２ビット並列ＯＲ回路１３が、レジスタＲ３の値とレジスタＲ５の値のＯＲを演算し、演算結果がレジスタＲ３に格納される。
【００４８】
各ステップで、各レジスタの値は図示のように変化する。
【００４９】
以上の処理により、入力のそれぞれの組合せに対して、ＧＦ（３）乗算に即した演算結果が得られる。演算結果では、元０、１、２がそれぞれ”Ｘ００”、”Ｘ１１”、”Ｘ１０”で表現される。
【００５０】
図１０の（Ａ）は、通常表現から第２の乗算処理の表現に変換する変換処理におけるレジスタの値の変化を示す変換処理の説明図であり、図１０の（Ｂ）は、第２の乗算処理の表現から通常表現に変換する変換処理におけるレジスタの値の変化を示す変換処理の説明図である。この変換処理は、実質的に通常表現と第１の乗算処理用表現の間の変換と同じであるので、説明は省略する。
【００５１】
実施例の演算装置では、加算処理についても２つの処理方法で行うことが可能である。
【００５２】
図１１は、第１の加算処理におけるレジスタの値の変化を示す第１の加算処理の説明図であり、図１２は第１の加算処理を示すフローチャートである。３２ビット幅の各データについて、図示のような処理が行われる。
【００５３】
図１１に示すように、第１の加算処理では、元０、１、２はそれぞれ”Ｘ００”、”Ｘ１１”、”Ｘ１０”で表現される（Ｘは０または１のどちらでもよい）。図１１に示した処理では、入力の一方は、第１レジスタグループ１１ＸのレジスタＲ０−Ｒ２に格納されたデータであり、入力の他方は第２レジスタグループ１１ＹのレジスタＲ３−Ｒ５に格納されたデータであり、演算結果は第２レジスタグループ１１ＹのレジスタＲ３−Ｒ５に格納される。第１の入力の３ビットのうち、ＸａビットがＲ０に、ＸｂビットがＲ１に、ＸｃビットがＲ２に格納され、第２の入力の３ビットのうち、ＹａビットがＲ３に、ＹｂビットがＲ４に、ＹｃビットがＲ５に格納される。
【００５４】
図１２に示すように、ステップ４０１では、レジスタＲ０の値をレジスタＲ５にコピーする。
【００５５】
ステップ４０２では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ５の値とレジスタＲ４の値のＡＮＤを演算し、演算結果がレジスタＲ５に格納される。
【００５６】
ステップ４０３では、レジスタＲ３の値をレジスタＲ２にコピーする。
【００５７】
ステップ４０４では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ２の値とレジスタＲ０の値のＸＯＲを演算し、演算結果がレジスタＲ２に格納される。
【００５８】
ステップ４０５では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ０の値とレジスタＲ５の値のＸＯＲを演算し、演算結果がレジスタＲ０に格納される。
【００５９】
ステップ４０６では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ３の値とレジスタＲ５の値のＸＯＲを演算し、演算結果がレジスタＲ３に格納される。
【００６０】
ステップ４０７では、３２ビット並列ＯＲ回路１３が、レジスタＲ３の値とレジスタＲ０の値のＯＲを演算し、演算結果がレジスタＲ３に格納される。
【００６１】
ステップ４０８では、３２ビット並列ＯＲ回路１３が、レジスタＲ４の値とレジスタＲ１の値のＯＲを演算し、演算結果がレジスタＲ４に格納される。
【００６２】
ステップ４０９では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ５の値とレジスタＲ２の値のＡＮＤを演算し、演算結果がレジスタＲ５に格納される。
【００６３】
ステップ４１０では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ４の値とレジスタＲ５の値のＸＯＲを演算し、演算結果がレジスタＲ４に格納される。
【００６４】
ステップ４１１では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ３の値とレジスタＲ５の値のＸＯＲを演算し、演算結果がレジスタＲ３に格納される。
【００６５】
各ステップで、各レジスタの値は図１１のように変化する。
【００６６】
以上の処理により、入力のそれぞれの組合せに対して、ＧＦ（３）加算に即した演算結果が得られる。演算結果は、入力と同じ形で表現される。
【００６７】
図１３の（Ａ）は、通常表現から第１の加算処理の表現に変換する変換処理におけるレジスタの値の変化を示す変換処理の説明図であり、図１３の（Ｂ）は、第１の加算処理の表現から通常表現に変換する変換処理におけるレジスタの値の変化を示す変換処理の説明図である。
【００６８】
図１３の（Ａ）に示すように、通常表現から第１の加算処理の表現に変換する変換処理は、図６の（Ａ）および図７の（Ａ）の変換処理においてステップ２０１を除いた処理である。また、図１３の（Ｂ）に示すように、第１の加算処理の表現から通常表現に変換する変換処理は、図６の（Ｂ）および図７の（Ｂ）の変換処理と同じであるので、説明は省略する。
【００６９】
第１の加算処理では、入力は第２の乗算処理の出力と同じ表現であり、第２の乗算処理の出力に対して第１の加算処理で加算を行うのであれば、変換処理は不要である。
【００７０】
図１４及び図１５は、第２の加算処理におけるレジスタの値の変化を示す第２の加算処理の説明図であり、図１６は第２の加算処理を示すフローチャートである。３２ビット幅の各データについて、図示のような処理が行われる。第２の加算処理では、第３レジスタグループ１１ＺのレジスタＲ６およびＲ７も使用される。
【００７１】
図１４および図１５に示すように、第２の加算処理では、元０、１、２はそれぞれ”Ｘ００”、”Ｘ０１”、”Ｘ１０”で表現される（Ｘは０または１のどちらでもよい）。言い換えれば、通常表現と同じ表現である。図１４および図１５に示した処理では、入力の一方は、第１レジスタグループ１１ＸのレジスタＲ０−Ｒ２に格納されたデータであり、入力の他方は第２レジスタグループ１１ＹのレジスタＲ３−Ｒ５に格納されたデータであり、演算結果は第３レジスタグループ１１ＺのレジスタＲ６−Ｒ８（Ｒ８は実際には使用されない）に格納される。第１の入力の３ビットのうち、ＸａビットがＲ０に、ＸｂビットがＲ１に、ＸｃビットがＲ２に格納され、第２の入力の３ビットのうち、ＹａビットがＲ３に、ＹｂビットがＲ４に、ＹｃビットがＲ５に格納される。
【００７２】
図１６に示すように、ステップ６０１では、レジスタＲ３の値をレジスタＲ６にコピーする。
【００７３】
ステップ６０２では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ６の値とレジスタＲ０の値のＸＯＲを演算し、演算結果がレジスタＲ６に格納される。
【００７４】
ステップ６０３では、レジスタＲ４の値をレジスタＲ７にコピーする。
【００７５】
ステップ６０４では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ７の値とレジスタＲ１の値のＸＯＲを演算し、演算結果がレジスタＲ７に格納される。
【００７６】
ステップ６０５では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ１の値とレジスタＲ４の値のＡＮＤを演算し、演算結果がレジスタＲ１に格納される。
【００７７】
ステップ６０６では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ３の値とレジスタＲ０の値のＡＮＤを演算し、演算結果がレジスタＲ３に格納される。
【００７８】
ステップ６０７では、３２ビット並列ＯＲ回路１３が、レジスタＲ７の値とレジスタＲ３の値のＯＲを演算し、演算結果がレジスタＲ７に格納される。
【００７９】
ステップ６０８では、３２ビット並列ＯＲ回路１３が、レジスタＲ６の値とレジスタＲ１の値のＯＲを演算し、演算結果がレジスタＲ６に格納される。
【００８０】
ステップ６０９では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ１の値とレジスタＲ６の値のＸＯＲを演算し、演算結果がレジスタＲ１に格納される。
【００８１】
ステップ６１０では、３２ビット並列ＡＮＤ回路１２が、レジスタＲ１の値とレジスタＲ７の値のＡＮＤを演算し、演算結果がレジスタＲ１に格納される。
【００８２】
ステップ６１１では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ７の値とレジスタＲ１の値のＸＯＲを演算し、演算結果がレジスタＲ７に格納される。
【００８３】
ステップ６１２では、３２ビット並列ＸＯＲ回路１４が、レジスタＲ６の値とレジスタＲ１の値のＸＯＲを演算し、演算結果がレジスタＲ６に格納される。
【００８４】
各ステップで、各レジスタの値は図１１のように変化する。
【００８５】
以上の処理により、入力のそれぞれの組合せに対して、ＧＦ（３）加算に即した演算結果が得られる。演算結果は、入力と同じ形で表現される。
【００８６】
上記のように、第２の加算処理では、元は通常表現で表現されるので、変換処理は必要ない。
【００８７】
ＧＦ（３）の演算では、０の減算は０の加算に等しく、１の減算は２の加算に等しく、２の減算は１の加算に等しい。従って、減算処理は、加算処理において、Ｙ１について”１”を”２”に、”２”を”１”に変換した後加算処理すればよい。
【００８８】
図１７は、第１の加算処理を利用した減算処理のフローチャートを示す。最初のステップ７０１で、３２ビット並列ＸＯＲ回路１４が、レジスタＲ３の値とレジスタＲ４の値のＸＯＲを演算し、演算結果がレジスタＲ３に格納され、それ以後は図１２の第１の加算処理と同じである。
【００８９】
図１８は、第２の加算処理を利用した減算処理のフローチャートを示す。レジスタＲ３をＲ４と、レジスタＲ４をＲ３とみなして図１６の第２の加算処理と同じ処理を行う。
【００９０】
以上、本発明の実施例の演算装置の処理を説明したが、次に従来例と比較して、本発明の効果を説明する。
【００９１】
従来のＧＦ（３）の計算例としては、例えば非特許文献２に記載されている方法がある。非特許文献２では、５．１節に、図１９に示すような通常の２ビット表現を用いたＧＦ（３）の加算と乗算が記載されている。ここで、”Ｈ”は上位ビットを、”Ｌ”は下位ビットを表す。この演算は、本発明の場合と同様に、ビットごとに別レジスタに格納され、図２に示した本発明の演算装置により計算することができる。
【００９２】
図２０は、非特許文献２に記載された従来の乗算処理におけるレジスタの値の変化を示す説明図である。
【００９３】
図２０の詳しい説明は省略するが、従来例の乗算処理では、式の上では６回の論理演算で実現できるが、図２に示したような論理回路の演算装置を使用する場合、第１引数に結果が上書きされるため、最低２回のコピー処理が必要になる。従って、全体では８ステップ必要であり、乗算処理単体では、本発明の第１の乗算処理は６ステップであり、第２の乗算処理は４ステップであり、本発明の方が従来例よりステップ数が少なく速い。通常表現との相互変換を含めた場合は、第１の乗算処理では１１ステップで、第２の乗算処理では９ステップである。これは、２個の入力で４ステップ増加し、１個の出力で１ステップ増加するためである。しかし、べき乗（ａe，ｅ≧２）を計算する場合には、相互変換は最初と最後に行えばよいため、入力の変換に２ステップ、変換後の入力のコピーに３ステップ、出力の変換に１ステップ増加するので、追加は６ステップである。従って、第１の乗算処理では６（ｅ−１）＋６ステップ、第２の乗算処理で（４＋２）（ｅ−１）＋６ステップとなる（１回の乗算で出力表現から入力表現に２ステップ増加する）。従って、従来例の８（ｅ−１）＋２ステップ（入力のコピーで２ステップ増加）に対して、第１および第２の乗算処理とも、ｅ≧４で従来例に比べて高速になる。
【００９４】
図２１は、非特許文献２に記載された従来の加算処理におけるレジスタの値の変化を示す説明図である。
【００９５】
図２１の詳しい説明は省略するが、従来例の加算処理では、式の上では７回の論理演算で実現できるが、図２に示したような論理回路の演算装置を使用する場合、乗算と同様に、最低２回のコピー処理が必要になるため９ステップになる。加算処理単体では、本発明の第１の加算処理は１１ステップであり、第２の加算処理は１２ステップであり、加算処理自体は従来例より遅い。しかし、係数がＧＦ（３）の元である多項式同士の積の場合は、ＧＦ（３）の乗算と加算の両方（積和演算）が実行されるため、全体として高速化され得る（このような多項式同士の積はＧＦ（３）の拡大体ＧＦ（３m）の乗算の途中で使用される）。以下その速度比較を行う。
【００９６】
ＧＦ（３）の元を係数とする２個のｎ−１次多項式を考える。この計算は通常のように項同士の積和演算の繰り返しとなる。例えば、２次多項式の積を考えると図２２の（Ａ）のようになる。
【００９７】
初期状態では、各多項式の係数は通常の表現で４個のレジスタに格納されているものとする。本発明においても従来例においても、乗算層１を並列計算し、その結果に乗算層２の計算結果を加算し、さらにその結果に乗算層３の計算結果を加算する順番となる。なお、例えば、乗算層１の並列計算において、図２２の（Ｂ）に示すように、係数ｆの上位ビットと下位ビットを各々レジスタに展開する手順が必要であるが、このための手間は本発明でも従来例でも同一であり、全体の速度差には関係しない。
【００９８】
本発明の第２の乗算処理と第１の加算処理をｆ（ｘ）＊ｇ（ｘ）の計算に適用すると、第２の乗算処理における３ビット出力表現は第１の加算処理における３ビット入出力表現と同一のため、乗算結果を直接加算処理へ入力できる。
【００９９】
各多項式は、ｎ個の係数を持つが、これを２ビット表現（通常表現）でビット幅Ｗのレジスタに格納するには多項式１個当たり２＊｛ｎ／Ｗ｝（ここで、｛  ｝は小数点以下切り上げを表す）個のレジスタであれば十分である。また、本発明および従来例でのＧＦ（３）の並列計算により多項式の積を計算するには、ＧＦ（３）の並列乗算が｛ｎ／Ｗ｝＊ｎ回、ＧＦ（３）の並列加算が｛ｎ／Ｗ｝＊（ｎ−１）回必要になる。積の結果は２ｎ−１個の項を持つ多項式となる。本発明の第２の乗算処理と第１の加算処理を適用する場合には、２ｎ個の入力項について通常表現から３ビット表現に変換し、多項式の積は３ビット表現で計算し、２ｎ−１個の出力項について３ビット表現から通常表現に変換するものとする。従って、全体の計算ステップ数は図２２の（Ｃ）に示される。
【０１００】
なお、図２２の（Ｃ）の右辺の第４項は、実際にはＶ＊｛（２ｎ−１）／Ｗ｝であるが、式を簡略にするため、本発明に対して不利になるように、図示の式としている。
【０１０１】
これにより、第２の乗算処理と第１の加算処理を適用した本発明と従来例とでステップ数を計算すると、図２２の（Ｄ）のようになる。
【０１０２】
これらのステップ数を比較すると、従来例のステップ数から本発明のステップ数を減じたステップ数は、｛ｎ／Ｗ｝＊［２＊ｎ−４］となり、ｎ≧３で正となる。従って、２次以上の多項式の積では、第２の乗算処理と第１の加算処理を適用した本発明の方が従来例よりも速くなる。
（付記１）
標数が３の有限体ＧＦ（３）の演算方法であって、
前記有限体ＧＦ（３）の３個の元０、１、２を、３ビットで表し、
乗算、加算及び減算の少なくとも１つの演算を、３ビットで表された元で行う、ことを特徴とする有限体ＧＦ（３）の演算方法。
（付記２）
３個の元０、１、２を２ビットで表現した入力を、前記３ビット表現の入力に変換する変換処理を行う付記１に記載の有限体ＧＦ（３）の演算方法。
（付記３）
３ビット表現の出力を、３個の元０、１、２を２ビットで表現した出力に変換する変換処理を行う付記１に記載の有限体ＧＦ（３）の演算方法。
（付記４）
乗算は、入力と出力の３ビット表現が異なる付記１に記載の有限体ＧＦ（３）の演算方法。
（付記５）
乗算と加算及び減算とで、３個の元の３ビット表現が異なる付記１に記載の有限体ＧＦ（３）の演算方法。
（付記６）
第１の入力と第２の入力の乗算は、
３個の元０、１、２を、”０００”、”０１１”、”１１０”で表現し、
第１の入力の０−２ビットをそれぞれ第０から第２レジスタに格納し、
第２の入力の０−２ビットをそれぞれ第３から第５レジスタに格納し、
前記第３レジスタと前記第０レジスタの値のＡＮＤを演算して前記第３レジスタに格納し、
前記第４レジスタと前記第１レジスタの値のＡＮＤを演算して前記第４レジスタに格納し、
前記第５レジスタと前記第２レジスタの値のＡＮＤを演算して前記第５レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＯＲを演算して前記第３レジスタに格納し、
前記第５レジスタと前記第４レジスタの値のＯＲを演算して前記第５レジスタに格納し、
前記第５レジスタと前記第３レジスタの値のＸＯＲを演算して前記第５レジスタに格納し、
前記３から第５レジスタの値を、３個の元０、１、２を、”０００”、”０１１”、”１１０”で表現する出力の０−２ビットとして出力する付記１から３のいずれかに記載の有限体ＧＦ（３）の演算方法。
（付記７）
第１の入力と第２の入力の乗算は、
３個の元０、１、２を、”０００”、”０１１”、”１１０”で表現し、
前記第１の入力の０−２ビットをそれぞれ第０から第２レジスタに格納し、
前記第２の入力の０−２ビットをそれぞれ第３から第５レジスタに格納し、
前記第３レジスタと前記第０レジスタの値のＡＮＤを演算して前記第３レジスタに格納し、
前記第４レジスタと前記第１レジスタの値のＡＮＤを演算して前記第４レジスタに格納し、
前記第５レジスタと前記第２レジスタの値のＡＮＤを演算して前記第５レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＯＲを演算して前記第３レジスタに格納し、
前記３及び第４レジスタの値を、３個の元０、１、２を、”００”、”１１”、”１０”で表現する出力の０−１ビットとして出力する付記１から４のいずれかに記載の有限体ＧＦ（３）の演算方法。
（付記８）
第１の入力と第２の入力の加算は、
前記３個の元０、１、２を、”Ｘ００”、”Ｘ１１”、”Ｘ１０”（Ｘは０と１のいずれも可）で表現し、
前記第１の入力の０−２ビットをそれぞれ第０から第２レジスタに格納し、
前記第２の入力の０−２ビットをそれぞれ第３から第５レジスタに格納し、
前記第１レジスタの値を第５レジスタに格納し、
前記第５レジスタと前記第４レジスタの値のＡＮＤを演算して第５レジスタに格納し、
前記第３レジスタの値を第２レジスタに格納し、
前記第２レジスタと前記第０レジスタの値のＸＯＲを演算して第２レジスタに格納し、
前記第０レジスタと前記第５レジスタの値のＸＯＲを演算して第０レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＸＯＲを演算して第３レジスタに格納し、
前記第３レジスタと前記第０レジスタの値のＯＲを演算して第３レジスタに格納し、
前記第４レジスタと前記第１レジスタの値のＯＲを演算して第４レジスタに格納し、
前記第５レジスタと前記第２レジスタの値のＡＮＤを演算して第５レジスタに格納し、
前記第４レジスタと前記第５レジスタの値のＸＯＲを演算して第４レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＸＯＲを演算して第３レジスタに格納し、
前記６及び第７レジスタの値を、前記３個の元０、１、２を、”００”、”１１”、”１０”で表現する出力の０−１ビットとして出力する付記１から３のいずれかに記載の有限体ＧＦ（３）の演算方法。
（付記９）
０の減算は０の加算とし、１の減算は２の加算とし、２の減算は１の加算として行われる付記８に記載の有限体ＧＦ（３）の演算方法。
（付記１０）
多項式の積の演算は、付記７に記載の演算方法における乗算を行い、その結果を入力として、付記８に記載の演算方法による加算または減算により行われる有限体ＧＦ（３）の演算方法。
（付記１１）
２グループで構成され、各グループが３個のレジスタで構成される合計６個のレジスタ群と、前記６個のレジスタの２個の値を入力としてＡＮＤ、ＯＲ、ＸＯＲ及びコピー処理を行い、処理結果を前記２個の入力の一方のレジスタに格納するように構成された演算回路と、を備える標数が３の有限体ＧＦ（３）の演算装置であって、
乗算、加算及び減算の少なくとも１つの演算は、有限体ＧＦ（３）の３個の元０、１、２を、３ビットで表し、
第１の入力の０−２ビットを第１のグループの第０から第２レジスタにそれぞれ格納し、
第２の入力の０−２ビットを第２のグループの第３から第５レジスタにそれぞれ格納して演算を行うことを特徴とする有限体ＧＦ（３）の演算装置。
（付記１２）
３個の元０、１、２を２ビットで表現した入力を、前記第１のグループの前記第０から第２レジスタまたは前記第２のグループの前記第３から第５レジスタに入力し、上記３ビット表現に変換する変換処理を行う付記１１に記載の有限体ＧＦ（３）の演算装置。
（付記１３）
前記第１のグループの前記第０から第２レジスタまたは前記第２のグループの前記第３から第５レジスタに格納された３ビット表現の出力を、３個の元０、１、２を２ビットで表現した出力に変換する変換処理を行う付記１１に記載の有限体ＧＦ（３）の演算装置。
（付記１４）
乗算は、入力と出力の３ビット表現が異なる付記１１に記載の有限体ＧＦ（３）の演算装置。
（付記１５）
乗算と加算及び減算で、３個の元の３ビット表現が異なる付記１１に記載の有限体ＧＦ（３）の演算装置。
（付記１６）
第１の入力と第２の入力の乗算は、
３個の元０、１、２を、”０００”、”０１１”、”１１０”で表現し、
前記第１の入力の０−２ビットをそれぞれ前記第０から第２レジスタに格納し、
前記第２の入力の０−２ビットをそれぞれ前記第３から第５レジスタに格納し、
前記第３レジスタと前記第０レジスタの値のＡＮＤを演算して前記第３レジスタに格納し、
前記第４レジスタと前記第１レジスタの値のＡＮＤを演算して前記第４レジスタに格納し、
前記第５レジスタと前記第２レジスタの値のＡＮＤを演算して前記第５レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＯＲを演算して前記第３レジスタに格納し、
前記第５レジスタと前記第４レジスタの値のＯＲを演算して前記第５レジスタに格納し、
前記第５レジスタと前記第３レジスタの値のＸＯＲを演算して前記第５レジスタに格納し、
前記３から第５レジスタの値を、３個の元０、１、２を、”０００”、”０１１”、”１１０”で表現する出力の０−２ビットとして出力する付記１１から１３のいずれかに記載の有限体ＧＦ（３）の演算装置。
（付記１７）
第１の入力と第２の入力の乗算は、
前記３個の元０、１、２を、”０００”、”０１１”、”１１０”で表現し、
前記第１の入力の０−２ビットをそれぞれ第０から第２レジスタに格納し、
前記第２の入力の０−２ビットをそれぞれ第３から第５レジスタに格納し、
前記第３レジスタと前記第０レジスタの値のＡＮＤを演算して第３レジスタに格納し、
前記第４レジスタと前記第１レジスタの値のＡＮＤを演算して第４レジスタに格納し、
前記第５レジスタと前記第２レジスタの値のＡＮＤを演算して第５レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＯＲを演算して第３レジスタに格納し、
前記３及び第４レジスタの値を、前記３個の元０、１、２を、”００”、”１１”、”１０”で表現する出力の０−１ビットとして出力する付記１１から１４のいずれかに記載の有限体ＧＦ（３）の演算装置。
（付記１８）
３個の元０、１、２を２ビットで表現した入力を、前記第１のグループの前記第０および第１レジスタまたは前記第２のグループの前記第３および第４レジスタに入力し、
前記第１レジスタまたは前記第４レジスタの値を、前記第２レジスタまたは第５レジスタに格納し、
前記第１レジスタと前記第０レジスタの値のＯＲまたは前記第４レジスタと前記第３レジスタの値のＯＲを演算して前記第１レジスタまたは第４レジスタに格納し、
前記第１のグループの前記第０から第２レジスタまたは前記第２のグループの前記第３から第５レジスタに格納された値を、入力として演算を行う付記１６または１７に記載の有限体ＧＦ（３）の演算装置。
（付記１９）
前記第１のグループの前記第０から第２レジスタまたは前記第２のグループの前記第３から第５レジスタに格納された３ビット表現の出力に対して、
前記第１レジスタと前記第０レジスタの値のＸＯＲまたは前記第４レジスタと前記第３レジスタの値のＸＯＲを演算して前記第１レジスタまたは前記第４レジスタに格納し、
前記第１のグループの前記第０及び第１レジスタまたは前記第２のグループの前記第３及び第４レジスタに格納された値を、２ビットで表現した出力として出力する付記１６または１７に記載の有限体ＧＦ（３）の演算装置。
（付記２０）
第１の入力と第２の入力の加算は、
前記３個の元０、１、２を、”Ｘ００”、”Ｘ１１”、”Ｘ１０”（Ｘは０と１のいずれも可）で表現し、
前記第１の入力の０−２ビットをそれぞれ第０から第２レジスタに格納し、
前記第２の入力の０−２ビットをそれぞれ第３から第５レジスタに格納し、
前記第１レジスタの値を第５レジスタに格納し、
前記第５レジスタと前記第４レジスタの値のＡＮＤを演算して第５レジスタに格納し、
前記第３レジスタの値を第２レジスタに格納し、
前記第２レジスタと前記第０レジスタの値のＸＯＲを演算して第２レジスタに格納し、
前記第０レジスタと前記第５レジスタの値のＸＯＲを演算して第０レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＸＯＲを演算して第３レジスタに格納し、
前記第３レジスタと前記第０レジスタの値のＯＲを演算して第３レジスタに格納し、
前記第４レジスタと前記第１レジスタの値のＯＲを演算して第４レジスタに格納し、
前記第５レジスタと前記第２レジスタの値のＡＮＤを演算して第５レジスタに格納し、
前記第４レジスタと前記第５レジスタの値のＸＯＲを演算して第４レジスタに格納し、
前記第３レジスタと前記第５レジスタの値のＸＯＲを演算して第３レジスタに格納し、
前記６及び第７レジスタの値を、前記３個の元０、１、２を、”００”、”１１”、”１０”で表現する出力の０−１ビットとして出力する付記１１から１３のいずれか１項に記載の有限体ＧＦ（３）の演算装置。
（付記２１）
３個の元０、１、２を２ビットで表現した入力を、前記第１のグループの前記第０および第１レジスタまたは前記第２のグループの前記第３および第４レジスタに入力し、
前記第１レジスタと前記第０レジスタの値のＯＲまたは前記第４レジスタと前記第３レジスタの値のＯＲを演算して前記第１レジスタまたは第４レジスタに格納し、
前記第１のグループの前記第０から第２レジスタまたは前記第２のグループの前記第３から第５レジスタに格納された値を、入力として演算を行う付記２０に記載の有限体ＧＦ（３）の演算装置。
（付記２２）
前記第１のグループの前記第０から第２レジスタまたは前記第２のグループの前記第３から第５レジスタに格納された３ビット表現の出力に対して、
前記第１レジスタと前記第０レジスタの値のＸＯＲまたは前記第４レジスタと前記第３レジスタの値のＸＯＲを演算して前記第１レジスタまたは前記第４レジスタに格納し、
前記第１のグループの前記第０及び第１レジスタまたは前記第２のグループの前記第３及び第４レジスタに格納された値を、２ビットで表現した出力として出力する付記２０に記載の有限体ＧＦ（３）の演算装置。
（付記２３）
ＡＮＤ、ＯＲ、ＸＯＲ及びコピー処理を行える第６から第７の２個のレジスタで構成される第３グループのレジスタ群をさらに備え、
第１の入力と第２の入力の加算は、
前記３個の元０、１、２を、”Ｘ００”、”Ｘ０１”、”Ｘ１０”（Ｘは０と１のいずれも可）で表現し、
前記第１の入力の０−２ビットをそれぞれ第０から第２レジスタに格納し、
前記第２の入力の０−２ビットをそれぞれ第３から第５レジスタに格納し、
前記第３レジスタの値を第６レジスタに格納し、
前記第６レジスタと前記第０レジスタの値のＸＯＲを演算して第６レジスタに格納し、
前記第４レジスタの値を第７レジスタに格納し、
前記第７レジスタと前記第１レジスタの値のＸＯＲを演算して第７レジスタに格納し、
前記第１レジスタと前記第４レジスタの値のＡＮＤを演算して第１レジスタに格納し、
前記第３レジスタと前記第０レジスタの値のＡＮＤを演算して第３レジスタに格納し、
前記第７レジスタと前記第３レジスタの値のＯＲを演算して第７レジスタに格納し、
前記第６レジスタと前記第１レジスタの値のＯＲを演算して第６レジスタに格納し、
前記第１レジスタと前記第６レジスタの値のＸＯＲを演算して第１レジスタに格納し、
前記第１レジスタと前記第７レジスタの値のＡＮＤを演算して第１レジスタに格納し、
前記第７レジスタと前記第１レジスタの値のＸＯＲを演算して第７レジスタに格納し、
前記第６レジスタと前記第１レジスタの値のＸＯＲを演算して第６レジスタに格納し、
前記６及び第７レジスタの値を、前記３個の元０、１、２を、”００”、”０１”、”１０”で表現する出力の０−１ビットとして出力する付記１１に記載の有限体ＧＦ（３）の演算装置。
（付記２４）
０の減算は０の加算とし、１の減算は２の加算とし、２の減算は１の加算として行われる付記１１、２０から２３のいずれか１項に記載の有限体ＧＦ（３）の演算装置。
（付記２５）
多項式の積の演算は、付記１７に記載の乗算を行い、その結果を入力として、付記２０に記載の加算または減算により行われる有限体ＧＦ（３）の演算装置。
（付記２６）
前記第０から第５レジスタは、３２ビット長を有し、３２個の演算が並列に行われる付記１１から２５のいずれか１項に記載の有限体ＧＦ（３）の演算装置。
（付記２７）
前記第６および第７レジスタは、３２ビット長を有し、３２個の演算が並列に行われる付記２３に記載の有限体ＧＦ（３）の演算装置。
【産業上の利用可能性】
【０１０３】
本発明は、標数３の有限体（ガロア体）演算を使用する場合には、どのような場合にも適用可能である。
【図面の簡単な説明】
【０１０４】
【図１】有限体（ガロア体）ＧＦ（３）の演算規則を示す図である。
【図２】本発明の実施例のＧＦ（３）演算装置のハードウェア構成図である。
【図３】実施例の演算装置の動作を示す図である。
【図４】実施例の第１の乗算処理の説明図である。
【図５】第１の乗算処理のフローチャートである。
【図６】第１の乗算処理用変換処理の説明図である。
【図７】第１の乗算処理用変換処理のフローチャートである。
【図８】実施例の第２の乗算処理の説明図である。
【図９】第２の乗算処理のフローチャートである。
【図１０】第２の乗算処理用変換処理の説明図である。
【図１１】実施例の第１の加算処理の説明図である。
【図１２】第１の加算処理のフローチャートである。
【図１３】第１の加算処理用変換処理の説明図である。
【図１４】実施例の第２の加算処理の説明図である。
【図１５】実施例の第２の加算処理の説明図である。
【図１６】第２の加算処理のフローチャートである。
【図１７】第１の加算処理に基づく減算処理のフローチャートである。
【図１８】第２の加算処理に基づく減算処理のフローチャートである。
【図１９】従来の演算の基本説明図である。
【図２０】従来の乗算処理の説明図である。
【図２１】従来の加算処理の説明図である。
【図２２】本発明と従来例の比較である。
【符号の説明】
【０１０５】
１１Ｘ    第１レジスタグループ
１１Ｙ    第２レジスタグループ
１１Ｚ    第３レジスタグループ
１２    ３２ビット並列ＡＮＤ回路
１３    ３２ビット並列ＯＲ回路
１４    ３２ビット並列ＸＯＲ回路
１５    ３２ビット並列ＣＯＰＹ回路
１６    制御部
１７、１８、１９    バス
Ｒ０−Ｒ８    レジスタ
【図１】
2008134812.tif 000003
【図２】
2008134812.tif 000004
【図３】
2008134812.tif 000005
【図４】
2008134812.tif 000006
【図５】
2008134812.tif 000007
【図６】
2008134812.tif 000008
【図７】
2008134812.tif 000009
【図８】
2008134812.tif 000010
【図９】
2008134812.tif 000011
【図１０】
2008134812.tif 000012
【図１１】
2008134812.tif 000013
【図１２】
2008134812.tif 000014
【図１３】
2008134812.tif 000015
【図１４】
2008134812.tif 000016
【図１５】
2008134812.tif 000017
【図１６】
2008134812.tif 000018
【図１７】
2008134812.tif 000019
【図１８】
2008134812.tif 000020
【図１９】
2008134812.tif 000021
【図２０】
2008134812.tif 000022
【図２１】
2008134812.tif 000023
【図２２】
2008134812.tif 000024