"ガロア拡大体の係数を有する第1多項式および第2多項式の乗算である出力多項式の各係数を出力するために使用される複数の係数乗算手段30および係数加算手段32を有する乗算回路12と、各セルが使用可能にされるか否かを示す使用可否値を記憶する記憶回路20と、複数のセル35を有し、前記出力多項式の各係数と、ガロア拡大体の係数を有する第3多項式の各係数と、前記使用可否値とを受信し、かつ、前記出力多項式を既約多項式で割ることによって結果として生じる剰余と前記第3多項式との和の係数を決定するガロア拡大体線形変換器回路18とを具備し、係数乗算手段30の各々は、第1多項式の係数と第2多項式の係数とを、予め決定された組み合わせで乗算し、係数加算手段32の各々は、前記出力多項式の各係数を決定するために、前記係数乗算手段30の出力値を加算し、各セル35は、少なくとも1つの隣接セルと結合され、かつ、イネーブル手段36と乗算値加算手段38とを有し、各イネーブル手段36は、前のセルの出力値とセルが使用可能にされるか否かを示す使用可否値とに関して、AND演算操作を実行し、各乗算値加算手段38は、該乗算値加算手段のセルと同じセル内のイネーブル手段36の出力値と該乗算値加算手段を有するセルと結合された前のセルの出力値とを加算し、それによって、加算結果を次のセルへ提供することを特徴とするガロア拡大体積算/積算加算/積和演算装置。前記第3多項式は加法単位元の多項式であることを特徴とする請求項1に記載のガロア拡大体積算/積算加算/積和演算装置。前記乗算回路の積は、前記第3多項式として再帰的にフィードバックされ、前記加算回路は、積和演算操作を実行することを特徴とする請求項1に記載のガロア拡大体積算/積算加算/積和演算装置。前記乗算の積は、第1出力レジスタに引き渡され、積算加算/積和演算の結果は、第2出力レジスタに引き渡されることを特徴とする請求項1に記載のガロア拡大体積算/積算加算/積和演算装置。前記ガロア拡大体線形変換器回路は、1サイクルで前記第3多項式を第1及び第2の積と組み合わせるための、前記乗算値加算手段に結びつけられた複数の加算セルを含むことを特徴とする請求項1に記載のガロア拡大体積算/積算加算/積和演算装置。前記ガロア拡大体線形変換器回路は、加算操作を無効にするために前記第3多項式を前記第1及び第2多項式の積へ加えることを阻止するための、前記加算セルのそれぞれに結びつけられたゲートを含むことを特徴とする請求項5に記載のガロア拡大体積算/積算加算/積和演算装置。したがってこの発明の目的は、改善されたガロア拡大体積算/積算加算/積和演算装置を提供することにある。この発明のさらなる目的は、1サイクルで積算/積算加算/積和演算操作を実行することができる改善されたガロア拡大体積算/積算加算/積和演算装置を提供することにある。この発明のさらなる目的は、付加的な論理回路なしに性能を増大させることができるそのような改善されたガロア拡大体積算/積算加算/積和演算装置を提供することにある。この発明のさらなる目的は、1サイクルで乗算、又は乗算及び加算、又は積和演算操作のどれかを実行することができるそのような改善されたガロア拡大体積算/積算加算/積和演算装置を提供することにある。本発明は、わずかな論理回路を用いて又は付加的な論理回路を用いずに1サイクルで乗算、又は乗算及び加算、又は積和演算操作のどれかを実行する改善されたガロア拡大体積算/積算加算/積和演算装置が、シングルサイクルで乗算器からの第1及び第2多項式の積を第3多項式に加えるために、ガロア拡大体加算回路と、GF2nの2元多項式binarypolynomialを乗算する多項式乗算回路と、ガロア拡大体線形変換器回路と、記憶回路と、を用いて達成され得る、ということを実現したものである。この発明は、ガロア拡大体線形変換器回路ガロア拡大体の係数を有する2つの多項式を乗算してこれら積を得るための乗算回路と、既約多項式に対する多項式の積のモジュロ剰余を予測するための、乗算回路に応答するガロア拡大体線形変換器回路と、を含むガロア拡大体積算/積算加算/積和演算装置を特徴とする。記憶回路は、所定の既約多項式に対するモジュロ剰余を予測するためにガロア拡大体線形変換器回路に一組の係数を供給する。ガロア拡大体加算回路は、シングルサイクルで乗算及び加算操作を実行するために、ガロア拡大体の係数を有する第3多項式に乗算回路の積を加える。好ましい実施例では、第3多項式は加法単位元の多項式とすることができ、加算操作はゼロになることができる。乗算の積は、第3多項式として再帰的にフィードバックしてもよく、加算回路は、積和演算操作を実行してもよい。乗算の積は、第1出力レジスタに引き渡すことができ、積算加算/積和演算の結果は、第2出力レジスタに引き渡すことができる。ガロア拡大体加算回路は、1サイクルで第3多項式を第1及び第2の積と組み合わせるための、ガロア拡大体線形変換器回路に結びつけられた複数の加算セルを含むことができる。他の目的、特徴、及び優位点は、次の好ましい実施例の記述、及び添付の図面から当業者に見出されよう。以下に開示される一つ又は複数の好ましい実施例に加えて、この発明は、他の実施例とすることができ、かつ様々な方法で実行又は実施することができる。このように、本発明はその適用において、次の記述に説明されるか又は図面に図示された構成要素の構成及び配置の詳細に制限されない。図1には、レジスタ14及び16内の値を選択的に乗じ、これらの積を出力レジスタ11へ供給するか、又は、レジスタ14及び16内の値を乗じ、これらの積をレジスタ15内の値と合計し、その結果を出力レジスタ11へ供給することのできるガロア拡大体積算/積算加算/積和演算装置10が示されている。以下で図2において本発明の実施例を説明する前に、ガロア拡大体乗法及び加法の性質及び操作について次に簡単に述べる。ガロア拡大体GFnは、2つの二項演算が実行され得る一組の元である。加法及び乗法は、交換法則、結合法則、及び分配法則を満足しなければならない。有限個の元を有する体は、有限体である。2元体の例は、モジュロ2の加算及びモジュロ2の乗算の下での集合{0,1}であり、GF2と表される。モジュロ2の加算及び乗算操作は、次の図に示された表に表される。第1行及び第1列は、ガロア拡大体加算器及び乗算器への入力を示す。例えば11=0であり、11=1である。一般に、pが素数であるならば、GFpがp個の元を有する有限体であること、及びGFpmがpm個の元を有する有限体であること、を示すことができる。加えて、体のそれぞれ異なる元は、異なる数で累乗することによって、一の体の元αのそれぞれ異なる累乗として生成され得る。例えばGF256は、256の元を有し、原始元αに256の異なる数を累乗することによって全て生成され得る。加えて、係数が二元である多項式はGF2に属する。m次のGF2の多項式は、mよりも小さいが0よりも大きい次数のGF2のどんな多項式によっても割り切れない場合には、既約であるといわれる。多項式FX=X2X1は、X又はX1のどちらでも割り切れないので、既約多項式である。X2m―11を割り切るm次の既約多項式は、原始多項式として知られている。一定のmに対しては、一つよりも多くの原始多項式があり得る。最も標準的な通信でしばしば用いられる、m=8に対する原始多項式の例は、FX=x8x4x3x2x1である。ガロア拡大体加算は、モジュロ加算と同じなのでソフトウェアで実行することが容易である。例えば、29及び16がGF28の2つの元である場合には、これらの加算は、次の[数1]のようにXOR演算として簡単に行われる。他方でガロア拡大体乗算は、次の例によって示されるようなより複雑なビットであり、原始元αを繰り返し乗算することによってGF24の全ての元を計算する。GF24に対する体の元を生成するために、次数m=4の原始多項式Gxが、次の通りにGx=X4X1と選択される。乗算の結果がなお体の元となるように乗算をモジュロさせるために、5番目のビットセットを有するあらゆる元は、次の恒等式Fα=α4α1=0を用いて4ビットとなる。この恒等式は、α4=1αとセットすることによって、体の異なる元を形成するために繰り返し用いられる。このように体の元は次のように列挙することができる:{0,1,α,α2,α3,1α,αα2,α2α3,1αα3,...1α3}αはGF24に対する原始元なので、αは、GF24の体の元を{0,1,2,4,8,3,6,12,11...9}として生成するために2に設定することができる。ガロア拡大体多項式乗算は2つの基本ステップで実行することができるということを理解することができる。第1は、代数的に拡大された多項式の積cx=axbxの計算であり、同様の冪がcxを与えるために収集される加算は対応する項の間のXOR演算に対応する。例えばcx=a3x3a2x2a1x1a0b3x3b2x2b1x1b0Cx=c6x6c5x5c4x4c3x3c2x2c1x1c0ここでである。第2は、dx=cxmodpxの計算であり、ここでpxは既約多項式である。説明のため、多項式の積を既約多項式で除算した余りを用いて乗算が実行される。例えば、もしpx=x8x4x3x1ならば{57}{83}={c1}である。なぜならば、これら{}バイトのそれぞれは、{b7,b6,b5,b4,b3,b2,b1,b0}の順番の個々のビット値0又は1の連続であり、多項式表現:b7x7b6x6b5x5b4x4b3x3b2x2b1x1b0x0=Σbixiを用いて有限の要素として解釈されるからである。この発明に係る図2の改善されたガロア拡大体乗算装置10は、レジスタ14内の2つの2元多項式binarypolynomialをレジスタ16内の多項式と乗算して、チャート2のように定められた16項の多項式cxによって与えられるこれらの積を得るための、2元多項式乗算回路12を含む。乗算回路12は実際には、複数の乗算セル12a,12b,12c...12nを含む。各項は、で表されるように論理積の機能を含み、項の各対は、[数6]によって示されるような論理的な排他的論理和と結合される。この積は、それぞれが16x8のセル35から構成された多くのガロア拡大体線形変換器ユニット18a,18b,18c...18nを含むことができるガロア拡大体線形変換器回路18へ送られ、所定の既約多項式に対する多項式の積のモジュロ剰余を1サイクルで予測するために乗算回路12によって生成される積に応答する。ユニット18a,18b,18c...18nで乗算が実行される。このガロア拡大体線形変換器回路の構成及び操作と、ガロア拡大体変換器ユニットのそれぞれと、ガロア拡大体乗算機能とは、参照によって全体が本願に組み入れられる2002年1月18日に出願されたSteinらによるGALOISFIELDLINEARTRANSFORMERというタイトルのシリアル番号10/051,533AD-239J、及び2001年11月30日に出願されたSteinらによるGALOISFIELDMULTIPLIERSYSTEMというタイトルのシリアル番号60/334,510AD-240Jの米国特許出願に、より完全に説明されている。ガロア拡大体線形変換器ユニットのそれぞれは、多項式を既約多項式で割ることによって1サイクルでモジュロ剰余を予測する。この既約多項式は、例えば[数7]に示されたどのようなものとすることもできる。GF28が全ての累乗28及びそれよりも下の累乗を用いて実行することのできる、与えられたガロア拡大体の乗算器がチャート3に示されている。次数のより低い多項式に対して、選択された累乗よりも大きい箇所の係数はゼロとなる。例えば、GF25が実行される場合にはGF25とGF28との間の係数はゼロとなる。それゆえ、そのレベルよりも上では予測が行われない。この特定の実施例に対しては、群GF28の既約多項式又は原始多項式0x11Dが選択された。記憶セル26を有する記憶回路20は、特定の原始多項式又は既約多項式に対するモジュロ剰余を予測するために、ガロア拡大体線形変換器回路に一組の係数を供給する。原始多項式0x11Dを有するガロア拡大体GF28に対しては、記憶回路20は図3に示されたようなマトリックス設定値を生み出す。ここでライン例えば22の各交差点は、線形変換器ユニット18a,18b,...18nのセル35を表す。それぞれの拡大された丸い点24は、記憶回路20内の関連する記憶セル26に1が存在することによって使用可能にされたセルを示す。既約多項式の1サイクルのモジュロ演算で予測を生み出すために1の適切なパターンを与える回路20の記憶セル26のプログラミングは、列28に示されている。図3に示されたマトリックスは、17の入力と8の出力とのアレイである。この発明に係るGF乗算の例は、次のように見出される。図2のこの発明によれば、ガロア拡大体の係数を有する第3多項式を含む第3レジスタ15がある。通常、レジスタ14,16,及び15のそれぞれは、各レジスタが4バイト、すなわちトータルで32ビットを含むように、8ビットからなる4つのバイト区分を含むことができる。レジスタ15からの出力は、この実施例ではバス17と、バス17の各ビットに対して一つである多くの排他的論理和ゲート19と、を含むガロア拡大体加算回路19へ引き渡される。積算及び加算、又は積和の結果を出力レジスタ回路11のMpaレジスタ25に提供するために、バス21上の積と第3多項式との組み合わせが、排他的論理和回路19′を含む加算回路19で組み合わされる一方で、乗算の単純な積が出力レジスタ回路11内のMpyレジスタ23で利用できるように、ガロア拡大体線形変換器回路18で得られる積はバス21へ引き渡される。例えば図9で、2つの新しい値が入力レジスタ回路14及び16へ送られる間、ガロア拡大体乗算装置10の出力が入力レジスタ回路15に再帰的にフィードバックされるならば、積和Multiplyandaccumulate:MACが実行される。他方図10で、2つの新しい値が入力レジスタ回路15及び16へ送られる間、ガロア拡大体乗算装置10の出力が入力レジスタ回路14で再帰的にフィードバックされるならば、積算及び加算Multiplyandadd:MPAが実行される。このように、レジスタ14及び16における多項式と、レジスタ15内の多項式とのこれらの加算と、の乗算全体は全て、1サイクルの操作で達成される。図2における多項式乗算回路12の各セル29は、図4における多くの論理積ゲート30を含み、一つは多項式の積と排他的論理和ゲート32との各項に対するものであり、一つは多項式の積における項の各対に対するものである。排他的論理和ゲート32が加算に影響を与える一方で、論理積ゲート30は乗算を実行する。ガロア拡大体線形変換器回路18における図2の各セル35は、前のセルから入力を受け、次のセルに出力を与える。第1セルの入力は図3に示されるように31でアースされる。図5における記憶回路20の各セル33は、データDの入力、Wrクロックの入力、及びQの出力を容易にするフリップフロップ34を含む。その全体が本願に組み入れられる、2002年1月18日に出願されたSteinらによるGALOISFIELDLINEARTRANSFORMERというタイトルのシリアル番号10/051,533の米国特許出願AD-239Jにも説明されているように、ガロア拡大体線形変換器回路の各セル35と、ガロア拡大体線形変換器回路の一つ又は複数のユニットのそれぞれとは、図6の論理積ゲート36と排他的論理和ゲート38とを有する図4のセル35を含む。セル29,33,及び35のそれぞれにおいて、示された特定の装置は、本発明を制限するものではない。例えば記憶装置33はフリップフロップによって実行される必要はなく、あらゆる他の記憶装置を用いることができる。図2及び図4では、セル29及び35はそれぞれ、論理積の機能と排他的論理和の機能とを必要とするが、これらは、排他的論理和ゲート及び論理積ゲートのようなブールの意味Booleansenseで機能する論理回路がある限り、特定の排他的論理和ゲート又は論理積ゲートを必要としない多くの異なる方法で実行することができる。例えば、論理積の機能は、論理積の機能を実行するための2:1の入力マルチプレクサを用いる特定の論理積ゲートなしに達成することができる。図2では示された実施例は、実際の論理回路、すなわち排他的論理和回路19′を含む加算回路19を使用するが、本発明に必須の制限ではない。本発明は、レジスタ15内の多項式の値がガロア拡大体線形変換器回路18のセル35の最初へライン17a上で直接送られる図7に示すように、いっそうより単純に行うことができる。この場合、図3のアースされた接続31は除去され、代わりに加算回路が1サイクルで積算及び加算、又は積和の全てを実行するために単純なライン17a及び接続19aを含むように、ライン17a上の入力を有する19aで接続が行われる。しかしながら、加算のない連続した乗算straightmultiplicationが望まれる場合には、入力レジスタ回路15は、加算0に対する加法的単位元の特性を保つべきであり、加算操作はゼロにされる。僅かばかりさほど単純でない図8の装置では、加算回路19bは、入力ライン17bに加えて、ライン17bからの入力を受けるとともに順にそれぞれがガロア拡大体線形変換器回路18における第1セル35の異なる入力へ接続された多くのゲート19′bを含む。ライン50上の信号は、各ゲートがレジスタ15内に格納された多項式からの値を通す又は通さないよう調整する。加算のない連続した乗算が望まれる場合には、ゲート19′bの全ての割り込みを抑制することができる。使用可能にされたゲートを用いるとレジスタ15内の多項式は、レジスタ14及び16内の多項式の乗算の積に加えられる。ガロア拡大体線形変換器回路18におけるこの第1セル35の使用は、参照によって本願に組み入れられる2002年6月12日に出願されたSteinらによるPROGRAMMABLEDATAENCRYPTIONENGINEにより完全に示されかつ説明されている。本発明の特定の特徴はいくつかの図面に示されており、他には示されていないが、それぞれの特徴は本発明に係る他の特徴のいくつか又は全てと組み合わせることができるので、これは便利のためのみである。ここで用いられたような含む、有する、及び備えるとの語は、広範囲にかつ包括的に解釈されるべきであり、あらゆる物理的な相互接続に制限されない。その上、本明細書に開示されたあらゆる実施例は、唯一可能な実施例と解されるべきではない。他の実施例は当業者に見出され、特許請求の範囲内にある。この出願は、2001年11月30日に出願されたSteinらによるGF2-ALUというタイトルのシリアル番号60/334,662AD-239J、2001年12月18日に出願されたSteinらによるGALOISFIELDMULTIPLYADDUSINGGF2ALUというタイトルのシリアル番号60/341,635AD-229J、2001年12月18日に出願されたSteinらによるMETHODFORDATAENCRYPTIONSTANDARDUSINGGF2ALUAND8WAYPARALLELLUTというタイトルのシリアル番号60/341,711AD-297J、2001年11月30日に出願されたSteinらによるGALOISFIELDMULTIPLIERSYSTEMというタイトルのシリアル番号60/334,510AD-240Jの米国仮出願の優先権を主張する。"