(57)【要約】  乗算器装置は、素数を法とする剰余系で第１の多倍長整数エンティティに第２の多倍長整数を乗算するため構成される。特に、この装置は、パイプライン型乗算器コアを含み、全体的な乗算をモンゴメリ形式で実行する。
2005513532.tif 000002
【特許請求の範囲】
【請求項１】
素数を法とする剰余系で第１の多倍長整数エンティティに第２の多倍長整数を乗算するため構成された乗算器装置であって、
パイプライン型乗算器コアを含み、全体的な乗算をモンゴメリ形式で実行することを特徴とする乗算器装置。
【請求項２】
修正ブースアルゴリズムを実行するようにさらに構成されている請求項１記載の乗算器装置。
【請求項３】
並列的にｙ０＊Ｘを減算するようにさらに構成されている請求項２記載の乗算器装置。
【請求項４】
ガロア体ＧＦ（２ｎ）の既約多項式を法として、前記第１の多倍長整数エンティティおよび前記第２の多倍長整数エンティティをそれぞれの多項式の形式で乗算するように構成されている請求項１記載の乗算器装置。
【請求項５】
ＲＳＡのような計算を実行するために適用される請求項１記載の乗算器装置。
【請求項６】
楕円曲線計算を実行するために適用される請求項１記載の乗算器装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、素数を法とする剰余系で第１の多倍長整数(long integer)エンティティに第２の多倍長整数を乗算する乗算器装置に係わり、この装置は、パイプライン型コアを含み、全体的な乗算をモンゴメリ形式で実行するために構成されている。
【背景技術】
【０００２】
素数を法とする剰余系での多倍長整数の乗算は、基本的な、繰り返し演算であり、いわゆる公開鍵システムおよび様々なその他のアプリケーションで使用される。このようなアプリケーションの効率的な使用のため、乗算の実効時間は最小限となるべきである。その結果、本発明は、特に、請求項１のプリアンブルに記載されるような装置に関する。このため、乗算演算と還元演算の組み合わせを使用する様々な方法および装置が提案されている。特に、屡々、結果の最上位部分が実際に還元に影響を与えるために使用されている。しかし、このような最上位部分の展開は、このような乗算の系列が連続した態様で実行されなければならないので、特に、利用可能なハードウェアが最大実現可能なデューティサイクルで使用されなければならないとき、実質的に全体的な演算を遅らせることに本発明者は気付いた。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
したがって、特に、本発明の目的は、プリアンブルに記載されたような乗算器装置であって、従来技術と対比して、実際の結果の最下位部分が還元に影響を与えるため使用され、ハードウェアがこのような乗算の実質的である長い系列を処理可能にするため実際に使用される時間の割合をさらに引き上げる乗算器装置を提供することである。
【課題を解決するための手段】
【０００４】
このため、本発明の態様の一つによれば、本発明は、請求項１の特徴部によって特徴付けられる。実際に、本発明による組み合わせは、より容易にパイプラインを一杯の状態に保ち、その結果として、オーバーレイ演算における平均計算時間を短縮する。乗算器装置は、ｐを素数としてＧＦ（ｐ）における演算、並びに、ＧＦ（２ｎ）における演算に適用可能である。
【０００５】
さらに、本発明の有利な態様は、本発明の主な要素への有利な拡張、または、本発明の適用分野を明確にする従属請求項に記載されている。
【０００６】
本発明の上記およびさらなる態様並びに効果は、好ましい実施形態の説明と、特に添付図面とを参照して以下で詳細に説明される。
【発明を実施するための最良の形態】
【０００７】
（１．  パイプライン型乗算器）
パイプライン型乗算器は、全てのクロックサイクルで、乗算される２個の新しい数を受け入れるように設計されている。両者の積は、多数の段階で計算され、全ての段階を通ったときに作動可能となる。例えば、３２＊３２ビット乗算の場合、段階の段数は１７（乗算用の１６段と最終加算用の１段）である。全てのクロックサイクルで、次の積が計算されるが、その結果は１７クロックサイクル後になってようやく準備ができている。したがって、最大で１７個の積が同一クロックサイクルに処理されている。
【０００８】
効率的なパイプライン型乗算器を目指して、多倍長整数計算は、パイプラインが一杯の状態を保つように設計されている。新しい計算がまだ進行中である結果に依存する状況を回避しなければならない。このような状況では、待機状態を挿入しなければならないであろう。これが、ＲＳＡのような計算とは異なって楕円曲線計算のためのモンゴメリ乗算器を設計する理由である。
【０００９】
乗算の次に、乗算器は、２回の加算Ｐ  ＝  Ｘ・Ｙ  ＋  Ａ  ＋  Ｂを実行する。一方の加算は、２個の多倍長整数の乗算のために必要であり、この場合、乗算は、多数の基本的な３２＊３２ビット乗算に分けられる。
【００１０】
パイプライン型乗算器は、例えば、８＊８ビット、または、１６＊１６ビットのような様々なビット数のため設計することができる。
【００１１】
（２．  モンゴメリ乗算）
モンゴメリ乗算は、積Ｐ  ＝  ｘ・ｙ・Ｒ−１ ｍｏｄ  ｐを計算する。ここで、ｘおよびｙは乗算される入力であり、ｐは乗算の法である。さらに、Ｒ＝２ｎであり、ここで、ｎはシステムのビット数であり、例えば、ＲＳＡのようなシステムでは１０２４であり、楕円曲線では１６０である。一例として、１７段のステージをもつ３２＊３２ビット乗算器が選択される。
【００１２】
（３．  基底Ｂを用いるモンゴメリ乗算）
この方法は、Ｎｗが大きい値である場合、ならびに、ＲＳＡの場合に適している。
【００１３】
Ｂ＝２３２であり、プロセッサのワードサイズは３２ビットであると仮定する。
【００１４】
Ｒ＝ＢＮｗであり、Ｎｗは多倍長整数の３２ビットワードの個数である。
【００１５】
ａ［ｉ］は数ａのｉ番目の３２ビットワードである。
【００１６】
Ｔ［０］は、一時変数Ｔの最下位３２ビット部分である。
【００１７】
事前に格納された定数：
ｍ'＝−（ｐ−１）  ｍｏｄ  Ｂ  （３２ビット幅）
素数ｐ
入力：ａ  ｍｏｄ  ｐ，  ｂ  ｍｏｄ  ｐ
出力：モンゴメリ積：ＭｏｎＰｒｏ（ａ，ｂ）＝ａ・ｂ・Ｒ−１  ｍｏｄ  ｐ
演算は次の通りである。
【００１８】
Ｔ  ＝  ０
ｆｏｒ  ｉ＝０  ｔｏ  Ｎｗ−１
｛  Ｔ  ＝  Ｔ  ＋  ａ［ｉ］・ｂ；                ／／  Ｎｗ回乗算
Ｕｉ  ＝  Ｔ［０］・ｍ'  ｍｏｄ  Ｂ；            ／／  １回乗算
Ｔ  ＝  （Ｔ  ＋  Ｕｉ・ｐ）／Ｂ              ／／  Ｎｗ回乗算
｝
Ｉｆ  Ｔ  ＞  ｐ  ｔｈｅｎ  Ｔ  ＝  Ｔ−ｐ
（４．  ５１２ビットオペランドのための計算）
本例では、ａおよびｂは３２ビットワードである。最初に、Ｔ＝Ｔ＋ａ［ｉ］・ｂがｉ＝０から計算される。
【００１９】
最初の計算はタイムスロット０で始まり、最後の計算はタイムスロット１５で始まる。タイムスロット１６に待機サイクルが加わる。
【００２０】
最初の結果Ｔ［０］は時点１７に作動可能である。次に、そのタイムスロットから、タイムスロット３４の出力である積Ｕｉ＝Ｔ［０］・ｍ'を計算する。
【００２１】
次の一連の計算は（Ｔ＋Ｕｉ・ｐ）／Ｂであり、これは、タイムスロット３４で始まり、タイムスロット４９で終わる。その最初の結果はタイムスロット５１で出力されるが、その結果は常に零であるため棄てられる。２番目の結果はタイムスロット５２で出力される。
【００２２】
タイムスロット５２以降、ループが改めて始まる。そのループは、前のラウンドの結果が作動可能となると直ちに前のラウンドの結果を使用する。
【００２３】
１６回のラウンドがあるので、タイムスロットの総数は１６＊５２＝８３２個である。
【００２４】
完全な結果はタイムスロット８４８で準備ができている。
【００２５】
（５．  １０２４個のオペランドのための計算）
最初に、Ｔ＝Ｔ＋ａ［ｉ］・ｂがｉ＝０から計算される。
【００２６】
最初の１７個の積を計算し始める。
【００２７】
最初の結果Ｔ［０］は時点１７に準備ができる。そのタイムスロットで、タイムスロット３４の出力である積Ｕｉ＝Ｔ［０］・ｍ'を計算する。タイムスロット１８から３２まで、残りの積Ｔ＝Ｔ＋ａ［ｉ］・ｂを計算する。
【００２８】
次の一連の計算は（Ｔ＋Ｕｉ・ｐ）／Ｂであり、これは、タイムスロット３４で始まり、タイムスロット６５で終わる。その最初の結果は、タイムスロット６６で新しいラウンドが開始したときに準備できる。
【００２９】
３２回のラウンドがあるので、タイムスロットの総数は３２＊６６＝２１１２個である。
【００３０】
完全な結果はタイムスロット２１２８で準備ができている。
【００３１】
（６．  ２０４８ビットオペランドのための計算）
最初に、Ｔ＝Ｔ＋ａ'［ｉ］・ｂ'がｉ＝０から計算される。
【００３２】
最初の１７個の積を計算し始める。
【００３３】
最初の結果Ｔ［０］は時点１７に準備ができる。そのタイムスロットで、タイムスロット３４の出力である積Ｕｉ＝Ｔ［０］・ｍ'を計算する。タイムスロット１８からＮｗまで、残りの積を計算する。
【００３４】
次の一連の計算は（Ｔ＋Ｕｉ・ｐ）／Ｂであり、これは、タイムスロットＮｗで始まり、タイムスロット２Ｎｗ−１で終わる。
【００３５】
その最初の結果は、タイムスロット２Ｎｗで新しいラウンドが開始したときに準備できる。
【００３６】
Ｎｗ回のラウンドがあるので、タイムスロットの総数はＮｗ・（２Ｎｗ＋１）個である。
【００３７】
完全な結果はタイムスロットＮｗ・（２Ｎｗ＋１）＋１７（＝８２７３（２０４８ビットに対する））で準備ができている。
【００３８】
（７．  基底Ｒを用いるモンゴメリ乗算）
このアルゴリズムは、Ｎｗの値が小さい場合、ならびに、楕円曲線の場合に適している。
【００３９】
Ｂ＝２３２である（プロセッサのワードサイズは３２ビットであると仮定する）。
【００４０】
Ｒ＝ＢＮｗである（Ｎｗは多倍長整数の３２ビットワードの個数である）。
【００４１】
事前に格納された定数：
ｍ'＝−（ｐ−１）  ｍｏｄ  Ｒ  （ｍ'はＮｗ３２ビット幅である）
素数ｐ
入力：ａ  ｍｏｄ  ｐ，  ｂ  ｍｏｄ  ｐ
出力：ＭｏｎＰｒｏ（ａ，ｂ）＝ａ・ｂ・Ｒ−１  ｍｏｄ  ｐ
Ｔ  ＝  ａ・ｂ
Ｕ  ＝  Ｔ・ｍ'  ｍｏｄ  Ｒ
Ｔ'  ＝  Ｔ  ＋  Ｕ・ｐ
Ｔ  ＝  Ｔ／Ｒ
ｉｆ  Ｔ＞ｐ  ｔｈｅｎ  Ｔ  ＝  Ｔ−ｐ
ＧＦ（２ｎ）上のシステムに対し、全ての加算は２を法とする。ここで、ｍ'は多項式Ｂ＝α３２の逆数である。
【００４２】
（８．  計算方法）
最初に、完全な積Ｔ＝ａ・ｂが計算される。これは、Ｎｗ２回の乗算を要する。最初のＴの結果が既に存在するので、その直後に開始することができる。積Ｔ・ｍ'の中で、Ｒよりも小さい積だけを計算すればよい。
【００４３】
積Ｔ［０］はタイムスロット１７で準備ができる。Ｔ［０］＊（ｍ［０］...ｍ［Ｎｗ−１］）の計算は、タイムスロットＮｗ２で始まり、Ｎｗ回の乗算を要する。
【００４４】
積Ｔ［１］はタイムスロット１７＋Ｎｗで準備ができる。Ｔ［１］＊（ｍ［０］...ｍ［Ｎｗ−２］）の計算は、タイムスロットＮｗ２＋Ｎｗで始まり、Ｎｗ−１回の乗算を要する。
【００４５】
積Ｔ［２］はタイムスロット１７＋２Ｎｗで準備ができる。Ｔ［２］＊（ｍ［０］...ｍ［Ｎｗ−３］）の計算は、タイムスロットＮｗ２＋２Ｎｗ−１で始まり、Ｎｗ−２回の乗算を要し、以下、同様に続く。
【００４６】
積Ｔ［ｊ］はタイムスロット１７＋ｊ・Ｎｗで準備ができる。Ｔ［ｊ］＊（ｍ［０］...ｍ［Ｎｗ−ｊ−１］）の計算は、タイムスロットＮｗ２＋（２Ｎｗ−ｊ＋１）・ｊ／２で始まり、Ｎｗ−ｊ回の乗算を要し、以下、同様に続く。
【００４７】
積Ｔ［Ｎｗ−１］はタイムスロット１７＋（Ｎｗ−１）・Ｎｗで準備ができる。Ｔ［Ｎｗ−１］＊ｍ［０］の計算は、タイムスロットＮｗ２＋（Ｎｗ＋２）・（Ｎｗ−１）／２で始まり、１回の乗算を要する。
【００４８】
Ｎｗ≧５に対し、積Ｔ［ｊ］は、新しい積Ｔ［ｊ］＊ｍ［０］が始まる前に、常に準備ができていることが証明できる。したがって、待機サイクルは不要である。
【００４９】
Ｕ［０］はタイムスロットタイムスロットＮｗ２＋１７で準備ができる。この瞬間から、積Ｕ・ｐが計算される。
【００５０】
最後の乗算がタイムスロットＮｗ２＋（Ｎｗ＋２）・（Ｎｗ−１）／２＋１で始まる。Ｎｗ＝５の場合、これはタイムスロット４０であり、Ｕ［０］はタイムスロット４２で始まる。このため、待機サイクルが２回必要である。より大きいＮｗの値の場合は、待機サイクルは不要である。
【００５１】
Ｕ・ｐの計算はＮｗ２個のタイムスロットを必要とする。
【００５２】
タイムスロットの総数は、Ｎｗ＞５の場合に、２・Ｎｗ２＋（Ｎｗ＋２）・（Ｎｗ−１）／２＋１個である。
【００５３】
タイムスロットの総数は、Ｎｗ＝５の場合に、６７個である。
【００５４】
完全な結果は、２・Ｎｗ２＋（Ｎｗ＋２）・（Ｎｗ−１）／２＋１８で準備ができる。
【００５５】
（９．  修正ブースアルゴリズム）
修正ブースアルゴリズムは、部分積を実行するため被乗数の２ビットを利用するように設計される。これは部分積の回数を半分にする。
【００５６】
最初に、乗数Ｙが記録され、ここで、ｙ'ｉは、−２、−１、０、＋１および＋２の値をとる（符号付き１０進数表記）。
【００５７】
ｙ'ｉ＝−２・ｙｉ＋１＋ｙｉ＋ｙｉ−１（ｉが偶数値である場合だけに定義される）
Ｙ＝ｙ'３０・２３０＋ｙ'２８・２２８＋．．．＋ｙ'０・２０
ｙｉ'＝−２ｙｉ＋１＋ｙｉ＋ｙｉ−１；
ｙｎ＝０
【数１】
2005513532.tif 000003
【００５８】
正しい結果を得るため、積ｙ０・Ｘからの減算が必要である。
【００５９】
（１０．  並列に実行される減算）
Ｘ＝ｘ３１・２３１＋ｘ３０・２３０＋．．．ｘ１・２１＋ｘ０・２０
Ｙ＝ｙ３１・２３１＋ｙ３０・２３０＋．．．ｙ１・２１＋ｙ０・２０
Ｗ＝ｗ３１・２３１＋ｗ３０・２３０＋．．．ｗ１・２１＋ｗ０・２０
Ｚ＝Ｘ・Ｙ＋Ｗ
この点に関して、図１はパイプライン型乗算器の一実施形態のブロック図である。図中、アスタリスク付きの円は乗算を実行し、プラス記号付きの円は、桁上げ保存(carry-save)演算を含む加算のような加算を実行する。種々のブロックは、その中に示された量を一時的に保持する。よりわかり易くするため、種々の相互接続は、それに沿って転送されるビットのビット順位（bit rankings)を表す。右側では、１列のブロックが必要な補正項を導入するため使用される。
【００６０】
左辺は、Ｚ＝Ｘ・Ｙ＋Ｗ＋ｙ０・Ｘを計算する。この最後の項は、アルゴリズムの所産である。右辺は、他の計算と並列に最後の項を減算する。これが発明である。
【００６１】
以下の実施形態は乗算がどのようにセットアップされるかを説明するが、実施形態は細部で変化しても構わない。
【００６２】
１番目のタイムスロットで、Ｚ０＝Ｘ・Ｙ（１：０）＋Ｗ０が計算され、レジスタＺ０に格納される。Ｘは２番目のＸレジスタへ転送され、Ｙ（３１：２）は２番目のＹレジスタへ転送される。
【００６３】
２番目のタイムスロットで、Ｚ１＝Ｘ・Ｙ（３：２）＋Ｚ０が計算され、レジスタＺ１に格納される。さらに、Ｘは３番目のＸレジスタへ転送され、Ｙ（３１：２）は３番目のＹレジスタへ転送される。
【００６４】
さらに、−ｙ０＊Ｘ（１：０）が計算され、Ｚ（１：０）に加えられ、以下同様に続く。
【００６５】
１６番目のタイムスロットで、Ｚ１５＝Ｘ・Ｙ（３１：３０）＋Ｚ１５が計算され、レジスタＺ１５に格納される。
【００６６】
さらに、−ｙ０＊Ｘ（３１：３０）が計算され、Ｚ（３１：３０）に加えられる。
【００６７】
ここで、Ｚ１５は６４ビットを含む。
【００６８】
最後のタイムスロット（１７番）において、上位３２ビットはＺ１６およびＺ１５へ転送され、２個の補正ビットが前のＺ１６の値に加算され、これが出力される。
【００６９】
多倍長整数乗算を実行するとき、Ｙｉは、Ｘ０、Ｘ１、．．．、ＸＮｗ−１と組み合わせてＮｗ回入力される。多倍長整数計算のはじめに、Ｚ１６は０にセットされる。Ｘ０・Ｙｉ＋Ｗが出力Ｚに達したときに限り、Ｚ１６＝０が加算される。
【００７０】
（１１．  ＧＦ（２ｎ）のモンゴメリ乗算）
楕円曲線計算は、ガロア体ＧＦ（２ｎ）上で定義することも可能である。ガロア体における全ての加算（ここでは「＋」によって示されている）は、２を法とする剰余系である（排他的論理和）。ガロア体における多項式の次数は、最大で次数ｎ−１である。したがって、ｎ＝３２であるとき、多項式ＸおよびＹは以下の通り定義される（全ての係数は０または１である。）。
【００７１】
Ｘ＝ｘ３１・α３１＋ｘ３０・α３０＋．．．ｘ１・α１＋ｘ０・α０
Ｙ＝ｙ３１・α３１＋ｙ３０・α３０＋．．．ｙ１・α１＋ｙ０・α０
さらに既約多項式が存在し、この多項式は次のように定義される。
【００７２】
ｐ＝ｐｎ・αｎ＋ｐｎ−１・αｎ−１＋．．．ｐ１・α１＋ｐ０・α０
積Ｐ  ＝  Ｘ・Ｙ  ｍｏｄ  ｐ  は次式によって計算される。
【００７３】
（ｘｎ−１・αｎ−１＋ｘｎ−２・αｎ−２＋．．．ｘ１・α１＋ｘ０・α０）・（ｙｎ−１・αｎ−１＋ｙｎ−２・αｎ−２＋．．．ｙ１・α１＋ｙ０・α０）  ｍｏｄ  ｐ
積Ｘ・Ｙは、次に、多項式ｐによって除算され、その余りが結果である。余りの次数は常にｐの次数よりも低い。
【００７４】
Ｘ、Ｙとｐの双方は多倍長整数で表現することができる。
【００７５】
可約積の計算は、内部の加算が２を法とする剰余系で行われるように修正された標準の積計算によって行うことができる。次に、除算は、加算が２を法とする剰余系であり、余りを保持する点を除いて標準的に行われる。
【００７６】
しかし、より高速なモンゴメリ乗算を実行してもよい。
【００７７】
（１２．  モンゴメリ乗算）
モンゴメリ乗算は、積が適当な因子Ｒ、例えば、α３２またはα１６０によって割り切れるように、素数（既約多項式）の倍数を（部分）積に加算する。多項式を２進表現した場合には、代わりに２３２または２１６０が想定される。以下、ｍ'は、ｍ'  ＝  ｐ−１  ｍｏｄ  Ｒとして定義され、ここで、ｐ−１はｐ・ｐ−１  ｍｏｄ  Ｒ  ＝  １のように定義される。
【００７８】
次に、同じアルゴリズムが以下の点を適合させて適用される。
【００７９】
乗算内部の加算は２を法とする剰余系である。
【００８０】
最後の減算は省略される。
【００８１】
この構成をさらに詳細に説明する。上記に加えて、種々のさらなる詳細、実施形態、および、解説が補足として以下に示される。
【００８２】
（１３．  多倍長整数の乗算器および加算器）
定義：
Ｘ＝ｘＮｗ−１・ＢＮｗ−１＋．．．＋ｘ２・Ｂ２＋ｘ１・Ｂ１＋ｘ０・Ｂ０
Ｙ＝ｙＮｗ−１・ＢＮｗ−１＋．．．＋ｙ２・Ｂ２＋ｙ１・Ｂ１＋ｙ０・Ｂ０
Ｐｉ＝ｐｉＮｗ・ＢＮｗ−１＋．．．＋ｐｉ２・Ｂ２＋ｐｉ１・Ｂ１＋ｐｉ０・Ｂ０
Ｐ＝ｐｋ・Ｂｋ＋．．．＋ｐ２・Ｂ２＋ｐ１・Ｂ１＋ｐｉ０・Ｂ０（ここで、ｋ＝２Ｎｗー１）
Ｂ＝２３２
ｍ＝Ｎｗ−１
多倍長整数乗算は、２個の３２ビットワードの多数の乗算を含む。この実施形態は、パイプライン型３２ビット乗算器（図１および４を参照）を使用し、この乗算器は、あらゆるタイムスロットで、３個の新しい３２ビットオペランド（Ｘ＊Ｙ＋Ｚ）を受け取る。このような乗算器は非常に高速である。しかし、乗算器の出力は、１７タイムスロット後にようやく準備ができている。したがって、最大で１７の乗算が同時に計算される。しかし、進行中の乗算の結果を用いて乗算をしたいとき、結果の準備ができるまで待たなければならない。これは、待機サイクルを持ち込む可能性があり、性能を低下させるであろう。
【００８３】
Ｚ  ＝  Ｘ・Ｙ  ＋  Ｗ
Ｚ  ＝  Ｘ・｛Ｙ０・Ｂ０  ＋  Ｙ１・Ｂ１  ＋  ．．  Ｙｍ・Ｂｍ｝  ＋  Ｗ
Ｚ、ＸおよびＷは、Ｎｗ−１個の３２ビットワードのサイズをもつ。Ｙｉは３２ビットの幅である。
【００８４】
Ｗ  ＝  Ｗ０・Ｂ０  ＋  Ｗ１・Ｂ１  ＋  ．．  Ｗｍ・Ｂｍ｝
中間結果は、
Ｗｉ  ＝  Ｗｉ１・Ｂ０  ＋  Ｗｉ２・Ｂ１  ＋  ．．  Ｗｉ，ｍ＋１・Ｂｍ
である。
【００８５】
Ｐ０  ＝  Ｘ・Ｙ０  ＋  Ｗが計算される。その結果は、Ｐ０  ＝  Ｗ０・Ｂ  ＋  Ｚ０に分けられる。
【００８６】
Ｐ１  ＝  Ｘ・Ｙ１  ＋  Ｗ０が計算される。その結果は、Ｐ１  ＝  Ｗ１・Ｂ  ＋  Ｚ１に分けられる。
【００８７】
Ｐ２  ＝  Ｘ・Ｙ２  ＋  Ｗ１が計算される。その結果は、Ｐ２  ＝  Ｗ２・Ｂ  ＋  Ｚ２に分けられる。
【００８８】
．．．
Ｐｍ  ＝  Ｘ・Ｙｍ  ＋  Ｗｍ−１が計算される。
【００８９】
Ｚｊ  ＝  Ｐｍ，ｊ    但し、ｊ≧ｍ
したがって、Ｐｉ  ＝  Ｘ・Ｙｉ  ＋  Ｗｉを計算する関数が必要である。
【００９０】
この点に関して、図２は、（Ｘ＊Ｙ＋Ｗ）を計算する構成のブロック図である。
【００９１】
Ｐｉ  ＝  Ｘ・Ｙｉ  ＋  Ｗ
この計算は前述の計算の一部である。ＸおよびＷのサイズは、ｍ＝（Ｎｗ−１）個の３２ビットワードである。Ｙｉは３２ビットの幅である。
【００９２】
Ｓ１  ＝  ｘ０・ｙｉ  ＋  ｗ０が計算される。Ｓ１は、Ｚ１・Ｂ  ＋  Ｐ０に分けられる。
【００９３】
Ｓ２  ＝  ｘ１・ｙ１  ＋  ｗ１  ＋  Ｚ１が計算される。Ｓ２は、Ｚ２・Ｂ  ＋  Ｐ１に分けられ、以下同様に続く。
【００９４】
Ｓｍ  ＝  ｘｍ・ｙ１  ＋  ｗｍ  ＋  Ｚｍ−１が計算される。Ｓｍは、Ｐｍ＋１・Ｂ  ＋  Ｐｍに分けられる。
【００９５】
関連した実施形態が図３に示され、図３は、（Ｘ＊Ｙ＋Ｗ）に従って多倍長整数乗算を実行する構成のブロック図である。
【００９６】
Ｓ  ＝  ｘ・ｙ  ＋  ｗ  ＋  ｚの計算は、既に部分的に説明した図１のパイプライン型乗算器によって行われる。
【００９７】
ＧＦ（２ｎ）上の計算のため、加算は２を法とする剰余系である。したがって、桁上げはない。
【００９８】
（１４．  パイプライン型乗算器）
Ｘ＝ｘ３１・２３１＋ｘ３０・２３０＋．．．ｘ１・２１＋ｘ０・２０
Ｙ＝ｙ３１・２３１＋ｙ３０・２３０＋．．．ｙ１・２１＋ｙ０・２０
Ｗ＝ｗ３１・２３１＋ｗ３０・２３０＋．．．ｗ１・２１＋ｗ０・２０
Ｚ＝Ｘ・Ｙ＋Ｗ
左辺は、Ｚ  ＝  Ｘ・Ｙ  ＋  Ｗ  ＋  ｙ０・Ｘを計算する。この最後の項は、使用されたアルゴリズムの所産である。右辺は最後の項を減算する。
【００９９】
次に、乗算をセットアップする方法についてのアイデアを示すが、実施形態は詳細において変化しても構わない。
【０１００】
１番目のタイムスロットで、Ｚ０  ＝  Ｘ・Ｙ（１：０）  ＋  Ｗ０が計算され、レジスタＺ０に格納される。Ｘは２番目のＸレジスタへ転送され、Ｙ（３１：２）は２番目のＹレジスタへ転送される。
【０１０１】
２番目のタイムスロットで、Ｚ１  ＝  Ｘ・Ｙ（３：２）  ＋  Ｚ０が計算され、レジスタＺ１に格納される。Ｘは３番目のＸレジスタへ転送され、Ｙ（３１：２）は３番目のＹレジスタへ転送される。
【０１０２】
さらに、−ｙ０＊Ｘ（１：０）が計算され、Ｚ（１：０）に加えられる。
【０１０３】
・・・以下同様に続く。
【０１０４】
１６番目のタイムスロットで、Ｚ１５  ＝  Ｘ・Ｙ（３１：３０）  ＋  Ｚ１５が計算され、レジスタＺ１５に格納される。
【０１０５】
さらに、−ｙ０＊Ｘ（３１：３０）が計算され、Ｚ（３１：３０）に加えられる。ここで、Ｚ１５は６４ビットを含む。
【０１０６】
最後のタイムスロット（１７番）において、上位３２ビットはＺ１６およびＺ１５へ転送され、２個の訂正ビットが前のＺ１６の値に加算され、これが出力される。
【０１０７】
第１３パラグラフで説明したように多倍長整数乗算を実行するとき、Ｙｉは、Ｘ０、Ｘ１、．．．、ＸＮｗ−１と組み合わせてＮｗ回入力される。Ｘ０・Ｙｉ  ＋  Ｗが出力Ｚに達したとき、Ｚ１６の内容が加算されるのではなく、何も加算されない。Ｚ１６は第１３パラグラフのＺｉの関数であり、その部分がある乗算から次の乗算へ転送される。
【０１０８】
（１５．  修正ブースアルゴリズム）
最初に、乗数Ｙが記録され、ここで、ｙ'ｉは、−２、−１、０、＋１および＋２の値をとる（符号付き１０進数表記）。
【０１０９】
ｙ'ｉ＝−２・ｙｉ＋１＋ｙｉ＋ｙｉ−１（ｉが偶数値である場合だけに定義される）
Ｙ＝ｙ'３０・２３０＋ｙ'２８・２２８＋．．．＋ｙ'０・２０
例えば、ｙ＝２９ｄｅｃ＝０１１１０１ｂｉｎであるならば、ｙ'＝（２  １  １）ｓｄ＝２・２４−１・２２＋１＝２９ｄｅｃであり、ここで、１は−１を表す。
【０１１０】
使用される式は、修正ブースアルゴリズムに関する前のパラグラフ（第９パラグラフ）で説明した式である。
【０１１１】
正しい結果を得るため、積ｙ０・Ｘからの減算が必要である。
【０１１２】
２による乗算は、被乗数を左へ１ビットシフトする。
【０１１３】
部分積は、基数２の表記でコード化され、ここで、全ての積は、−１、０または＋１の値をとり得る。
【０１１４】
次に、積が１６段のステージで計算される。あらゆるステージで、部分積ｙ'ｉ・Ｘ・２ｉが計算され、前の結果に加算され、例えば、ｘ＝５３ｄｅｃ＝１１０１０１ｂｉｎ、かつ、ｙ＝２９（ｙ'＝（２  １  １）ｓｄ）である。
【０１１５】
３２ビットオペランドの場合、１５回の加算を実行しなければならない。これは、標準の全加算器では桁上げを波及させる必要があるので、非常に長時間を要する。これを回避するため、桁上げ伝播の無い加算器を使用する。この点に関して、図５は桁上げ伝播の無い加算器の構成を示す図である。
【０１１６】
（１６．  冗長２進表記）
加算器の被加数および加数は冗長２進表記で表され、この表記は符号付き桁表記でもある。それは、固定基数２と、数字セット｛１，  ０，  １｝とをもち、ここで、ここで、１は−１を表す。ｎ桁の冗長２進整数Ｙの値は、ｙｎ−１・２ｎ−１＋ｙｎ−２・２ｎ−２＋．．．＋ｙ１・２１＋ｙ０・２０であり、ここで、ｙｉの値は、−１、０または１である。
【０１１７】
整数は様々な冗長２進表記で表現することができ、例えば、［０１０１］ＳＤ２＝［０１１１］ＳＤ２＝［１１０１］ＳＤ２＝［１１１１］ＳＤ２＝［１０１１］ＳＤ２＝５ｄｅｃである。「０」だけは唯一の表現形式：［００．．．０］を持つ。
【０１１８】
通常の２進表記から冗長２進表記への変換は簡単であり、どちらでも同じである。
【０１１９】
冗長２進表記から通常の２進表記への変換は、以下の減算：Ｘｂｉｎ  ＝  Ｘ＋  −  Ｘ−によって行われ、ここで、Ｘ＋は、すべての「１」を「０」で置換することによってＸｓｄ２から得られ、Ｘ−は、すべての「１」を「０」で置換し、すべての「１」を「１」で置換することによってＸｓｄ２から得られる。例えば、Ｘ＝［１０１１］ＳＤ２＝５ｄｅｃであるならば、Ｘ＋＝［１０００］ｂｉｎ＝８ｄｅｃであり、Ｘ−＝［００１１］ｂｉｎ＝３ｄｅｃである。
【０１２０】
変数の否定は、すべての「１」を「１」で置換し、「１」を「１」で置換することによって行われる。例えば、Ｘ＝［１０１１］ＳＤ２＝５ｄｅｃであるならば、−Ｘ＝［１０１１］ＳＤ２＝−５ｄｅｃである。
【０１２１】
変数は次のように符号化する（表１を参照せよ）。
【表１】
2005513532.tif 000004
【０１２２】
組み合わせ１１は決して使用されない。
【０１２３】
したがって、Ｘが入力され、Ｘ＝１であるとき、条件ｘ＋＝１は満足する。同様に、Ｘ＝１であるとき、ｘ−＝１が満足する。
【０１２４】
（１７．  桁上げ伝播の無い加算器）
この表現は、起こり得る桁上げが次の桁で吸収され、次の桁上げに影響を与えないように選択される。したがって、このような加算器の速度は、３２ビット全加算器の速度よりもかなり速い。
【０１２５】
３２＊３２ビット乗算器に関しては、１６回の加算がある（前の乗算の上側の最上位ワードが含まれる）。次に、最後だけで、冗長２進表記が通常の２進表記に変換される。この変換は伝播無しではない。
【０１２６】
加算は、（理論的には）２ステップで行われる。最初に、中間の和ｓｉと中間の桁上げｃｉが計算される。次のステップで、両方は最終的な和（ｓｕｍｉ）に変換される。この中間の桁上げは、最大で現在および前の桁の値に依存するが、それよりも前の桁の値には依存しない。
【０１２７】
ｃｉおよびｓｉは、次式：２ｃｉ  ＋  ｓｉ  ＝  ｘｉ  ＋  ｙｉを満足する。さらに、ｃｉ−１およびｓｉは、両方が決して１と１にならないように選択される。
【０１２８】
この点に関して、図６は、中間のキャリーおよび和の量の生成を説明する図表である。
【０１２９】
和Ｓｉ  ＝  ｃｉ  ＋  ｓｉ−１は、新しいキャリーを与えない。
【０１３０】
タイプ１、３、４および６：  ｃｉ−１  ＋  ｓｉ  ＝  ｃｉ−１
タイプ２ａ、５ａ：  ｃｉ−１  ≠  １、即ち、０または１であるので、ｃｉ−１  ＋  ｓｉは、１または０である。
【０１３１】
タイプ２ｂ、５ｂ：  ｃｉ−１  ≠  １、即ち、０または１であるので、ｃｉ−１  ＋  ｓｉは、１または０である。
【０１３２】
これは以下の例によって説明される。
【０１３３】
Ｘ            ［１  ０  １  ０  １  ０  ０  １］ｓｄ２  ＝  ８７ｄｅｃ
Ｙ            ［１  １  １  ０  ０  １  １  １］ｓｄ２  ＝  １０１ｄｅｃ
−−−−−−−−−−−＋
Ｓ             ０  １  ０  ０  １ １  １  ０
Ｃ         １  １  ０  ０  ０  １  ０  １
ー−−−−−−−−−−−＋
Ｓｕｍ    １  １  １  ０  ０  ０  １  ０  ０  ＝  １８８ｄｅｃ
（１８．  通常の２進表記への変換）
最後のステージにおいて、結果は通常の２進表記へ変換される。Ｘ  ＝  Ｘ＋  −  Ｘ−  であり、ここで、Ｘ＋は全てのｘｉ＋により形成され、Ｘ−は全てのｘｉ−により形成される。
【０１３４】
ｘｉ＋およびｘｉ−は決して同時に１ではないので、全減算器は不要である。したがって、異なる方法を試す。
【０１３５】
ここでは、右から左までの全ての１を除去する。
【０１３６】
右からの借りが無いとき：
次の桁が「１」であるとき、その桁が維持され、左への借りは無い。
【０１３７】
次の桁が「０」であるとき、その桁が維持され、左への借りは無い。
【０１３８】
次の桁が「１」であるとき、その「１」は「１」によって置換され、左への借りがある。
【０１３９】
右からの借りがあるとき：
次の桁が「１」であるとき、その「１」は「０」によって置換され、左への借りは無い。
【０１４０】
次の桁が「０」であるとき、その「０」は「１」によって置換され、左への借りがある。
【０１４１】
次の桁が「１」であるとき、その「１」は「０」によって置換され、左への借りがある。
【０１４２】
しかし、最も左の桁が「１」であり、最も右の桁が「１」であり、その間の全ての桁が「０」であるならば（１０．．．０１）、これは非常に大きい遅延を生じさせるであろう。
【０１４３】
遅延を減少させるため、３２ビットを４ビットずつの８個のグループに分ける。
【０１４４】
最も左の非零の桁が「１」であるとき、次の左のグループへの借りが生成される。
【０１４５】
このグループに少なくとも１個の「１」が存在するとき、右のグループからの借りは次のグループへ伝播しない。
【０１４６】
（１９．  ＧＦ（２Ｎ）用の乗算器ロジック）
Ｘ＝ｘ３１・α３１＋ｘ３０・α３０＋．．．ｘ１・α１＋ｘ０・α０
Ｙ＝ｙ３１・α３１＋ｙ３０・α３０＋．．．ｙ１・α１＋ｙ０・α０
Ｗ＝ｗ３１・α３１＋ｗ３０・α３０＋．．．ｗ１・α１＋ｗ０・α０
上記ベクトルを表現するため、上記式の「α」を「２」と読んでも構わない。
【数２】
2005513532.tif 000005
【０１４７】
なお、上記数式において、＋を丸で囲んだ記号は排他的論理和を表している。
ブース符号化に関してＧＦ（２ｎ）に等価なものはない。
【０１４８】
１番目のタイムスロットで（図４を参照）、Ｘ・Ｙ（１：０）とＷとの排他的論理和が計算され、レジスタＺ０に格納される。Ｘは２番目のＸレジスタへ転送され、Ｙ（３１：２）は２番目のＹレジスタ（Ｙ）へ転送される。
【０１４９】
２番目のタイムスロットで、Ｘ・Ｙ（３：２）とＺ０との排他的論理和が計算され、レジスタＺ０に格納される。Ｘは２番目のＸレジスタへ転送され、Ｙ（３１：４）は３番目のＹレジスタ（Ｙ）へ転送される。
【０１５０】
１６番目のタイムスロットで、Ｚ１５＝Ｘ・Ｙ（３１：３０）とＺ１５との排他的論理和が計算され、レジスタＺ１５に格納される。
【０１５１】
ここで、Ｚ１５は６４ビットを収容する。
【０１５２】
最後のタイムスロット（１７番）において、上位３２ビットはＺ１６へ転送され、Ｚ１５は前のＺ１６の値に加算され、これが出力される。
【０１５３】
第１３パラグラフで説明したように多倍長整数乗算を実行するとき、Ｙｉは、Ｘ０、Ｘ１、．．．、ＸＮｗ−１と組み合わせてＮｗ回入力される。Ｘ０．Ｙｉ                Ｗが出力Ｚに達したとき、Ｚ１６の内容が加算されるのではなく、何も加算されない。Ｚ１６は第１３パラグラフのＺｉの関数であり、その部分がある乗算から次の乗算へ転送される。
【０１５４】
特に、図４は、ＧＦ（２ｎ）で動作するパイプライン型乗算器の実施形態の構成の説明図である。
【０１５５】
（加算）
加算は２個の変数の排他的論理和(exor)である。桁上げはない。
【０１５６】
（符号化）
ロジックをＧＦ（ｐ）のそれと合成するため、以下の冗長符号化を使用すべきである。したがって、Ｘ  ＝  ｘ＋  ＾  ｘ−であり、ここで、＾は、論理的なＯＲ演算を表す。
【表２】
2005513532.tif 000006
【０１５７】
（２０．  ＧＦ（ｐ）とＧＦ（２ｎ）の両方のためのロジック）
両方の乗算器ステージは、次の構造ｚｊ  ＝  ａｉ・ｘｊ−１        ｂｉ・ｘｊを使用する。
【０１５８】
ＧＦ（ｐ）
ＧＦｐ  ＝  １
ｙ'ｉ  ＝  −２・ｙｉ＋１  ＋  ｙｉ  ＋  ｙｉ−１  （但し、ｉは奇数の場合だけ、以下の表３を参照）
【表３】
2005513532.tif 000007
【０１５９】
ＧＦ（２ｎ）
【数３】
2005513532.tif 000008
【０１６０】
合成後
【数４】
2005513532.tif 000009
【０１６１】
（２１．  桁上げ伝播の無い加算）
【表４】
2005513532.tif 000010
【０１６２】
表４は、表１に従って符号化した図６と同じである。
【数５】
2005513532.tif 000011
【０１６３】
Ｓｉ  ＝  ｃｉ−１  ＋  ｓｉ
【表５】
2005513532.tif 000012
【０１６４】
（２２．  ＧＦ（２ｎ））
Ｓｉ  は、ｘｉ  とｙｉ  との排他的論理和の演算によって計算される。
ＧＦ（ｐ）システムにおける桁上げを抑えた場合、ＧＦ（ｐ）の規則に従って生成されたＳｉ、即ち、表２に従って符号化されたＳｉが正しい答えを与えることは明らかである。
【０１６５】
合成ロジック
【数６】
2005513532.tif 000013
【０１６６】
（２３．  冗長２進から２進への変換）
入力は、ｘｉ  ＝  ｛１，  ０，  １｝となるベクトルＸである。出力は、ｙｉ  ＝  ｛０，  １｝となるベクトルＹである。このベクトルＸは、４ビットずつの８個のグループに分割され、ｉ  ＝  ４ｍ＋ｎ  （ｎ＝０．．３，  ｍ＝０．．７）である。
【０１６７】
グループ間：
グループ借りｇｍは、このグループの最も左の非零の桁が「１」であるときに生成される。
【０１６８】
グループ借りｇｍ−１が伝播するのは、グループが全く「１」を含まないときである（ｇｍ  ＝  ｇｍ−１）。
【０１６９】
グループ内：
借りｂｉは、桁が「１」であるときに生成される。
【０１７０】
借りｂｉ−１は、桁が「１」ではないとき、即ち、ｂｉ  ＝  ｂｉ−１であるときに伝播する。
【表６】
2005513532.tif 000014
【０１７１】
【数７】
2005513532.tif 000015
【０１７２】
（２４．  ＧＦ（２ｎ））
この変換は、借りが無いので簡単である。全ての借りを抑えた場合、ＧＦ（ｐ）の回路は正しい答えを与える。
【０１７３】
合成ロジック
【数８】
2005513532.tif 000016
【０１７４】
パイプライン型乗算器
図１に示されたようなパイプライン型乗算器はＧＦ（２ｎ）のためにも使用可能であるが、−Ｙ［０］を右辺で「０」にセットしなければならない。その他の全ての適合については上記の通りである。
【図面の簡単な説明】
【０１７５】
【図１】パイプライン型乗算器のブロック図である。
【図２】多倍長整数乗算Ｘ＊Ｙ＋Ｗのブロック図である。
【図３】多倍長乗算Ｘｉ・Ｙ＋Ｗのブロック図である。
【図４】ガロア体ＧＦ（２ｎ）用のパイプライン型乗算器である。
【図５】桁上げ伝播の無い加算器の処理説明図である。
【図６】中間の桁上げおよび和の量を示す図表である。
【図１】
2005513532.tif 000017
【図３】
2005513532.tif 000018
【図２】
2005513532.tif 000019
【図４】
2005513532.tif 000020
【図５】
2005513532.tif 000021
【図６】
2005513532.tif 000022
【国際調査報告】
2005513532.tif 000023
2005513532.tif 000024
2005513532.tif 000025