(57)【要約】  一緒に加算され乗算されるべき幾つかの数字を受け取る、ｐ組のパイプライン処理された論理レジスタの対を含む乗算器−加算器を備えた少なくとも一つの計算セルと、低次及び高次に対応する少なくとも二つの出力とを備え、加算器が乗算器−加算器の二つの出力を受け、乗算器−加算器の最大周波数が加算器の最大周波数以上になるように数ｐが選択されることを特徴とする、モジュラー乗算を実行するための装置。【選択図】図１
2008535011.tif 000002
【特許請求の範囲】
【請求項１】
モジュラー乗算を実行するための装置であって、
一緒に加算され乗算されるべき幾つかの数字を受け取る、ｐ組のパイプライン処理された論理レジスタの対を含む乗算器−加算器（１）を備えた少なくとも一つの計算セルと、低次及び高次に対応する少なくとも二つの出力とを備え、加算器（２）が乗算器−加算器の二つの出力を受け、乗算器−加算器の最大周波数Ｆ１ｍａｘが加算器の最大周波数Ｆ２ｍａｘ以上になるように数ｐが選択されることを特徴とする装置。
【請求項２】
前記乗算器−加算器の最大周波数Ｆ１ｍａｘが、実質的に加算器の最大周波数Ｆ２ｍａｘに等しいことを特徴とする請求項１に記載の装置。
【請求項３】
入力が前記加算器のＬＳＢ出力と予め計算された定数とに対応する下方部分の乗算器（３）を備え、前記乗算器が深さｋにわたってパイプライン処理されていることを特徴とする請求項１に記載の装置。
【請求項４】
前記乗算器−加算器におけるデータの到着を遅らせるために適したレジスタ及びマルチプレクサの組を備えることを特徴とする、請求項１又は２に記載の装置。
【請求項５】
２ビット＋１ビット〜２ビットの補足的な加算器を備えることを特徴とする、請求項１又は２に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はモンゴメリーのモジュラー乗算を実行するための方法及び装置に関する。
【背景技術】
【０００２】
それはとりわけ暗号学の領域において、ＦＰＧＡ（フィールド・プログラマブル・ゲートアレイ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ））又はＡＳＩＣ（特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ））タイプの集積回路において用いられる。モジュラー乗算はモジュラーリング（Ｚ／ＮＺ）の上、又は素数ｐを有する体（Ｚ／ｐＺ）の上でなされる。
【０００３】
説明において、ｐ層を有するパイプライン処理された乗算器−加算器の動作周波数は、乗算器−加算器の層のしきいを横切るための時間の逆数で与えられるように定義される。
【０００４】
説明において、用語「パイプライン」（“ｐｉｐｅｌｉｎｅ”）は、論理相とそこから生じるアーキテクチャとの間にレジスタのバリヤを加えることにある作業として定義される。
【０００５】
モジュラー乗算は多くの公開鍵暗号方式（ＲＳＡ、ＥＣＤＳＡ）の中核にある。
【０００６】
暗号化作業及び署名の作業は、ハードウェア資源に関してとりわけ速く、柔軟で安価なアーキテクチャを必要とする様々な制約を示す。
二つの柔軟性レベルが従って定義される。
・第一レベルはアーキテクチャの統合以前に位置付けられる。アーキテクチャの設計は、与えられたハードウェア／時間の制約を満足できるように十分な自由度を備えなければならない。
・第二レベルはアーキテクチャの統合後に位置付けられる。
【０００７】
該アーキテクチャは、サイズが２５６−５１２ビットのＥＣＤＳＡ（楕円曲線電子署名アルゴリズム）タイプの演算、及び又サイズが１０２４−４０９６ビットのＲＳＡ（その発明者の名前から：リベスト、シャミール、アドレマン（Ｒｉｖｅｓｔ，Ｓｈａｍｉｒ，Ａｄｌｅｍａｎ））タイプの演算を実行できるように、様々なサイズのデータを処理可能でなければならない。
【０００８】
アーキテクチャの性能を評価するために、時間×面積の積が用いられる。時間はクロック周期の数に関して与えられる。面積は等価ＮＡＮＤゲートの数（ＡＳＩＣ）に関して、又は基本セル（ＦＰＧＡ又はフィールド・プログラマブル・ゲートアレイ用のＬＣ（論理セル（Ｌｏｇｉｃ  Ｃｅｌｌ））あるいはＣＬＢ（構成論理ブロック（Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｌｏｇｉｃ  Ｂｌｏｃｋ））、連続組合せブロック（ｓｅｑｕｅｎｔｉａｌ  ｃｏｍｂｉｎａｔｏｒｉａｌ  ｂｌｏｃｋｓ））に関して評価される。
【０００９】
従来技術は非対称の暗号法におけるモジュラー乗算を用いた、様々な例示的装置及び方法を説明している。
【００１０】
モジュラー乗算の最も頻繁な実行はシストリック型であり、モンゴメリー・アルゴリズムを使用する。多くの出版物がこれらの実行について扱っている。この分野の参考文献はピーター・ケルナーアップの「右方シフトアルゴリズムのクラス用シストリック線形アレイ」、ＩＥＥＥ  論文誌（計算機）、４３巻（１９９４年）、第８号、８９２〜８９８頁（Ａ  ｓｙｓｔｏｌｉｃ，ｌｉｎｅａｒ−ａｒｒａｙ  ｆｏｒ  ａ  ｃｌａｓｓ  ｏｆ  ｒｉｇｈｔ−ｓｈｉｆｔ  ａｌｇｏｒｉｔｈｍｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ  ４３  （１９９４），ｎｏ．８，８９２−８９８）による。
【００１１】
モジュラー乗算はまたバレットのモジュラー・リダクション法、ＣＨＥＳ’００、  ２０００年（Ｂａｒｒｅｔ’ｓ  Ｍｏｄｕｌａｒ  ｒｅｄｕｃｔｉｏｎ  ｍｅｔｈｏｄ，ＣＨＥＳ’００，２０００）に基づく、「バレット、ヨハン・グロースシェーデルの高速ＲＳＡハードウェアのアルゴリズム」（ａｌｇｏｒｉｔｈｍ  ｏｆ  Ｂａｒｒｅｔ，Ｊｏｈａｎｎ  Ｇｒｏｓｓｓｃｈａｅｄｌ，Ｈｉｇｈ  ｓｐｅｅｄ  ＲＳＡ  Ｈａｒｄｗａｒｅ）に従って実行できる。
【００１２】
後者の実行のタイプは有効ではあるが、それは所定のサイズに対して定義され、より大きなサイズの演算を取り扱えないため、柔軟ではないという欠点を示す。
【００１３】
「エキゾチック」（“Ｅｘｏｔｉｃ”）な数表現（すなわち、例えばＲＮＳ（剰余数システム（Ｒｅｓｉｄｕｅ  Ｎｕｍｂｅｒ  Ｓｙｓｔｅｍ））表現）のような、異例の表現も例えば、Ｌ−Ｓ  ディディエ、Ｊ−Ｃ  バジャード、及びＰ．ケルナーアップの「ＲＮＳモンゴメリー乗算アルゴリズム」、ＡＲＩＴＨ１３の議事録、ＩＥＥＥ  コンピュータ・ソサエティー、１９９７年、２３４〜２３９頁（Ｌ−Ｓ  Ｄｉｄｉｅｒ，Ｊ−Ｃ  Ｂａｊａｒｄ  ａｎｄ  Ｐ．  Ｋｏｒｎｅｒｕｐ，Ａｎ  ＲＮＳ  Ｍｏｎｔｇｏｍｅｒｙ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＲＩＴＨ１３，ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，１９９７，ｐｐ．２３４−２３９）の、モジュラー乗算の実行を並列化するために又用いられる。しかしながら、この解決策は相当なハードウェア資源を必要とし、そして柔軟性の問題を解決しない。
【００１４】
柔軟なアーキテクチャを示す装置、又は「拡張性のあるハードウェア」もまた知られている。そのようなアーキテクチャの最初の出版物はアレキサンダー  Ｆ．テンカ及びセティン  Ｋ．コッスの「モンゴメリー乗算用の拡張可能なアーキテクチャ」、ＣＨＥＳ’９９、  １９９９年（Ａｌｅｘａｎｄｒｅ  Ｆ．Ｔｅｎｃａ  ａｎｄ  Ｃｅｔｉｎ  Ｋ．Ｋｏｃ，Ａ  ｓｃａｌａｂｌｅ  ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｍｏｎｔｇｏｍｅｒｙ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ，ＣＨＥＳ’９９，１９９９）による。
【００１５】
別のより最近の出版物は、この論文において展開された考えに再び手を加え、改善及び拡張を提案している。そのようなものは、下記におけるケースである。
・アレキサンダー  Ｆ．テンカ及びセティン  Ｋ．コッス、「モンゴメリーのアルゴリズムに基づくモジュラー乗算用の拡張可能なアーキテクチャ」、ＩＥＥＥ  論文誌（計算機）、５２巻（２００３年）、第９号（Ａｌｅｘａｎｄｒｅ  Ｆ．Ｔｅｎｃａ  ａｎｄ  Ｃｅｔｉｎ  Ｋ．Ｋｏｃ，Ａ  ｓｃａｌａｂｌｅ  ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｂａｓｅｄ  ｏｎ  Ｍｏｎｔｇｏｍｅｒｙ’ｓ  Ａｌｇｏｒｉｔｈｍ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ｃｏｍｐｕｔｅｒｓ  ５２  （２００３），ｎｏ．９）。
・アレキサンダー  Ｆ．テンカ、セティン  Ｋ．コッス、エルケイ・サバス、「有限体ＧＦ（ｐ）及びＧＦ（２ｎ）用の拡張可能で統一された乗算器アーキテクチャ」、ＣＨＥＳ’００、  ２０００年（Ａｌｅｘａｎｄｒｅ  Ｆ．Ｔｅｎｃａ，Ｃｅｔｉｎ  Ｋ．Ｋｏｃ，ａｎｄ  Ｅｒｋａｙ  Ｓａｖａｓ，Ａ  ｓｃａｌａｂｌｅ  ａｎｄ  ｕｎｉｆｉｅｄ  ｍｕｌｔｉｐｌｉｅｒ  ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  ｆｉｎｉｔｅ  ｆｉｅｌｄ  ＧＦ（ｐ）  ａｎｄ  ＧＦ（２ｎ），ＣＨＥＳ’００，２０００）。
・アレキサンダー  Ｆ．テンカ、ゲオルギ・トドロフ、セティン  Ｋ．コッス、「拡張可能なモジュラー乗算器の高基数設計」、ＣＨＥＳ’０１、ＬＮＣＳ  ２１６２巻、２００１年、１８５〜２０１頁（Ａｌｅｘａｎｄｒｅ  Ｆ．Ｔｅｎｃａ，Ｇｅｏｒｇｉ  Ｔｏｄｏｒｏｖ  ａｎｄ  Ｃｅｔｉｎ  Ｋ．Ｋｏｃ，Ｈｉｇｈ−Ｒａｄｉｘ  Ｄｅｓｉｇｎ  ｏｆ  ａ  ｓｃａｌａｂｌｅ  ｍｏｄｕｌａｒ  ｍｕｌｔｉｐｌｉｅｒ，ＣＨＥＳ’０１，ｖｏｌ．ＬＮＣＳ  ２１６２，２００１，ｐｐ．１８５−２０１）。
・グンナー・ゴーバッツ、「バーサタイル・モンゴメリー乗算器アーキテクチャ」、博士論文、ウースター・ポリテクニック・インスティテュート、２００２年４月（Ｇｕｎｎａｒ  Ｇａｕｂａｔｚ，Ｖｅｒｓａｔｉｌｅ  Ｍｏｎｔｇｏｍｅｒｙ  Ｍｕｌｔｉｐｌｉｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅｓ，ＰｈＤ  ｔｈｅｓｉｓ，Ｗｏｒｃｅｓｔｅｒ  Ｐｏｌｙｔｅｃｈｎｉｃ  Ｉｎｓｔｉｔｕｔｅ，Ａｐｒｉｌ  ２００２）。
【００１６】
これらのアーキテクチャは、加算器及び乗算器からなる小さな基本セルの配線に基づく。これらの装置は柔軟性の問題に対処する。しかしながら、これらの構造は小さい内部バスのサイズ選択を伴う。モジュラー乗算を実行する繰り返し数は従って多い。
【００１７】
本発明による方法の装置及びステップを説明する前に、モンゴメリーのアルゴリズムに関する幾つかの注意が与えられる。用いられるモンゴメリーのアルゴリズムは次の通りである。
ＭＭｎＳ（Ａ，Ｂ，Ｎ）
Ｓ←ａ０Ｂ
Ｆｏｒ  ｉ＝１〜ｎ  ｄｏ
ｍｉ←Ｓ０Ｎ’ｍｏｄ  ｒ
Ｓ←ａｉＢ＋（ｍｉＮ＋Ｓ）／ｒ
ｍｎ＋１←Ｓ０Ｎ’ｍｏｄ  ｒ
Ｓ←（ｍｎ＋１Ｎ＋Ｓ）／ｒ
Ｒｅｔｕｒｎ  Ｓ
ステップＳ←ａｉＢ＋（ｍｉＮ＋Ｓ）／ｒは、計算時間の視点からは最も高価である。このステップは同じ演算：数字×長い整数＋長い整数→長い整数（ｘｉＹ＋Ｚ→Ｚ）
［ｄｉｇｉｔ×ｌｏｎｇ  ｉｎｔｅｇｅｒ＋ｌｏｎｇ  ｉｎｔｅｇｅｒ→ｌｏｎｇ  ｉｎｔｅｇｅｒ（ｘｉＹ＋Ｚ→Ｚ）］
を２回行なうことによって得られることが注目され得る。このステップは、二つの長い整数（Ｙ及びＺ）の数字に対してループ計算を行なうことにより実行される。しかしながら、シフトが実施されるか否かによって二つの場合が区別される。
【００１８】
伝統的な乗算：ａｉＢ＋Ｔ→Ｓ（１）
この乗算−加算は次のループにより実行される。
ｃ＝０
Ｆｏｒ  ｊ＝０〜ｎ  ｄｏ、
Ｐ←ａｉｂｊ＋ｔｊ＋ｃ
ｓｊ←ＬＳＢ（Ｐ）
ｃ←ＭＳＢ（Ｐ）
Ｓｎ＋１＝ｃ
ｊ＝ｎの反復に対し、ｂｊ≦１、それゆえＰ≦３（ｒ−１）＝２ｒ＋ｒ−３であり、それはＭＳＢ（Ｐ）≦２を意味する。従ってここからＳｎ＋１≦２となる。
【００１９】
所見：
基本演算はｘ×ｙ＋ｚ＋ｃで、ここでｘ、ｙ、ｚ及びｃは０〜ｒ−１の間にある。その結果は従って二つの数字で表わされる、０とｒ２−１の間にある。
【００２０】
乗算及びシフト：（ｍｉＮ＋Ｓ／ｒ）→Ｔ（２）
ｒによる除算の特定の場合（右方シフト）、出力Ｔレベルにおけるインデックスのシフトを伴って、該ループは上記と同じである。
【００２１】
具体的には、ｍｉの決定はｒで除算できる数量Ｐ＝ｍｉ×Ｎ０＋ｓ０を与える。その場合、ＬＳＢ（Ｐ）は確実に０である。それゆえ、この最初の値（インデックス−１）は意図的に「切り捨てられ」、第一の有効値（ｔ０）が次の反復（ｊ＝１）において得られる。
【００２２】
インデックスのシフトのため、最後の反復（ｊ＝ｎ）はｔｎ−１の値への接近を許す。ｔｎの値はそれゆえｓｎ＋１と共に反復ｊ＝ｎのｃ＝ＭＳＢ（Ｐ）を加えることによって得られる。ループはそれゆえ次のようになる。
ｃ＝０
Ｆｏｒ  ｊ＝０〜ｎ  ｄｏ
Ｐ←ｍｉＮｊ＋ｓｊ＋ｃ
ｔｊ−１←ＬＳＢ（Ｐ）
ｃ←ＭＳＢ（Ｐ）
ｔｎ＝ｃ＋ｓｎ＋１
ｊ＝ｎ，Ｎｊ＝０の反復に対し、それゆえＰ≦２（ｒ−１）＝ｒ＋ｒ−２であり、それはＭＳＢ（Ｐ）≦１を意味する。従ってここからｔｎ≦３となる。ｒ≧４であるため、ここからＴが実際にｎ＋１の数字により表わされることとなる。
【発明の開示】
【課題を解決するための手段】
【００２３】
本発明は特に、通常の演算の間、従来技術において考えられるセルよりも大きなサイズの独自のセルと、高いベースを有するモンゴメリー・アルゴリズムを用いる自己反復プロセスとを考慮した、新たなアプローチに頼る。すなわち、これ以後、ベースｒは４以上（４よりも大きいか等しい）と想定される。実際にベースｒは通常２３２又は２６４に相当し、それによって高いベースという用語を正当化する。
【００２４】
本発明は、一緒に加算され乗算されるべき幾つかの数字を受け取る、ｐ組のパイプライン処理された論理レジスタの対を含む乗算器−加算器を備えた少なくとも一つの計算セルと、低次及び高次に対応する少なくとも二つの出力とを備え、加算器が乗算器−加算器の二つの出力を受け、乗算器−加算器の最大周波数が加算器の最大周波数以上になるように数ｐが選択されることを特徴とする、モジュラー乗算を実行するための装置に関する。
【００２５】
該装置はその入力が加算器のＬＳＢ出力及び予め計算された定数に対応する、下方部分の乗算器を備えることができ、前記乗算器は深さｋにわたってパイプライン処理される。
【００２６】
本発明はとりわけ次の利点を示す。より高いベースの使用はモジュラー乗算の計算に必要なサイクル数を減少させる。そこで単一の基本セルが用いられる。このアーキテクチャの時間と面積の積はそれゆえ改善される。
【００２７】
本発明の別の特徴及び利点は、以下に続く、図面と共に全く限定されない説明により与えられる例示的実施形態の説明を読むことによって更に明らかになるであろう。
【発明を実施するための最良の形態】
【００２８】
本発明による乗算器において実行される着想は、とりわけ乗算−加算演算（ｘ×ｙ＋ｚ）をパイプライン処理することにより、そして結果が得られるにつれて、ｘ、ｙ、及びｚがデータで、ｃが前の反復から生じる高次の数字である、変数ｃを加えることにより、演算ｘ×ｙ＋ｚ＋ｃを（ｘ×ｙ＋ｚ）＋ｃに分割することにある。
【００２９】
パイプライン
パイプラインはクリティカルパスを減らし、従って最大動作周波数（理論的にはベースｒを有する加算器の動作周波数）を増すように、論理位相間にレジスタのバリヤを加えることにある。
【００３０】
基本構成要素のパイプライン深さはその内部レジスタの数により定義される。出力レジスタはカウントされない。
【００３１】
乗算−加算の実行
図１に与えられる例は、深さｐのパイプライン処理された乗算器−加算器１が利用できることを想定している。
【００３２】
それは特に論理−レジスタの対（ｌｉ，ｒｉ）の組を含む。これらの対の数ｐはとりわけ、パイプライン処理された乗算器−加算器の最大周波数Ｆ１ｍａｘが加算器の最大周波数Ｆ２ｍａｘ以上であり、これら二つの周波数の値が出来る限り近くなるように選択される。
【００３３】
乗算器−加算器の最大動作周波数は、乗算−加算演算を実行するための時間の逆数で与えられ、一方でパイプライン処理された乗算器−加算器の最大動作周波数はｐ層の中の一つを実行するための時間の逆数で与えられる。最適演算に対して加算器の最大周波数が決定され、それにより加算器の実行時間を与え、該乗算器−加算器はその横断時間が加算器の実行時間以下であって、しかしそれに出来る限り近いｐ層へと分割される。
【００３４】
乗算器−加算器１の入力は三つの数字ｘ、ｙ、及びｚに対応し、出力はＬＳＢ（ｘ×ｙ＋ｚ）及びＭＳＢ（ｘ×ｙ＋ｚ）に対応する数字の対である。出力は二つの数字を保持している。
【００３５】
乗算器−加算器の結果は参照番号２の三入力加算器に伝送される。「数字＋数字＋けた上げ→数字＋けた上げ」（ｄｉｇｉｔ＋ｄｉｇｉｔ＋ｃａｒｒｙ→ｄｉｇｉｔ＋ｃａｒｒｙ）が周波数Ｆ２ｍａｘにおいて１サイクル（パイプライン０）内で動作する。これ以後、ｂは内部バスのサイズを意味するであろう（なされる想定は、ｒ≧４を満足するようにｂ≧２である）（ｒ＝２ｂ）。
【００３６】
レジスタＴｅｍｐは次の計算：ｃと次のＬＳＢとの加算及び前のけた上げに必要なｃのストレージに対応する。
【００３７】
データ（ｘ×ｙ＋ｚの数字）は、従ってけた上げの伝搬と同じ方向に、各サイクルにおいて順番に、低次の数字を先頭にして出る。
【００３８】
図２は乗算の下方部分用に適切な装置３、及びレジスタとマルチプレクサからなる装置５を有する、図１の構成要素の例示的配置を説明している。
【００３９】
この例において、回路の主要構成要素は、パイプライン処理された乗算器−加算器１、参照番号２の三入力加算器、下方部分の乗算器３、参照番号４で示される２ビット＋１ビット〜２ビットの加算器、及び参照番号５で示されるｎｒｅｇ−ｍａｘ−１レジスタとマルチプレクサのバリヤである。
【００４０】
マルチプレクサ及びレジスタの数は、とりわけ回路に固有のデータである、パイプラインの深さｐとｋ、及び同様にデータ数字の数に依存する。
【００４１】
図２の例において、ｎｒｅｇ−ｍａｘ−１レジスタとマルチプレクサのバリヤ（参照番号５で示される構成要素）の機能は、特に乗算器−加算器１におけるデータの到着を遅らせることである。
【００４２】
下方部分の乗算−構成要素３
アルゴリズムの主要ループ内で、各反復ｍｉにおいて、数量Ｓ＋ｍｉＮをｒで割り切れるようにする数字が決定される。ｍｉは所定の係数Ｎに対して、一回限りで予め計算された定数Ｎ’とＳの低次数との部分的な乗算を実行することにより決定される。この乗算において、下方部分のみが興味を引く。この演算はｒを法として実行される。この演算は加算よりも遅く、それはまたパイプライン処理される。この演算子のパイプラインの深さはｋと呼ばれ、ｋ＜ｐであることが想定される。
【００４３】
ループバック、待ち時間、及び追加レジスタ
伝統的な乗算ａｉＢ＋Ｔ→Ｓ，（１）から乗算及びシフト（ｍｉ×Ｎ＋Ｓ）／ｒ→Ｔ，（２）への切替え、及び（２）から（１）への切替えの二つの場合が区別され、遅れは同じではない。
【００４４】
この遅れは、とりわけ使用されるべきレジスタの数：場合によりｎ’ｒｅｇ又はｎｒｅｇｋ；を決定する。従って例えば、（２）から（１）への切替えにおいて、及びｐ＋２≦ｎの場合（ここでｎ’ｒｅｇが定義されている場合）、使用されるべきレジスタの数はｎ’ｒｅｇである。それらのｎｒｅｇ−ｍａｘ−１があるのと同じように、それらのｎｒｅｇ−ｍａｘ−１−ｎ’ｒｅｇをスキップすることが必要である。これは相応に設置されるマルチプレクサによってなされる。
【００４５】
（１）から（２）への切替え
乗算−加算（１）と（２）を時間のロスなしに（すなわち待ち時間を加えることなく）つなぐことが出来るように、実行中の乗算の全ての数字を走査してしまう前にｍｉを決定することが適切である。
【００４６】
従って条件：ｐ＋ｋ＋２≦ｎを達成することが望ましい。
【００４７】
具体的には、乗算−加算の結果の低次の数字は、インデックスｐ＋１の数字が乗算器−加算器の入力に到達したときに利用可能である。
【００４８】
次のサイクルにおいて、加算が実行される。Ｓ０が利用可能であり、従ってｍｉの計算を開始することができる。ｋ＋１の追加クロック動作の後、ｍｉは下方部分の乗算器からの出力として利用できる。それは従って次のクロック動作において乗算器−加算器用の入力用として使用可能である。これは条件ｐ＋ｋ＋２≦ｎを説明する。
【００４９】
ループバック
乗算−加算（１）と（２）を時間のロス無しにつなぐことが望まれる場合、ｐ＋ｋ＋２≦ｎが選択される。
【００５０】
この場合、データｍｉは実行中の乗算−加算の数字の行程の終了前に利用できる。この値は、従って乗算器−加算器への入力を遅らせるようにループバックされる。この値の必要なループバックの数に相当するｎｒｅｂｋ＝ｎ−ｐ−ｋ−２がそのとき定義される。
【００５１】
ｎｒｅｂｋ＝０である特定の場合、データｍｉは乗算器−加算器の新たな入力と同期している。
【００５２】
しかしながら、全ての場合において、ｍｉの値は入力がＮの全ての数字に対して同じになるようにｎ回ループバックされる。
【００５３】
他方でｎ−ｐ−ｋ−２が負の場合、これはｍｉの計算の遅れに相当し、それゆえ待ち時間が加えられる。
【００５４】
待ち時間
条件ｐ＋ｋ＋２≦ｎが達成されないとき、これは出力が入力に対して幾らかの遅れを有することを表わし、データを同期させるための待機動作（待ち時間）が加えられる。
【００５５】
待機動作の間、入力は（Ｓの最後のけた上げを考慮するため、新たな入力として０が採られるという意味で）凍結され、計算は既に入力されたデータに関して続けられる。
【００５６】
この場合（ｐ＋ｋ＋２＞ｎ）、ｎｌａｔｋ＝ｐ＋ｋ＋２−ｎが定義される。この大きさは乗算器−加算器へ新たな入力を与える前に実行されるべき待ち時間動作の回数を表わす。
【００５７】
ｍｉが決定されると直ちに、それは乗算−加算用の入力として用いられる。Ｓ０に関しては、必然的にｍｉの前に決定され、（Ｓ１，Ｓ２・・・と同様に）ｍｉが計算されるまで記憶されなければならない。
【００５８】
このため、乗算器−加算器の入力において結果の到着を遅らせるようにレジスタが加えられる。
【００５９】
追加のレジスタ
二つの場合が区別される。具体的には、ｐ＋ｋ＋２がｎよりも大きいか小さいかによって、付加されたレジスタの数及び用途は、しかしながら同じではない。
【００６０】
ケース１：ｐ＋ｋ＋２≦ｎ
この場合、Ｓ０とｍｉの組はデータの数字の行程が終わる前に決定される。
【００６１】
ｍｉに関しては、ループバックに対する区間を見ると、ループバック区間において上述の方法が用いられている。
【００６２】
Ｓ０に関しては、乗算器−加算器の入力におけるその到着はシフトレジスタを加えることにより遅くされる。
【００６３】
次にｎｒｅｇはｎｒｅｇ＝ｎ−ｐ−１により定義される。この数量は、乗算−加算結果の低次の数字の到着を次のものの低次データと同期させるために加えられるべきレジスタの数に相当する。
【００６４】
ケース２：ｐ＋ｋ＋２＞ｎ
ｐがｎよりも大きいか、もはやｎよりも大きくないかによって二つのサブ・ケースが区別される。事実、ｐの値がどうであれ、ｍｉはＳ０の後に決定されるであろう。
【００６５】
乗算器の入力におけるＳ０の到着は従ってレジスタの付加により遅くされる。このレジスタの数は、従って下方部分の乗算演算子のパイプラインの深さであるｋのみに依存するであろう。
【００６６】
従ってこの場合、乗算器の入力においてＳ０の到着を遅らせるために加えられるレジスタの数である、ｎｒｅｇｋ＝ｋ＋１が定義される。
【００６７】
（２）から（１）への切替え
本発明者らはここで（２）から（１）への切替えを取り扱う。決定されるべきｍｉがない場合、他方でシフト（ｒによる除算）を考慮する必要がある。
【００６８】
上述したように、結果の到着は新たなデータの入力と同期される。ここで、数量ｐのみが重要であり、ｍｉは決定される必要がなく、ｋは関係しない。
【００６９】
他方で、シフトが考慮される（すなわち、ｔ０を低次の数字として考慮し、ゼロであるｔ１を考慮しない）。これは追加のパイプライン・レベルとして見ることができる。
【００７０】
追加のレジスタ及び待ち時間
それゆえ、上述したように、ｐ＋２がｎより大きいか否かによって二つの場合が区別される。
【００７１】
ケース１：ｐ＋２≦ｎ
この場合、ｔ０はデータの数字の行程が終わる前に利用できる。従ってレジスタが遅れを考慮に入れるために加えられる。次に、遅れを考慮するために加えられるべきレジスタの数を示す、ｎ’ｒｅｇ＝ｎ−ｐ−２が定義される。
【００７２】
ケース２：ｐ＋２＞ｎ
この場合、ｔ０はデータの数字の行程の後に利用できる。新たなデータの入力は従って遅くされる。これは、上述したように、待機動作（待ち時間）を加えることによってなされる。作り出されるべき待機動作の数を表わすｎ’ｌａｔ＝ｐ＋２−ｎが定義される。
【００７３】
追加の加算器及びループバック
ｔｎの決定は、ｓｎ＋１≦２、及びｃ≦１であるｓｎ＋１とｃとを加算することによってなされる。このために２ビット＋１ビット〜２ビットの（論理）加算器（ｔｎ≦３）（参照番号４の構成要素）が想定される。
【００７４】
Ｔの計算において、シフトはレジスタの使用を節約することを可能にする。後者はｓｎ＋１の記憶用に使用される。この値はｃが決定されるまで記憶され、次にその二つは加算され、従ってｓｎ＋１記憶用のレジスタを解放する。それゆえ、ｓｎ＋１の必要なループバックの数であるｎｒｅｂ＝ｎ＋ｎｌａｔｋ−１が定義される。
【００７５】
修正パラメータ
構成要素の最終設計は、最初に想定される、長い整数の数字ｎの数と同様に、とりわけパイプライン深さｐ及びｋに依存する。特に、加えられるべきレジスタの数は、その場合が（１）から（２）への切替えか、あるいは（２）から（１）への切替えかによって同じではないため、難しい点である。
【００７６】
次の総括表１は前に定義された修正パラメータに対するｐ、ｋ、及びｎの数量に関する。
【００７７】
【表１】
2008535011.tif 000003
【００７８】
実際に、加えられるべきレジスタの数は、ｎｒｅｇ−ｍａｘ＝ｍａｘ（ｎｒｅｇｋ，ｎｒｅｇ）により定義され、ｐ＋ｋ＋２≦ｎの場合はｎ−ｐ−１に等しく、そうでなければｋ＋１に等しい。特に、ｎｒｅｇ−ｍａｘは１以上である。より少ないレジスタを必要とするステップは、マルチプレクサを加えることにより、レジスタの連鎖を短縮することによって実行される。
【００７９】
図２に説明されるシーケンス
演算の一つの例示的シーケンスが図２に関連して説明されている。取り決めとして、次のクロック動作を制御するために実行中のクロック動作の終わりにおけるマルチプレクサの状態を固定することが採用される。
【００８０】
マルチプレクサの一般的挙動
ここでは待ち時間が関係する。具体的に、待ち時間の有無によっては状態の複数の変化が同時に生じない。
【００８１】
しかしながら、マルチプレクサの一般的挙動を定義するために回路（ｎ’ｌａｔ及びｎｌａｔｋ）の待ち時間修正パラメータを用いることは可能である。
【００８２】
具体的に、ゼロであるＢの初期数字ｎ’ｌａｔと共に
｜Ｂ｜＝ｎ＋１＋ｎ’ｌａｔ
が想定され得る。（明らかにａ０Ｂの計算を除く。）
【００８３】
同様に、ゼロであるＮの初期数字ｎｌａｔｋと共に
｜Ｎ｜＝ｎ＋１＋ｎｌａｔｋ
を想定することができる。
【００８４】
更に、待ち時間が考慮されない（Ｂの初期数字ｎ’ｌａｔがゼロ）最初の計算ａ０Ｂの特定の場合が分離される。
【００８５】
最後に、この特定の場合を過ぎて、乗算器−加算器への入力として連続的に与えられたデータは、２ｎ＋２＋ｎ’ｌａｔ＋ｎｌａｔｋのデータの部分に再編成され得ることが注目される。最初のｎｌａｔｋ＋ｎ＋１はデータｍｉ及びＮｊに対応する。最後のｎ’ｌａｔ＋ｎ＋１はデータａｉ及びｂｊに対応する。マルチプレクサの挙動は従って期間２ｎ＋２＋ｎ’ｌａｔ＋ｎｌａｔｋの周期的挙動であろう。
【００８６】
ｍｕｘ１
ｍｕｘ１は乗算器−加算器のレベルにおいて、どちらのタイプの入力が考慮されなければならないかを象徴的に示す、二つの状態を有するマルチプレクサである。該二つの状態は、下記である。
０：ｘ＝ａｉ及びｙ＝ｂｊが乗算器−加算器の入力として採られる。
１：ｘ＝ｍｉ及びｙ＝Ｎｊが乗算器−加算器の入力として採られる。
【００８７】
定数ｎ’ｌａｔ及びｎｌａｔｋの使用は、特にＢ（又はＮ）の全ての数字が走査された時に、状態変化が起きることの確認を可能にする。
【００８８】
ａ０に対して、ｎ’ｌａｔの初期数字ゼロは考慮されない。該計算はデータａ０ｂｎ’ｌａｔにより直接的に始まる。
【００８９】
従って初期にゼロの（リセットされた）ｍｕｘ１は、最初のｎ回のクロック動作の間はこの状態に留まり、そしてｎ＋１回目の動作において状態１に切り替わる。
【００９０】
このｎ＋１回目の動作の終わりに、乗算器−加算器への入力として与えられるデータはａ０及びｂｎであり、Ｂの全ての数字はそれゆえ走査されているであろう。ｍｕｘ１はこの同じクロック動作の終わりにおいて１であり、従って次のクロック動作の終わりに、ｍ１及びＮ０が乗算器−加算器への入力として与えられるであろう。
【００９１】
クロック動作時計の関数としてのｍｕｘ１の一般的挙動は、次のステップで要約されることができる。
Ｉｆ  ｃｌｏｃｋ＜ｎ＋１  ｔｈｅｎ
ｍｕｘ１＝０
Ｏｔｈｅｒｗｉｓｅ：
Ｉｆ  （ｃｌｏｃｋ−（ｎ＋１）  ｍｏｄ  （２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ））＜ｎ＋１＋ｎｌａｔｋ  ｔｈｅｎ
ｍｕｘ１＝１
Ｏｔｈｅｒｗｉｓｅ
ｍｕｘ１＝０
【００９２】
ｍｕｘ２
ｍｕｘ２は加算ｓｎ＋２＋ｃが実行されなければならない時期を象徴的に示す、二つの状態を有するマルチプレクサである。ｓｎ＋２はＳｔａｂ１に記憶されていることを想起されたい。
【００９３】
更に、この加算が実行されたとき、新たな加算が始まっているため、三入力加算器のけた上げは０に初期化されなければならない。該二つの状態は、下記である。
０：加算ｓｎ＋１＋ｃが実行出来ず、ｃはまだ決定されていない。
１：入力ｓｎ＋１及びｃが次のクロック動作において加算されるように位置付けられ、三入力加算器のけた上げは０に初期化されている。
この加算は主要な反復（ｉに対するループ）当たり１回実行され、それはＮの数字に対する第二ループ内に位置する。
これはｍｕｘ２が決して連続して２回は状態１にないことを表わす。更に、この加算はレジスタＳｔａｂ１の値に関係し、それゆえパイプライン深さｐはｍｕｘ２の挙動を決定するために介入する。
【００９４】
積ａ０×ｂ０の低次の数字（ｓ０）は、クロックｐ＋３において加算器の出力レジスタ内にある（＝１（ｌｏａｄ）＋（ｐ＋１）（ＬＳＢ内のｓ０）＋１（加算器の出力レジスタ内のｓ０））。従ってｓｎはクロックｐ＋３＋ｎにおいてこの同じレジスタ内にある。ｓｎはａ０×ｂｎの低次の数字に相当するため、次の入力はそれゆえＮ及びｍ１の数字である。ところで、ｔｎ−１が加算器の出力レジスタ内に位置するときに、ｔｎを決定するためｓｎ＋１に加えられるべきけた上げの正しい値が利用できるため、加算が実行されなければならない。ｍｕｘ２は従ってｔｎ−１が加算器の出力レジスタ内に位置するとき、すなわちクロック動作ｐ＋３＋ｎ＋ｎｌａｔｋ＋ｎ＋１＝ｐ＋２ｎ＋ｎｌａｔｋ＋４において、１の状態になければならない。シフトと共にｔｎ−１がｍ１×Ｎｎの計算に対応することを忘れるべきではない。周期性によって、ｍｕｘ２の一般的挙動を説明することが可能である。
Ｉｆ  ｃｌｏｃｋ＝ｐ＋２ｎ＋４＋ｎｌａｔｋ  ｍｏｄ  ２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ  ｔｈｅｎ
ｍｕｘ２＝１
Ｏｔｈｅｒｗｉｓｅ
ｍｕｘ２＝０
【００９５】
ｍｕｘ３
Ｎの数字に対するループの間、ｒによる除算を考慮するため、正しいシフトが出力の数字に対して実行されなければならない。ｍｕｘ３は（レジスタの飛び越しによりモデル化される）シフトが実行される時期を象徴的に示す、二つの状態を有するマルチプレクサである。該二つの状態は、下記である。
０：シフトは実行されない。
１：シフトは実行される。
インデックスのこのシフトは、レジスタをスキップすることによりハードウェアで実行される。
【００９６】
該シフトはデータｓｎ＋１がレジスタＳｔａｂｌ内にあるときに起きる。具体的にはこの瞬間に、加算器のレジスタＳはｎｌａｔｋの値によって、０（待ち時間動作の結果）又はｔ０の値を含む。ｔ０は伝統的な乗算に対して遅れ時間（ｓ０）を有し、それは次にこの遅れ時間を取り戻すようにレジスタをスキップしなければならない。従ってこのシフトは、ｔｎ−１に至る迄のＴの全ての数字（待ち時間を含む）が決定されるまで実行されなければならない。具体的には、ｔｎ−１が決定されたとき（すなわち、加算器のレジスタＳ内）、次のクロック動作において、ｔｎはｃとｓｎ＋１との加算によりＳｔａｂ１内で決定され、そしてｔｎ−１はレジスタＳｔａｂ２内に位置する。次に該シフトは終了し、データｔｎ−１及びｔｎは再び二つの連続するレジスタ内にあり、ｍｕｘ３はそれゆえｎ＋ｎｌａｔｋ＝ｎｒｅｂ＋１回の動作の間中、状態１に留まる。
【００９７】
本発明者らが上述したように、シフトはレジスタＳｔａｂｌの飛び越しに相当し、それは次にｓｎ＋１へのループバック用に用いられる。ｓｎ＋１へのループバックは従って該シフトと同時に起きる。それゆえ０から１へのｍｕｘ３の状態変化は又、ｓｎ＋１の値をレジスタＳｔａｂｌ内へとループバックする必要があることを示す。このループバックはｎｒｅｂ回生じる。
【００９８】
初期にはｍｕｘ３は状態０（伝統的乗算）にある。それはｓｎ＋１がレジスタＳｔａｂｌ内にあるとき１に切り替わる。ところで、ｓｎはクロック動作ｐ＋３＋ｎにおいてＳの中にある（ｍｕｘ２の挙動を参照）。従ってｓｎ＋１は動作ｐ＋ｎ＋４においてこの同じレジスタ内にあり、次の動作ｐ＋ｎ＋５においてＳｔａｂｌ内にある。ｍｕｘ３の一般的挙動は周期性により推定される。
Ｉｆ  ｃｌｏｃｋ＜ｐ＋ｎ＋５  ｔｈｅｎ
ｍｕｘ３＝０
Ｏｔｈｅｒｗｉｓｅ：
Ｉｆ  （ｃｌｏｃｋ−（ｐ＋ｎ＋５））  ｍｏｄ  （２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ））＜ｎｒｅｂ＋１  ｔｈｅｎ
ｍｕｘ３＝０
Ｏｔｈｅｒｗｉｓｅ
ｍｕｘ３＝０
前の所見はコマンドｒｅｂを定義し説明することを可能にする。
【００９９】
コマンドｒｅｂ
このコマンドは、それに対してｓｎ＋１がレジスタＳｔａｂｌ内へループバックされなければならない瞬間を表わす。該二つの状態は、下記である。
０：ループバックなし
１：ループバック
【０１００】
ｒｅｂの挙動はｍｕｘ３の挙動と同時に説明される。本発明者らは従ってここから次を推定する。
Ｉｆ  ｃｌｏｃｋ＜ｐ＋ｎ＋５  ｔｈｅｎ
ｒｅｂ＝０
Ｏｔｈｅｒｗｉｓｅ：
Ｉｆ  （ｃｌｏｃｋ−（ｐ＋ｎ＋５）  ｍｏｄ  （２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔｋ））＜ｎｒｅｂ  ｔｈｅｎ
ｒｅｂ＝１
Ｏｔｈｅｒｗｉｓｅ
ｒｅｂ＝０
【０１０１】
ｍｕｘ４
ｍｕｘ４はレジスタのバリヤの部分を形成する二つの状態を有するマルチプレクサである。このマルチプレクサが存在している場合、それはｎ’ｒｅｇレジスタ又はｎｒｅｇｋレジスタを使用する必要があるかどうかを示す。該二つの状態は下記である。
０：全レジスタの使用（乗算（２）に対応する。）
１：ｎ’ｒｅｇレジスタの使用（乗算（１）に対応する。）
【０１０２】
ｍｕｘ４はｔ０がＳの中で決定されるとき、状態１でなければならない。ｓｎ＋１は、ｃｌｏｃｋ＝ｐ＋ｎ＋４においてＳの中に存在することが見られた（ｍｕｘ３参照）。従ってｎｌａｔｋ＋１回のクロック動作後、すなわちｃｌｏｃｋ＝ｐ＋ｎ＋５＋ｎｌａｔｋにおいて、ｔ０はＳの中にある。ｍｕｘ４はｔｎがＳｔａｂｌ内に位置するまで、すなわちｎ＋１回のクロック動作の間中、１のままでなければならない。
【０１０３】
ｍｕｘ４の一般的挙動は周期性により推定される。
Ｉｆ  ｃｌｏｃｋ＜ｐ＋ｎ＋５＋ｎｌａｔｋ  ｔｈｅｎ
ｍｕｘ４＝０
Ｏｔｈｅｒｗｉｓｅ：
Ｉｆ  （ｃｌｏｃｋ−（ｐ＋ｎ＋５＋ｎｌａｔｋ）  ｍｏｄ  （２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ））＜ｎ＋１  ｔｈｅｎ
ｍｕｘ４＝１
Ｏｔｈｅｒｗｉｓｅ
ｍｕｘ４＝０
【０１０４】
コマンドｒｅｂｋ
コマンドｒｅｂｋは、ｍｉの値を下方部分の乗算器の出力レジスタ内へとループバックする必要がある時期を示す。該二つの状態は、下記である。
０：ループバックなし
１：ループバック
初期は、ｒｅｂｋ＝０である。
ｍ１（すなわち、下方部分の乗算器の出力レジスタ内に存在する）はクロック動作ｃｌｏｃｋ＝ｐ＋ｋ＋４の終わりに決定される。具体的には、ｍ１はそれ自体がクロック動作ｃｌｏｃｋ＝ｐ＋３（ｍｕｘ２参照）の終わりに、レジスタＳ内に存在する、ｓ０の助けを得て決定される。従ってそれはｋ＋１回のクロック動作の後に、すなわちｃｌｏｃｋ＝ｐ＋ｋ＋４において結果を与える、下方部分の乗算器への入力として役立つ。
【０１０５】
この入力がＮの全ての数字に対して同じであるように、従ってこの値をその時期から前方へ、少なくともｎ＋１回はループバックする必要がある。また、ｍ１がＢの全ての数字の走査前に決定される場合に、ｍ１の必要なループバック回数であるｎｒｅｂｋの値を考慮に入れることも必要である。ｍ１に対する全ループバック回数は、それゆえｎ＋１＋ｎｒｅｂｋである。ｒｅｂｋの一般的挙動は周期性により推定される。
Ｉｆ  ｃｌｏｃｋ＜ｐ＋ｎ＋４  ｔｈｅｎ
ｒｅｂｋ＝０
Ｏｔｈｅｒｗｉｓｅ：
Ｉｆ  （ｃｌｏｃｋ−（ｐ＋ｎ＋４））  ｍｏｄ  （２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ））＜ｎ＋１＋ｎｒｅｂｋ  ｔｈｅｎ
ｒｅｂｋ＝１
Ｏｔｈｅｒｗｉｓｅ
ｒｅｂｋ＝０
【図面の簡単な説明】
【０１０６】
【図１】本発明による乗算器−加算器セルの基本構成要素の例示的配置である。
【図２】モンゴメリー・モジュラー乗算器の核心部を構成する要素の例示的配置である。
【図１】
2008535011.tif 000004
【図２】
2008535011.tif 000005
【手続補正書】
【提出日】平成19年2月1日(2007.2.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
４以上のベースｒを有するモンゴメリーのモジュラー乗算を実行するための装置であって、
一緒に加算され乗算されるべき幾つかの数字を受け取る、ｐ組のパイプライン処理された論理レジスタの対を含む乗算器−加算器（１）を備えた少なくとも一つの計算セルと、低次及び高次に対応する少なくとも二つの出力とを備え、加算器（２）が乗算器−加算器の二つの出力を受け、乗算器−加算器の最大周波数Ｆ１ｍａｘが加算器の最大周波数Ｆ２ｍａｘ以上になるように数ｐが選択されることを特徴とする装置。
【請求項２】
前記乗算器−加算器の最大周波数Ｆ１ｍａｘが、実質的に加算器の最大周波数Ｆ２ｍａｘに等しいことを特徴とする請求項１に記載の装置。
【請求項３】
入力が前記加算器のＬＳＢ出力と予め計算された定数とに対応する下方部分の乗算器（３）を備え、前記乗算器が深さｋにわたってパイプライン処理されていることを特徴とする請求項１に記載の装置。
【請求項４】
前記乗算器−加算器におけるデータの到着を遅らせるまたは記憶するために適したレジスタ及びマルチプレクサの組を備えることを特徴とする、請求項１又は２に記載の装置。
【請求項５】
２ビット＋１ビット〜２ビットの補足的な加算器を備えることを特徴とする、請求項１又は２に記載の装置。
【国際調査報告】
2008535011.tif 000006
2008535011.tif 000007
2008535011.tif 000008
2008535011.tif 000009