(57)【要約】【課題】有限体上の演算を行う演算回路を従来に比べて少ない回路構成要素で小規模に構成できる回路構成方法を提供する。【解決手段】第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る（ＳＴ１）。第２の有限体から第３の有限体への第２の拡大についての第２の多項式であって、ＳＴ１で得られた第１の原始根α１  と第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された第２の多項式を基に第２の原始根α２  を得る（ＳＴ２）。第２の原始根α２  を用いて表現された基底を用いて、第３の有限体上の演算を規定して演算回路を構成する（ＳＴ３，４）。【選択図】  図５
2004164383.tif 000002
【特許請求の範囲】
【請求項１】
有限体上の演算を行う演算回路を構成する回路構成方法であって、
第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る第１の工程と、
前記第２の有限体から前記第３の有限体への第２の拡大についての第２の多項式であって、前記第１の工程で得られた前記第１の原始根α１  と前記第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された前記第２の多項式を基に第２の原始根α２  を得る第２の工程と、
前記第２の工程で得られた前記第２の原始根α２  を用いて表現された基底を用いて、前記第３の有限体上の演算を規定する第３の工程と、
前記第３の工程で規定された演算を基に、当該演算を行う演算回路を構成する第４の工程と
を有する回路構成方法。
【請求項２】
前記第１の有限体が、有限体Ｆｑ  から拡大次数ｎの拡大であり、
前記第２の有限体が、前記第１の有限体から拡大次数ｌ１  の第１の拡大であり、
前記第３の有限体が、前記第２の有限体から拡大次数ｌ２  の第２の拡大であり、
前記第３の工程において、下記（１−１）で示す位数の下記（１−２）で示す前記第３の有限体上の演算を規定する場合に、
前記第１の工程において、前記第１の原始根α１  を下記（１−３）を基に得て、
前記第２の工程において、前記第２の原始根α２  を下記（１−４）を基に得る
請求項１に記載の回路構成方法。
【数１】
2004164383.tif 000031
【数２】
2004164383.tif 000032
【数３】
2004164383.tif 000033
【数４】
2004164383.tif 000034
【請求項３】
前記拡大次数ｌ１  とｌ２  とが共にｑである場合に、
前記第１の工程において、前記第１の原始根α１  を下記（１−５），（１−５ａ）を基に得て、
前記第２の工程において、前記第２の原始根α２  を下記（１−６）を基に得る
請求項２に記載の回路構成方法。
【数５】
2004164383.tif 000035
【数６】
2004164383.tif 000036
【数７】
2004164383.tif 000037
【請求項４】
前記第３の工程において、前記第２の有限体上の演算を用いて前記第３の有限体上の演算を規定し、
前記第４の工程において、前記第３の工程で用いた前記第２の有限体上の演算を行う第１の演算回路を構成し、当該第１の演算回路を用いて前記第３の有限体上の演算を行う第２の演算回路を構成する
請求項１に記載の回路構成方法。
【請求項５】
前記第３の工程において、前記第２の多項式の０次の項の係数を乗じる前記第２の有限体上の演算を用いて、前記第３の有限体上の演算を規定する
請求項４に記載の回路構成方法。
【請求項６】
有限体上の演算を行う演算回路を構成する回路構成装置であって、
第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る第１の手段と、
前記第２の有限体から前記第３の有限体への第２の拡大についての第２の多項式であって、前記第１の手段で得られた前記第１の原始根α１  と前記第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された前記第２の多項式を基に第２の原始根α２  を得る第２の手段と、
前記第２の手段で得られた前記第２の原始根α２  を用いて表現された基底を用いて、前記第３の有限体上の演算を規定する第３の手段と、
前記第３の手段で規定された演算を基に、当該演算を行う演算回路を構成する第４の手段と
を有する回路構成装置。
【請求項７】
有限体上の演算を行う演算回路を構成する回路構成装置によって実行されるプログラムであって、
第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る第１の手順と、
前記第２の有限体から前記第３の有限体への第２の拡大についての第２の多項式であって、前記第１の手順で得られた前記第１の原始根α１  と前記第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された前記第２の多項式を基に第２の原始根α２  を得る第２の手順と、
前記第２の手順で得られた前記第２の原始根α２  を用いて表現された基底を用いて、前記第３の有限体上の演算を規定する第３の手順と、
前記第３の手順で規定された演算を基に、当該演算を行う演算回路を構成する第４の手順と
を有するプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、有限体上の演算を行う演算回路の回路構成方法、その方法およびそのプログラムに関する。
【０００２】
【従来の技術】
例えば、ハミング符号などの誤り訂正符号や復号では、例えば、有限体上の演算が行われている。
このような有限体は、他の有限体からの拡大によって規定される場合がある。
例えば、第１の有限体からの第１の拡大によって第２の有限体が規定され、第２の有限体からの第２の拡大によって第３の有限体が規定される場合に、上記第３の有限体上の演算は、上記第２の有限体上の演算を用いて規定される。
また、上記第２の有限体上の演算は、上記第１の拡大についての第１の多項式によって得られた原始根を基に決定された基底を用いて表現される。また、第２の有限体上の演算は、上記第２の拡大についての第２の多項式によって得られた原始根を基に決定された基底を用いて表現される。
従来の回路構方法では、上記第２の多項式の０次の項の係数を、上記第１の多項式の０次の項の係数とは無関係に定めている。
【０００３】
【発明が解決しようとする課題】
しかしながら、上述した従来の回路構成方法では、第３の有限体上の演算を行う演算回路の回路構成要素が多くなり、当該演算回路が大規模化してしまうという問題がある。
【０００４】
本発明はかかる事情に鑑みてなされたものであり、有限体上の演算を行う演算回路を従来に比べて少ない回路構成要素で小規模に構成できる回路構成方法、その装置、そのプログラムおよび演算回路を提供することを目的とする。
【０００５】
【課題を解決するための手段】
上記の目的を達成するため、第１の発明の回路構成方法は、有限体上の演算を行う演算回路を構成する回路構成方法であって、第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る第１の工程と、前記第２の有限体から前記第３の有限体への第２の拡大についての第２の多項式であって、前記第１の工程で得られた前記第１の原始根α１  と前記第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された前記第２の多項式を基に第２の原始根α２  を得る第２の工程と、前記第２の工程で得られた前記第２の原始根α２  を用いて表現された基底を用いて、前記第３の有限体上の演算を規定する第３の工程と、前記第３の工程で規定された演算を基に、当該演算を行う演算回路を構成する第４の工程とを有する。
【０００６】
第１の発明の回路構成方法の作用は以下のようになる。
先ず、第１の工程において、第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る。
次に、第２の工程において、前記第２の有限体から前記第３の有限体への第２の拡大についての第２の多項式であって、前記第１の工程で得られた前記第１の原始根α１  と前記第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された前記第２の多項式を基に第２の原始根α２  を得る。
次に、第３の工程において、前記第２の工程で得られた前記第２の原始根α２を用いて表現された基底を用いて、前記第３の有限体上の演算を規定する。
次に、第４の工程において、前記第３の工程で規定された演算を基に、当該演算を行う演算回路を構成する。
【０００７】
第２の発明の回路構成装置は、有限体上の演算を行う演算回路を構成する回路構成装置であって、第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る第１の手段と、前記第２の有限体から前記第３の有限体への第２の拡大についての第２の多項式であって、前記第１の手段で得られた前記第１の原始根α１  と前記第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された前記第２の多項式を基に第２の原始根α２を得る第２の手段と、前記第２の手段で得られた前記第２の原始根α２  を用いて表現された基底を用いて、前記第３の有限体上の演算を規定する第３の手段と、前記第３の手段で規定された演算を基に、当該演算を行う演算回路を構成する第４の手段とを有する。
【０００８】
第２の発明の回路構成装置の作用は以下のようになる。
先ず、第１の手段において、第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る。
次に、第２の手段において、前記第２の有限体から前記第３の有限体への第２の拡大についての第２の多項式であって、前記第１の手段で得られた前記第１の原始根α１  と前記第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された前記第２の多項式を基に第２の原始根α２  を得る。
次に、第３の手段において、前記第２の手段で得られた前記第２の原始根α２を用いて表現された基底を用いて、前記第３の有限体上の演算を規定する。
次に、第４の手段において、前記第３の手段で規定された演算を基に、当該演算を行う演算回路を構成する。
【０００９】
第３の発明のプログラムは、有限体上の演算を行う演算回路を構成する回路構成装置によって実行されるプログラムであって、第１の有限体から第２の有限体への第１の拡大についての第１の多項式を基に第１の原始根α１  を得る第１の手順と、前記第２の有限体から前記第３の有限体への第２の拡大についての第２の多項式であって、前記第１の手順で得られた前記第１の原始根α１  と前記第１の多項式の０次の項の係数とを用いて、０次の項の係数が規定された前記第２の多項式を基に第２の原始根α２  を得る第２の手順と、前記第２の手順で得られた前記第２の原始根α２  を用いて表現された基底を用いて、前記第３の有限体上の演算を規定する第３の手順と、前記第３の手順で規定された演算を基に、当該演算を行う演算回路を構成する第４の手順とを有する。
【００１０】
【発明の実施の形態】
〔本発明の関連技術〕
当該関連技術では、有限体Ｆが有限体Ｆｑ  のｎ次拡大であり、有限体Ｋが有限体Ｆからの拡大次数ｑの拡大であり、有限体Ｌが有限体Ｋからの拡大次数ｑの拡大である場合に、有限体Ｋ上のａ倍演算を含む有限体Ｌ上の演算を行う演算回路を構成する回路構成方法を説明する。
ここで、位数が下記（２−１）で示され、有限体Ｌが下記（２−２）のように表現される。本実施形態では、下記（２−１），（２−２）において、ｌ１  ＝ｌ２  ＝ｑの場合を例示する。
この場合に、上記拡大の関係は、下記（２−３）で示される。
【００１１】
【数８】
2004164383.tif 000003
【００１２】
【数９】
2004164383.tif 000004
【００１３】
【数１０】
2004164383.tif 000005
【００１４】
従来の回路構成方法では、図１に示すように、有限体Ｋ上のｌ２  次元ベクトルＤ＿ＩＮを入力し、有限体Ｋ上のｌ２  次元ベクトルＤ＿ＯＵＴを出力し、有限体Ｋ上のａ倍演算回路３０１を有し、有限体Ｌ上の演算を行う演算回路３００を構成する。
有限体Ｋ上のａ倍演算回路３０１は、有限体Ｆ上のｌ１  次元ベクトルＶＡを入力し、有限体Ｆ上のｌ１  次元ベクトルＶＤを出力する。
有限体Ｆから有限体Ｋへの第１の拡大Ｋ／Ｆの原始根α１  を下記（２−４）に示す第１の多項式を基に得る。
そして、原始根α１  を基に、有限体Ｋ上の演算の基底を選択する。
【００１５】
【数１１】
2004164383.tif 000006
【００１６】
また、有限体Ｋから有限体Ｌへの第２の拡大Ｌ／Ｋの原始根α２  を下記（２−５）に示す第２の多項式を基に得る。
そして、原始根α２  を基に、有限体Ｌ上の演算の基底を選択する。
ここで、上記ａ倍演算回路３０１のａは、下記（２−５）内の０次の項の係数ａである。
【００１７】
【数１２】
2004164383.tif 000007
【００１８】
そして、上記原始根α１  を基に定められた基底を用いた下記（２−６）に示す有限体Ｋ上の任意の元Ａを、下記（２−７）のように有限体Ｆ上のｌ１  （＝ｑ）次元ベクトルＶＡで示す。
【００１９】
【数１３】
2004164383.tif 000008
【００２０】
【数１４】
2004164383.tif 000009
【００２１】
また、上記原始根α１  を基に定められた基底を用いた下記（２−８）で示すＤを、下記（２−９）のように有限体Ｆ上のｌ１  （＝ｑ）次元ベクトルＶＤで示す。
【００２２】
【数１５】
2004164383.tif 000010
【００２３】
【数１６】
2004164383.tif 000011
【００２４】
この場合に、Ｄ：＝ａ・Ａは、上記（２−５）で定義されるａ、並びに上記（２−６）で定義されるＡを用いると、下記（２−１０）のように示され、ベクトルＶＤは下記（２−１１）のように示される。ここで、下記（２−１２）の左辺のα１  のｑ乗値を右辺の値（α１  −１）に置き換えて表現される。
【００２５】
【数１７】
2004164383.tif 000012
【００２６】
【数１８】
2004164383.tif 000013
【００２７】
【数１９】
2004164383.tif 000014
【００２８】
上記回路構成方法では、上記（２−１０），（２−１１）を基に、図２に示すように、図１に示す有限体Ｋ上のａ倍演算回路３０１を構成する。
図２に示すａ倍演算回路３０１には、上記（２−７）で示すｑ次元ベクトルＶＡが入力される。
図２に示すＡ〔０〕〜Ａ〔ｑ−１〕が、上記（２−７）に示すＡ０  〜Ａｑ−１  にそれぞれ対応している。
ａ倍演算回路３０１は、上記（２−４）より得られる下記（２−１２）を基にα１  のｑ次の項を１次および０次の項で置き換えて上記（２−１０）に示す演算を行うように構成される。
これにより、ａ倍演算回路３０１は、α１  のｑ次未満の項の係数についての演算を行うように構成される。
【００２９】
図２に示すように、上記回路構成方法は、データＡ〔０〕〜Ａ〔ｑ−１〕のそれぞれが、係数ｄを乗算するｑ−１個の乗算回路３１＿１〜３１＿ｑ−１、係数ｃｄを乗算するｉ−１個の乗算回路３２＿１〜３２＿ｉ−１、加算回路３３のうち、対応る回路に入力されるようにａ倍演算回路３０１を構成する。
また、上記回路構成方法は、乗算回路３２＿０〜３２＿ｉ−１の出力が、インバータ３５＿０〜３５＿ｉ−１にそれぞれ入力されるようにａ倍演算回路３０１を構成する。
また、上記回路構成方法は、乗算回路３１＿１〜３１＿ｉ−１の出力が、それぞれ加算回路３４＿１〜３４＿ｉ−１に入力されるようにａ倍演算回路３０１を構成する。
また、上記回路構成方法は、インバータ３５＿１〜３５＿ｉ−１の出力が、それぞれ加算回路３４＿１〜３４＿ｉ−１に入力されるようにａ倍演算回路３０１を構成する。
また、上記回路構成方法は、乗算回路３３の出力が、係数ｄを乗算する乗算回路３２に入力されるようにａ倍演算回路３０１を構成する。
そして、インバータ３５＿０、加算回路３４＿１〜３４＿ｉ−１、乗算回路３２、並びに乗算回路３１＿ｉ〜３１＿ｑ−１の出力が、それぞれデータＤ〔０〕〜〔ｑ−１〕となる。
図２に示すＤ〔０〕〜Ｄ〔ｑ−１〕が、上記（２−９），（２−１１）に示すＤ０  〜Ｄｑ−１  にそれぞれ対応している。
【００３０】
〔発明の実施の形態〕
本実施形態では、上述した関連技術と同様に、有限体Ｆ（本発明の第１の有限体）が有限体Ｆｑ  のｎ次拡大であり、有限体Ｋ（本発明の第２の有限体）が有限体Ｆからの拡大次数ｑの拡大であり、有限体Ｌ（本発明の第３の有限体）が有限体Ｋからの拡大次数ｑの拡大である場合に、有限体Ｋ上のａ倍演算を含む有限体Ｌ上の演算を行う演算回路を構成する回路構成方法を説明する。
ここで、位数が下記（３−１）で示され、有限体Ｌが下記（３−２）のように表現される。本実施形態では、下記（３−１），（３−２）において、ｌ１  ＝ｌ２  ＝ｑの場合を例示する。例えば、ｑは２、ｎは４である。
この場合に、上記拡大の関係は、下記（３−３）で示される。
【００３１】
【数２０】
2004164383.tif 000015
【００３２】
【数２１】
2004164383.tif 000016
【００３３】
【数２２】
2004164383.tif 000017
【００３４】
本実施形態の回路構成方法では、図３に示すように、有限体Ｋ上のｌ２  （＝ｑ）次元ベクトルＤ＿ＩＮを入力し、有限体Ｋ上のｌ２  次元ベクトルＤ＿ＯＵＴを出力し、有限体Ｋ上のａ倍演算回路１０１を有し、有限体Ｌ上の演算を行う演算回路１００を構成する。
有限体Ｋ上のａ倍演算回路１０１は、有限体Ｆ上のｌ１  （＝ｑ）次元ベクトルＶＡを入力し、有限体Ｆ上のｌ１  次元ベクトルＶＤを出力する。
有限体Ｆから有限体Ｋへの第１の拡大Ｋ／Ｆ（本発明の第１の拡大）の第１の原始根α１  （本発明の第１の原始根）を下記（３−４）に示す第１の多項式を基に得る。
そして、原始根α１  を基に、有限体Ｋ上の演算の基底を選択する。
【００３５】
【数２３】
2004164383.tif 000018
【００３６】
上記（３−４）において、トレースＴｒは、下記（３−４ａ）のように定義される。
【００３７】
【数２４】
2004164383.tif 000019
【００３８】
また、有限体Ｋから有限体Ｌへの第２の拡大Ｌ／Ｋ（本発明の第２の拡大）の第２の原始根α２  （本発明の第２の原始根）を下記（３−５）に示す第２の多項式（本発明の第２の多項式）を基に得る。
ここで、下記（３−５）に示す第２の多項式は、上記（３−４）に示す第１の多項式の第１の原始根α１  と当該第１の多項式の０次の項の係数ｃとを用いて、０次の項の係数ａが規定されている。
【００３９】
【数２５】
2004164383.tif 000020
【００４０】
そして、上記第１の原始根α１  を基に定められた基底を用いた下記（３−６）に示す有限体Ｋ上の任意の元Ａを、下記（３−７）のように有限体Ｆ上のｌ１  次元ベクトルＶＡで示す。
【００４１】
【数２６】
2004164383.tif 000021
【００４２】
【数２７】
2004164383.tif 000022
【００４３】
また、上記第１の原始根α１  を基に定められた基底を用いた下記（３−８）で示すＤを、下記（３−９）のように有限体Ｆ上のｌ１  次元ベクトルＶＤで示す。
【００４４】
【数２８】
2004164383.tif 000023
【００４５】
【数２９】
2004164383.tif 000024
【００４６】
この場合に、Ｄ：＝ａ・Ａは、上記（３−５）で定義されるａ、並びに上記（３−６）で定義されるＡを用いると、下記（３−１０）のように示され、ベクトルＤ＿Ｖは下記（３−１１）で示される。ここで、上記（３−４）から得られる下記（３−１２）の左辺のα１  のｑ乗値を右辺の値（α１  −１）に置き換えて表現される。
【００４７】
【数３０】
2004164383.tif 000025
【００４８】
【数３１】
2004164383.tif 000026
【００４９】
【数３２】
2004164383.tif 000027
【００５０】
上記回路構成方法では、上記（３−１０），（３−１１）を基に、図１に示すように、有限体Ｋ上のａ倍演算回路１０１を構成する。
ここで、ａ倍演算回路１０１のａは、上記（３−５）内のａである。
【００５１】
図４は、本実施形態の回路構成方法を実行するコンピュータ２９（本発明の回路構成装置）の構成図である。
図４に示すように、コンピュータ２９は、例えば、操作部３１、ディスプレイ３２、メモリ３３およびＣＰＵ３４を有し、これらがバス３０を介して接続されている。
操作部３１は、キーボードやマウスなどの操作手段であり、ユーザの操作に応じた操作信号をＣＰＵ３４に出力する。
ディスプレイ３２は、ＣＰＵ３４による回路構成の処理に応じた画面を表示する。
メモリ３３は、ＣＰＵ３４の処理に用いられるプログラム４１（本発明のプログラム）およびデータ４２を記憶する。
【００５２】
ＣＰＵ３４は、プログラム４１を実行し、データ４２を用いて、以下に示すように上記有限体Ｌ上の演算回路における上記有限体Ｋ上のａ倍演算回路を構成（設計）する。
ＣＰＵ３４が、本発明の回路構成装置の第１〜第４の手段に対応している。
【００５３】
図５は、ＣＰＵ３４が演算回路２内の各乗算回路を構成する場合の動作例を説明するためのフローチャートである。
ステップＳＴ１：
ＣＰＵ３４が、有限体Ｆから有限体Ｋへの第１の拡大についての上記（３−４）に示す第１の多項式を基に第１の原始根α１  を得る。
【００５４】
ステップＳＴ２：
ＣＰＵ３４が、ステップＳＴ１で得られた第１の原始根α１  および第１の多項式の０次の項の係数とを用いてその０次の項の係数ａが規定された上記（３−５）に示す第２の多項式を基に上記第２の原始根α２  を得る。
【００５５】
ステップＳＴ３：
ＣＰＵ３４が、ステップＳＴ２で得られた上記原始根α２  を用いて表現された基底を用いて、有限体Ｌ上の演算を規定する。
そして、上記有限体Ｌ上の演算内に、上有限体Ｋ上のａ倍演算がある場合に、上記（３−１０），（３−１１）を基に、ａ倍演算を規定する。このとき、上記（３−１２）を基に、上記（３−１０）におけるα１  のｑ次の項を１次および０次の項の係数ｃで置き換えて、当該ａ倍演算を規定する。これにより、上記ａ倍演算は、α１  のｑ次未満の項の係数についての演算によって規定される。
【００５６】
ステップＳＴ４；
ＣＰＵ３４が、ステップＳＴ３で規定された演算を基に、上記有限体Ｋ上のａ倍演算回路を含む、有限体Ｌ上の上記演算を行う演算回路を構成する。
【００５７】
本実施形態では、例えば、図３に示す有限体Ｋ上のａ倍演算回路１０１が、図６に示すように構成される。
すなわち、ＣＰＵ３４が、上記（３−７）で示すｑ次元ベクトルＶＡを入力するようにａ倍演算回路１０１を構成する。
図６に示すＡ〔０〕〜Ａ〔ｑ−１〕が、上記（３−７）に示すＡ０  〜Ａｑ−１  にそれぞれ対応している。
また、ＣＰＵ３４が、図６に示すように、データＡ〔０〕〜Ａ〔ｑ−１〕のそれぞれが、インバータ１３＿０〜１３＿ｉ−１、ｃ−１倍演算を行うｃ−１倍演算回路１１＿１〜１１＿ｉ−１、ｃ−１倍演算回路１１＿ｉ＋１〜１１＿ｑ−１および、加算回路１２のうち対応する回路に入力されるようにａ倍演算回路１０１を構成する。
【００５８】
また、ＣＰＵ３４が、ｃ−１倍演算回路１１＿１〜１１＿ｉ−１の出力が加算回路１４＿１〜１４＿ｉ−１に入力されるようにａ倍演算回路１０１を構成する。また、ＣＰＵ３４が、インバータ１３＿１〜１３＿ｉ−１の出力が加算回路１４＿１〜１４＿ｉ−１に入力されるようにａ倍演算回路１０１を構成する。
【００５９】
また、ＣＰＵ３３４が、加算回路１２の出力がｃ−１倍演算回路１１＿ｉに入力されるようにａ倍演算回路１０１を構成する。
そして、ＣＰＵ３４が、インバータ１３＿０、加算回路１４＿１〜１４＿ｉ−１、ｃ−１倍演算回路１１＿ｉ〜１１＿ｑ−１の出力が、それぞれデータＤ〔０〕〜〔ｑ−１〕となるように、ａ倍演算回路１０１を構成する。
図６に示すＤ〔０〕〜Ｄ〔ｑ−１〕が、上記（３−９），（３−１１）に示すＤ０  〜Ｄｑ−１  にそれぞれ対応している。
【００６０】
以上説明したように、本実施形態の回路構成方法によれば、上記（３−５）に示すように、第２の多項式の０次の項の係数ａを、上記（３−４）に示す第１の多項式の第１の原始根α１  と当該第１の多項式の０次の項の係数ｃとを用いて規定することで、図２に示すａ倍演算回路３０１に比べて、回路数が削減され、小規模化された図６に示すａ倍演算回路１０１を構成できる。図２に示す従来のａ倍演算回路３０１では、Ｘ倍演算回路として上記（２−４）に示す係数ｃと上記（２−５）に示す係数ｄとに係わる乗算を行う回路が必要だったが、ａ倍演算回路１０１では、Ｘ倍演算回路は係数ｃに係わる回路のみとなる。
【００６１】
本発明は上述した実施形態には、限定されない。
例えば、上記（３−４），（３−５）において、ｑ＝２，ｎ＝４とすると、第１の有限体Ｆは下記（４−１）で示され、上記（３−４），（３−５）はそれぞれ下記（４−２），（４−３）で示される。
【００６２】
【数３３】
2004164383.tif 000028
【００６３】
【数３４】
2004164383.tif 000029
【００６４】
【数３５】
2004164383.tif 000030
【００６５】
また、上述した実施形態では、Ｋ上のａ倍演算回路を含むＬ上の演算回路を構成する場合を例示したが、本発明は、その他、Ｋ上の乗算回路または逆元生成回路を含むＬ上の演算回路を構成してもよい。
【００６６】
【発明の効果】
本発明によれば、有限体上の演算を行う演算回路を従来に比べて少ない回路構成要素で小規模に構成できる回路構成方法、その装置、そのプログラムおよび演算回路を提供することができる。
【図面の簡単な説明】
【図１】図１は、本発明の関連技術の回路構成方法によって構成される有限体Ｌ上の演算を行う演算回路を説明するための図である。
【図２】図２は、図１に示す有限体Ｋ上のａ倍演算回路の構成図である。
【図３】図３は、本発明の実施形態の回路構成方法によって構成される有限体Ｌ上の演算を行う演算回路を説明するための図である。
【図４】図４は、本発明の実施形態の回路構成方法を実行するコンピュータを説明するための図である。
【図５】図５は、図４に示すコンピュータの処理を説明するための図である。
【図６】図６は、図３に示す有限体Ｋ上のａ倍演算回路の構成図である。
【符号の説明】
３０…バス、３１…操作部、３２…ディスプレイ、３３…メモリ、３４…ＣＰＵ、１００，３００…有限体Ｌ上の演算回路、１０１，３０１…有限体Ｋ上のａ倍演算回路
【図１】
2004164383.tif 000038
【図２】
2004164383.tif 000039
【図３】
2004164383.tif 000040
【図４】
2004164383.tif 000041
【図５】
2004164383.tif 000042
【図６】
2004164383.tif 000043