(57)【要約】【課題】複数の有限体でそれぞれ定義された複数の演算を行う演算回路を小規模に構成できる回路構成方法を提供する。【解決手段】演算回路２内の乗算回路３，４，５，６を、第１および第２の乗算回路構成方法のうちその演算回路を小規模に構成する乗算回路構成方法を選択して構成する。乗算回路４は、ＸＯＲおよびＡＮＤ回路を用いてそれぞれ加算および乗算を行って所定の乗算を行う。乗算回路５は、乗算回路および加算回路を用いて所定の乗算を行う。【選択図】      図１
2004164391.tif 000002
【特許請求の範囲】
【請求項１】
第１の有限体上で定義された少なくとも２つの第１の演算および第２の演算を用いて前記第１の有限体の拡大である第２の有限体上で定義された第３の演算が規定される場合に、前記第３の演算を行う演算回路を構成する演算回路構成方法であって、
複数の回路構成方法のうち、前記第１の演算を行う第１の演算回路と前記第２の演算を行う第２の演算回路とのうち回路規模が大きい演算回路が行う前記演算をより少ない個数用いて前記第３の演算を規定する前記回路構成方法を選択する第１の工程と、
前記第１の工程で選択した前記回路構成方法による前記第３の演算の規定に基づいて、前記第１の演算回路および前記第２の演算回路を用いて前記第３の演算を行う前記演算回路を構成する第２の工程と
を有する演算回路構成方法。
【請求項２】
前記第１の有限体および前記第２の有限体は、下記（１）で定義される有限体である
【数１】
2004164391.tif 000027
請求項１に記載の回路構成方法。
【請求項３】
前記第２の有限体を下記（２−１）で示し、当該有限体の元Ａ，Ｂを下記（２−２）で定義されるｍ２  次拡大についての原始根αを用いて下記（２−３）のように定義し、前記原始根αを下記（２−４）で定義し、上記式（２−３）に応じて下記（２−５）で示される前記第１の有限体上のｍ２  次ベクトルをそれぞれ下記（２−６），（２−７）で定義した場合に、
前記第１の工程において、
上記（２−６），（２−７）で定義されるｍ２  次ベクトルを用いて、下記式（２−８）で定義される演算を行ってＣＫ  を算出し、当該算出されたＣＫ  を基に定義された下記式（２−９）に基づいて前記第３の演算としての乗算を行う乗算回路を構成する第１の前記回路構成方法と、
上記（２−１）で示される前記第２の有限体の元Ａ，Ｂを下記式（２−１０）で定義し、下記（２−１０）内のＡｌ，Ａｈ，Ａｌ，Ｂｈを下記（２−１１）で定義し、ｔを下記（２−１２）で定義し、上記（２−６），（２−７）で定義されるｍ２  次ベクトルを用いて下記式（２−１３），（２−１４），（２−１５）で定義される演算を行ってそれぞれＤ０  ，Ｄ１  ，Ｄ２  を算出し、当該算出されたＤ０  ，Ｄ１  ，Ｄ２  を用いて下記式（２−１６）に基づいて前記第３の演算としての乗算を行う乗算回路を構成する第２の前記回路構成方法と
のうち、
一つの前記回路構成方法を選択する
請求項２に記載の演算回路構成方法。
【数２】
2004164391.tif 000028
【数３】
2004164391.tif 000029
【数４】
2004164391.tif 000030
【数５】
2004164391.tif 000031
【数６】
2004164391.tif 000032
【数７】
2004164391.tif 000033
【数８】
2004164391.tif 000034
【数９】
2004164391.tif 000035
【数１０】
2004164391.tif 000036
【数１１】
2004164391.tif 000037
【数１２】
2004164391.tif 000038
【数１３】
2004164391.tif 000039
【数１４】
2004164391.tif 000040
【請求項４】
前記第１の工程において、ｑ＝２、ｍ１  ＝１である場合に、前記第１の回路構成方法を選択する
請求項３に記載の演算回路構成方法。
【請求項５】
前記第１の工程において、ｑ＝２，ｍ１  ＞１である場合に、前記第２の回路構成方法を選択する
請求項３に記載の演算回路構成方法。
【請求項６】
第１の有限体上で定義された少なくとも２つの第１の演算および第２の演算を用いて前記第１の有限体の拡大である第２の有限体上で定義された第３の演算が規定される場合に、前記第３の演算を行う演算回路を構成する演算回路構成装置であって、
複数の回路構成方法のうち、前記第１の演算を行う第１の演算回路と前記第２の演算を行う第２の演算回路とのうち回路規模が大きい演算回路が行う前記演算をより少ない個数用いて前記第３の演算を規定する前記回路構成方法を選択する選択手段と、
前記選択手段が選択した前記回路構成方法による前記第３の演算の規定に基づいて、前記第１の演算回路および前記第２の演算回路を用いて前記第３の演算を行う前記演算回路を構成する回路構成手段と
を有する演算回路構成装置。
【請求項７】
第１の有限体上で定義された少なくとも２つの第１の演算および第２の演算を用いて前記第１の有限体の拡大である第２の有限体上で定義された第３の演算が規定される場合に、前記第３の演算を行う演算回路を構成する演算回路構成装置が実行するプログラムであって、
複数の回路構成方法のうち、前記第１の演算を行う第１の演算回路と前記第２の演算を行う第２の演算回路とのうち回路規模が大きい演算回路が行う前記演算をより少ない個数用いて前記第３の演算を規定する前記回路構成方法を選択する第１の手順と、
前記第１の手順で選択した前記回路構成方法による前記第３の演算の規定に基づいて、前記第１の演算回路および前記第２の演算回路を用いて前記第３の演算を行う前記演算回路を構成する第２の手順と
を有するプログラム。
【請求項８】
異なる複数の有限体上でそれぞれ定義された複数の演算を、それぞれの有限体に適合した異なる複数の演算回路構成方法を基に規定された構成でそれぞれ行う複数の演算回路
を有する演算回路。
【請求項９】
第１の前記有限体上で定義された演算を行う第１の前記演算回路を用いて構成され、前記第１の有限体の拡大である第２の前記有限体上で定義された演算を行う第２の前記演算回路
を有する請求項８に記載の演算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、有限体の演算に係わる演算回路構成方法、その方法、そのプログラムおよび演算回路に関する。
【０００２】
【従来の技術】
例えば、ハミング符号などの誤り訂正符号や復号では、例えば、下記（３−１）で定義される有限体上で定義された乗算や逆元生成演算などの種々の演算が行われる。
【０００３】
【数１５】
2004164391.tif 000003
【０００４】
上記（３−１）でｑ＝２とした下記（３−２）の有限体は、２ｍ  個の元からなる集合であり、各々の元は指数表現またはベクトル表現で表現される。
【０００５】
【数１６】
2004164391.tif 000004
【０００６】
図１１は、種々の有限体上で定義された乗算を行う複数の乗算回路を有する演算回路１０２を説明するための図である。
図１１に示す演算回路１０２は、第１の有限体、第２の有限体および第３の有限体上で定義された乗算回路を有し、ベクトルデータＤ＿ＩＮを入力して所定の演算を行い、ベクトルデータＤ＿ＯＵＴを出力する。
第１の有限体は下記（３−３）で示され、第２の有限体は下記（３−４）で示され、第３の有限体は下記（３−５）で示される。
ここで、第１、第２および第３の有限体には、第１、第２および第３の有限体の順で、下位から上位となる拡大の関係がある。
【０００７】
【数１７】
2004164391.tif 000005
【０００８】
【数１８】
2004164391.tif 000006
【０００９】
【数１９】
2004164391.tif 000007
【００１０】
図１１に示す演算回路１０２は、第３の有限体上で定義された乗算を行う乗算回路１０５と、第２の有限体上で定義された乗算を行う乗算回路１０６とを有する。
乗算回路１０５は、第２の有限体上で定義された乗算を行う乗算回路１０４を有し、乗算回路１０４は第１の有限体上で定義された乗算を行う乗算回路１０３を有する。
【００１１】
乗算回路は、例えば、当該乗算回路が行う乗算が定義された有限体の特性に応じて、当該有限体の下位の有限体の乗算回路および加算回路などの演算回路を用いて構成される。
ところで、乗算回路を構成する乗算回路構成方法には、種々の乗算回路構成方法がある。
従来では、演算回路１０２を構成（設計）する場合に、乗算回路１０３〜１０６を含む演算回路１０２全体について同じ乗算回路構成方法ＣＭ１を基に回路を構成している。
【００１２】
【発明が解決しようとする課題】
しかしながら、乗算回路を構成する種々の演算回路の規模および個数は、当該乗算回路の乗算が定義されている有限体の特性に応じて異なるため、上述したように、演算回路１０２全体について同じ乗算回路構成方法ＣＭ１を基に回路を構成すると、回路規模などの観点から演算回路１０２を効率的に構成できず、演算回路１０２を大規模化してしまう場合があるという問題がある。
同様な問題は、逆元生成回路などのその他の演算回路を含む演算回路を構成する場合にも生じる。
【００１３】
本発明はかかる事情に鑑みてなされたものであり、複数の有限体でそれぞれ定義された複数の演算を行う演算回路を小規模に構成できる回路構成方法、その装置、そのプログラムおよび演算回路を提供することを目的とする。
【００１４】
【課題を解決するための手段】
上記の目的を達成するため、第１の発明の演算回路構成方法は、第１の有限体上で定義された少なくとも２つの第１の演算および第２の演算を用いて前記第１の有限体の拡大である第２の有限体上で定義された第３の演算が規定される場合に、前記第３の演算を行う演算回路を構成する演算回路構成方法であって、複数の回路構成方法のうち、前記第１の演算を行う第１の演算回路と前記第２の演算を行う第２の演算回路とのうち回路規模が大きい演算回路が行う前記演算をより少ない個数用いて前記第３の演算を規定する前記回路構成方法を選択する第１の工程と、前記第１の工程で選択した前記回路構成方法による前記第３の演算の規定に基づいて、前記第１の演算回路および前記第２の演算回路を用いて前記第３の演算を行う前記演算回路を構成する第２の工程とを有する。
【００１５】
第１の発明の演算回路構成方法では、第１の工程において、複数の回路構成方法のうち、前記第１の演算を行う第１の演算回路と前記第２の演算を行う第２の演算回路とのうち回路規模が大きい演算回路が行う前記演算をより少ない個数用いて前記第３の演算を規定する前記回路構成方法を選択する。
次に、第２の工程において、前記第１の工程で選択した前記回路構成方法による前記第３の演算の規定に基づいて、前記第１の演算回路および前記第２の演算回路を用いて前記第３の演算を行う前記演算回路を構成する。
【００１６】
第２の発明の演算回路構成装置は、第１の有限体上で定義された少なくとも２つの第１の演算および第２の演算を用いて前記第１の有限体の拡大である第２の有限体上で定義された第３の演算が規定される場合に、前記第３の演算を行う演算回路を構成する演算回路構成装置であって、複数の回路構成方法のうち、前記第１の演算を行う第１の演算回路と前記第２の演算を行う第２の演算回路とのうち回路規模が大きい演算回路が行う前記演算をより少ない個数用いて前記第３の演算を規定する前記回路構成方法を選択する選択手段と、前記選択手段が選択した前記回路構成方法による前記第３の演算の規定に基づいて、前記第１の演算回路および前記第２の演算回路を用いて前記第３の演算を行う前記演算回路を構成する回路構成手段とを有する。
【００１７】
第２の発明の演算回路構成装置では、選択手段が、複数の回路構成方法のうち、前記第１の演算を行う第１の演算回路と前記第２の演算を行う第２の演算回路とのうち回路規模が大きい演算回路が行う前記演算をより少ない個数用いて前記第３の演算を規定する前記回路構成方法を選択する。
次に、回路構成手段が、前記選択手段が選択した前記回路構成方法による前記第３の演算の規定に基づいて、前記第１の演算回路および前記第２の演算回路を用いて前記第３の演算を行う前記演算回路を構成する。
【００１８】
第３の発明のプログラムは、第１の有限体上で定義された少なくとも２つの第１の演算および第２の演算を用いて前記第１の有限体の拡大である第２の有限体上で定義された第３の演算が規定される場合に、前記第３の演算を行う演算回路を構成する演算回路構成装置が実行するプログラムであって、複数の回路構成方法のうち、前記第１の演算を行う第１の演算回路と前記第２の演算を行う第２の演算回路とのうち回路規模が大きい演算回路が行う前記演算をより少ない個数用いて前記第３の演算を規定する前記回路構成方法を選択する第１の手順と、前記第１の手順で選択した前記回路構成方法による前記第３の演算の規定に基づいて、前記第１の演算回路および前記第２の演算回路を用いて前記第３の演算を行う前記演算回路を構成する第２の手順とを有する。
【００１９】
第４の発明の演算回路は、異なる複数の有限体上でそれぞれ定義された複数の演算を、それぞれの有限体に適合した異なる複数の演算回路構成方法を基に規定された構成でそれぞれ行う複数の演算回路を有する。
【００２０】
【発明の実施の形態】
〔本発明の関連技術〕
以下、乗算回路の構成方法について説明する。
乗算演算が定義されている第２の有限体を下記（４−１）で示し、当該第２有限体の元Ａ，Ｂを下記（４−２）で定義されるｍ２  次拡大についての原始根αを用いて下記（４−３）のように定義する場合を考える。
この場合に、原始根αは、下記（４−４）のように定義される。下記（４−４）において、ｍｏｎｉｃは、多項式の最高次の項の係数が１であることを示している。
【００２１】
【数２０】
2004164391.tif 000008
【００２２】
【数２１】
2004164391.tif 000009
【００２３】
【数２２】
2004164391.tif 000010
【００２４】
【数２３】
2004164391.tif 000011
【００２５】
上記式（４−３）を基に下記（４−５）で示される第１の有限体上のｍ２  次ベクトルを、下記（４−６），（４−７）で定義する。
【００２６】
【数２４】
2004164391.tif 000012
【００２７】
【数２５】
2004164391.tif 000013
【００２８】
第１の乗算回路構成方法では、以下に示すように、乗算回路を構成する。
すなわち、第１の乗算回路構成方法では、上記（４−６），（４−７）で定義されるｍ２  次ベクトルを入力として、下記式（４−８）で定義される演算を行ってＣＫ  を算出するように乗算回路を構成する。
【００２９】
【数２６】
2004164391.tif 000014
【００３０】
また、上記式（４−８）で定義される演算によって算出されたＣＫ  を用いて定義された下記式（４−９）に基づいて演算を行うように乗算回路を構成する。
すなわち、下記式（４−９）において、α以外の部分に係わる演算を、上記（４−５）で示される有限体上の演算回路を用いて構成する。
【００３１】
【数２７】
2004164391.tif 000015
【００３２】
また、第２の乗算回路構成方法では、以下に示すように、乗算回路を構成する。
当該第２の乗算回路構成方法は、Ｃｈｒｉｓｔｏｆ  Ｐａａｒ  著、Ａ  Ｎｅｗ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒａ  Ｐａｒａｌｌｅｌ  Ｆｉｎｉｔｅ  Ｆｉｅｌｄ  Ｍｕｌｔｉｐｌｉｅｒ  ｗｉｔｈ  Ｌｏｗ  Ｃｏｍｐｌｅｘｉｔｙ  Ｂａｓｅｄ  ｏｎ  Ｃｏｍｐｏｓｉｔｅ  Ｆｉｅｌｄｓ，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，  Ｖｏｌ．４５，  Ｎｏ．７，Ｊｕｌｙ  １９９６，  Ｐ８５６−Ｐ８６１などに開示されている方法である。
すなわち、当該第２の乗算回路構成方法では、上記（４−１）〜（４−７）に基づいて、上記（４−１）で示される第２の有限体の元Ａ，Ｂを下記（４−１０）のように定義する。
【００３３】
【数２８】
2004164391.tif 000016
【００３４】
また、上記（４−１０）内のＡｌ，Ａｈ，Ａｌ，Ｂｈを、下記（４−１１）のように定義し、ｔを下記（４−１２）のように定義する。
【００３５】
【数２９】
2004164391.tif 000017
【００３６】
【数３０】
2004164391.tif 000018
【００３７】
そして、上記（４−６），（４−７）で定義されるｍ２  次ベクトルを入力として、下記式（４−１３），（４−１４），（４−１５）で定義される演算を行ってそれぞれＤ０  ，Ｄ１  ，Ｄ２  を算出するように乗算回路を構成する。
【００３８】
【数３１】
2004164391.tif 000019
【００３９】
そして、上記式（４−１３），（４−１４），（４−１５）で定義される上記演算によって算出されたＤ０  ，Ｄ１  ，Ｄ２  を用いて定義された下記式（４−１６）に基づいて、乗算回路を構成する。
すなわち、下記式（４−１６）において、α以外の部分に係わる演算を、上記（４−５）で示される第１の有限体上の演算回路を用いて構成する。
【００４０】
【数３２】
2004164391.tif 000020
【００４１】
〔発明の実施の形態〕
図１は、本発明の実施形態の演算回路構成方法によって構成される演算回路２を説明するための図である。
図１に示す演算回路２は、第３の有限体上で定義された乗算を行う乗算回路５と、第２の有限体上で定義された乗算を行う乗算回路６とを有する。
乗算回路５は、第２の有限体上で定義された乗算を行う乗算回路４を有し、乗算回路４は第１の有限体上で定義された乗算を行う乗算回路３を有する。
【００４２】
本実施形態では、第１、第２および第３の有限体をそれぞれｑ＝２として下記（５−１），（５−２），（５−３）で定義する。すなわち、第２の有限体は第１の有限体の拡大であり、第３の有限体は第２の有限体の拡大である。
また、本実施形態では、ｍ１＝１，ｍ２＞２、ｍ３≧１とする。
【００４３】
【数３３】
2004164391.tif 000021
【００４４】
【数３４】
2004164391.tif 000022
【００４５】
【数３５】
2004164391.tif 000023
【００４６】
本実施形態において、回路構成の対象となる乗算は、例えば、上記（４−６），（４−７）で定義されるｍ２  次ベクトルの乗算である。
本実施形態では、回路構成の対象となる乗算（第３の演算）が定義される有限体の下位の有限体上での加算（第１の演算）が排他的論理和演算で実現され、乗算（第２の演算）が論理積演算で実現される場合に、すなわち下位の有限体の拡大次数が１の場合（例えば、第１の有限体である場合）に、上記第１の乗算回路構成方法ＣＭ１を選択して、排他的論理和（ＸＯＲ）演算回路および論理積（ＡＮＤ）演算回路を用いて、上記対象となる乗算を行う乗算回路（例えば、乗算回路４）を構成する。
ここで、排他的論理和演算回路の方が論理積演算回路より回路規模が大きく、第１の乗算回路構成方法を選択することで、第２の乗算回路構成方法を選択した場合に比べて排他的論理和演算回路の数を削減できる。これにより、対象となる乗算を行う乗算回路を小規模化に実現できる。
また、本実施形態では、対象となる乗算（第３の演算）が定義される有限体の下位の有限体上での加算（第１の演算）がＸＯＲ回路でない加算回路で実現され、乗算（第２の演算）がＡＮＤ回路でない乗算回路で実現される場合に、すなわち下位の有限体の拡大次数が２以上の場合（例えば、第２の有限体である場合）に、上記第２の乗算回路構成方法ＣＭ２を選択して、加算回路および乗算回路を用いて、上記対象となる乗算を行う乗算回路（例えば、乗算回路５）を構成する。
ここで、乗算回路の方が加算回路より回路規模が大きく、第２の乗算回路構成方法を選択することで、第１の乗算回路構成方法を選択した場合に比べて乗算回路の数を削減できる。これにより、対象となる乗算を行う乗算回路を小規模化に実現できる。
【００４７】
また、乗算回路３、６は、共に上記第１の乗算回路構成方法ＣＭ１を選択して構成する。
【００４８】
図２は、本実施形態の乗算回路構成方法を実行するコンピュータ２９（本発明の演算回路構成装置）の構成図である。
図２に示すように、コンピュータ２９は、例えば、操作部３１、ディスプレイ３２、メモリ３３およびＣＰＵ３４を有し、これらがバス３０を介して接続されている。
操作部３１は、キーボードやマウスなどの操作手段であり、ユーザの操作に応じた操作信号をＣＰＵ３４に出力する。
ディスプレイ３２は、ＣＰＵ３４による回路構成の処理に応じた画面を表示する。
メモリ３３は、ＣＰＵ３４の処理に用いられるプログラム４１（本発明のプログラム）およびデータ４２を記憶する。
【００４９】
ＣＰＵ３４は、プログラム４１を実行し、データ４２を用いて、以下に示すように演算回路２を構成（設計）する。
ＣＰＵ３４が、本発明の選択手段および回路構成手段を実現する。
【００５０】
図３は、ＣＰＵ３４が演算回路２内の各乗算回路を構成する場合の動作例を説明するためのフローチャートである。
ステップＳＴ１：
ＣＰＵ３４が、上記第１の乗算回路構成方法および上記第２の乗算回路構成方法のうち、上記第１の演算（乗算）を行う演算回路と上記第２の演算（加算）を行う演算回路とのうち回路規模が大きい演算回路の演算をより少ない個数用いて、対象となる乗算（第３の演算）を規定する乗算回路構成方法を選択する。
具体的には、ＣＰＵ３４が、対象となる乗算が規定される有限体の下位の有限体の拡大次数が１の場合（例えば、第１の有限体である場合）に、上記第１の乗算回路構成方法ＣＭ１を選択する。
また、ＣＰＵ３４が、対象となる乗算が定義される有限体の下位の有限体の拡大次数が２以上の場合（例えば、第２の有限体である場合）に、上記第２の乗算回路構成方法ＣＭ２を選択する。
【００５１】
ステップＳＴ２：
ＣＰＵ３４が、ステップＳＴ１で第１の乗算回路構成方法を選択したと判断した場合にはステップＳＴ３の処理に進み、第２の乗算回路構成方法を選択したと判断した場合にはステップＳＴ４の処理に進む。
【００５２】
ステップＳＴ３：
ＣＰＵ３４が、上記第１の乗算回路構成方法を基に、上記第１の演算（乗算）を行う排他的論理和回路と上記第２の演算（加算）を行う論理積回路とを用いて乗算回路を構成する。
【００５３】
ステップＳＴ４：
ＣＰＵ３４が、上記第２の乗算回路構成方法を基に、上記第１の演算（乗算）を行う乗算回路と上記第２の演算（加算）を行う加算回路とを用いて乗算回路を構成する。
【００５４】
以下、図３に示すステップＳＴ３の処理を説明する。
図４は、図３に示すステップＳＴ３の処理を説明するための図である。
図５は、図３に示すステップＳＴ３によって構成される演算回路４の構成図である。
なお、以下に示すステップＳＴ３の処理手順は、一例であり、各手順の順番は任意であると共に、各手順を一括して実行するようにしてもよい。
ステップＳＴ１１：
ＣＰＵ３４が、上記（４−６），（４−７）で定義されるｍ２  次ベクトルを入力する入力インタフェース５０の構成（回路）データを生成する。
【００５５】
ステップＳＴ１２：
ＣＰＵ３４が、上記（４−８）の演算を行う演算回路５１の構成データを生成する。演算回路５１は、それぞれＡＮＤ回路によって実現されるｍ２  ×ｍ２  個の乗算回路３１＿０＿０〜３１＿ｍ２  −１＿ｍ２  −１を有する。すなわち、乗算回路３１＿０＿０〜３１＿ｍ２  −１＿ｍ２  −１は、対象となる乗算が定義される有限体の下位の有限体で定義された乗算（ＡＮＤ演算）を行う。
【００５６】
ステップＳＴ１３：
ＣＰＵ３４が、上記（４−９）の左辺のΣの演算を行う演算回路５２の構成データを生成する。演算回路５２は、それぞれＸＯＲ回路によって実現される（２ｍ２  −１）個の加算回路３２＿０〜３２＿２ｍ２  −２を有する。
すなわち、加算回路３２＿０〜３２＿２ｍ２  −２は、対象となる乗算が定義される有限体の下位の有限体で定義された加算（ＸＯＲ演算）を行う。
【００５７】
ステップＳＴ１４：
ＣＰＵ３４が、上記（４−９）の左辺の（ｍｏｄ（ｆ（α）））の演算を行うｍｏｄｕｌｏ回路５３の構成データを生成する。
【００５８】
ステップＳＴ１５：
ＣＰＵ３４が、ｍｏｄｕｌｏ回路５３から出力されるｍ２  次ベクトル（Ｄ）を出力する出力インタフェース５４の構成データを生成する。
【００５９】
上述した第１の乗算回路構成方法によれば、第２の乗算回路構成方法による場合に比べて加算回路の数を削減できる。ここで、第１の有限体上では、加算回路はＸＯＲ回路で実現され、ＡＮＤ回路で実現される乗算回路に比べて回路規模が大きいため、第２の有限体上で定義された対象となる乗算を行う乗算回路全体の回路規模を縮小できる。
【００６０】
以下、図３に示すステップＳＴ４の処理を説明する。
図６は、図３に示すステップＳＴ４の処理を説明するための図である。
図７は、図３に示すステップＳＴ４によって構成される演算回路５の構成図である。
ステップＳＴ２１：
ＣＰＵ３４が、上記（４−６），（４−７）で定義されるｍ２  次ベクトルを入力する入力インタフェース６１の構成データを生成する。
【００６１】
ステップＳＴ２２：
ＣＰＵ３４が、上記（４−１３），（４−１４），（４−１５）で定義されるＤ０  ，Ｄ１  ，Ｄ２  をそれぞれ生成するＤ０  演算回路６２、Ｄ１  演算回路６３およびＤ２  演算回路６４の構成データを生成する。
Ｄ０  演算回路６２は、下記（５−４）の演算を行い、図８に示すように、乗算回路８１および加算回路８２で構成される。
【００６２】
【数３６】
2004164391.tif 000024
【００６３】
Ｄ１  演算回路６３は、下記（５−５）の演算を行い、図９に示すように、乗算回路８１および加算回路８２で構成される。
【００６４】
【数３７】
2004164391.tif 000025
【００６５】
Ｄ２  演算回路６４は、下記（５−６）の演算を行い、図１０に示すように、乗算回路８１および加算回路８２で構成される。
【００６６】
【数３８】
2004164391.tif 000026
【００６７】
ステップＳＴ２３：
ＣＰＵ３４が、上記（４−１６）内の「Ｄ０  ＋（Ｄ１  −Ｄ０  −Ｄ２  ）αｔ  ＋Ｄ２  α２ｔ」の演算を行う演算回路６５の構成データを生成する。
演算回路６５は、インバータ７１，７２、加算回路６５、αｔ  乗算回路７４、７５および加算回路７６，７７を有する。
【００６８】
ステップＳＴ２４：
ＣＰＵ３４が、上記（４−１６）の左辺の（ｍｏｄ（ｆ（α）））の演算を行うｍｏｄｕｌｏ回路６６の構成データを生成する。
【００６９】
ステップＳＴ２５：
ＣＰＵ３４が、ｍｏｄｕｌｏ回路６６から出力されるｍ２  次ベクトル（Ｄ）を出力する出力インタフェース６７の構成データを生成する。
【００７０】
上述した第２の乗算回路構成方法によれば、第１の乗算回路構成方法による場合に比べて乗算回路の数を削減できる。ここで、上記第２の有限体上では、乗算回路はＡＮＤ回路以外の回路で実現され、加算回路はＸＯＲ以外の回路で実現され、乗算回路は加算回路に比べて回路規模が大きくなる。そのため、上述した第２の乗算回路構成方法のように、乗算回路の数を削減できると、第３の有限体上で定義された乗算を行う対象となる乗算回路全体の回路規模を縮小できる。
【００７１】
以上説明したように、本発明の演算回路構成方法によれば、演算回路２内の各乗算回路を、第１および第２の乗算回路構成方法のうちその演算回路を小規模に構成する乗算回路構成方法を選択して構成するため、演算回路２全体を従来に比べて小規模に構成できる。
【００７２】
本発明は上述した実施形態には、限定されない。
例えば、上述した実施形態では、ｍ１＝１，ｍ２＞２、ｍ３≧１の場合を例示したが、ｍ１，ｍ２，ｍ３として、これら以外の値を用いてもよい。
また、演算回路２の構成は、複数の乗算回路を有していれば、任意である。
また、上述した実施形態では、乗算回路を構成する場合を例示したが、逆元生成回路などのその他の演算回路を構成する場合にも本発明は適用可能である。
【００７３】
【発明の効果】
本発明によれば、複数の有限体でそれぞれ定義された複数の演算を行う演算回路を小規模に構成できる回路構成方法、その装置、そのプログラムおよび演算回路を提供することができる。
【図面の簡単な説明】
【図１】図１は、本発明の実施形態の演算回路構成方法によって構成される演算回路を説明するための図である。
【図２】図２は、本実施形態の乗算回路構成方法を実行するコンピュータの構成図である。
【図３】図３は、図２に示すＣＰＵが演算回路２内の各乗算回路を構成する場合の動作例を説明するためのフローチャートである。
【図４】図４は、図３に示すステップＳＴ３の処理を説明するための図である。
【図５】図５は、図３に示すステップＳＴ３によって構成される演算回路の構成図である。
【図６】図６は、図３に示すステップＳＴ４の処理を説明するための図である。
【図７】図７は、図３に示すステップＳＴ４によって構成される演算回路の構成図である。
【図８】図８は、図７に示すＤ０  演算回路の構成である。
【図９】図９は、図７に示すＤ１  演算回路の構成図である。
【図１０】図１０は、図７に示すＤ２  演算回路の構成図である。
【図１１】図１１は、種々の有限体上で定義された乗算を行う複数の乗算回路を有する従来の演算回路を説明するための図である。
【符号の説明】
２…演算回路、３，４，５，６…乗算回路、３０…バス、３１…操作部、３２…ディスプレイ、３３…メモリ、３４…ＣＰＵ、５０…入力インタフェース、５１…演算回路、５２…演算回路、５３…ｍｏｄｕｌｏ回路、５３…出力インタフェース、６１…入力インタフェース、６２…Ｄ０  演算回路、６３…Ｄ１  演算回路、６４…Ｄ２  演算回路、６５…演算回路、６６…ｍｏｄｕｌｏ回路、６７…出力インタフェース
【図１】
2004164391.tif 000041
【図２】
2004164391.tif 000042
【図３】
2004164391.tif 000043
【図４】
2004164391.tif 000044
【図５】
2004164391.tif 000045
【図６】
2004164391.tif 000046
【図７】
2004164391.tif 000047
【図８】
2004164391.tif 000048
【図９】
2004164391.tif 000049
【図１０】
2004164391.tif 000050
【図１１】
2004164391.tif 000051