(57)【要約】【課題】モントゴメリー・モジュラ乗算を実行する、改良された小型電子論理演算装置を提供する。【解決手段】ρ(A・B)Nのモントゴメリー・モジュラ乗算を実行するものであって、ここでρ(A・B)Nは A・B・I mod N にモジュラ演算上の合同であり、I・2n≡1 mod N であり、A、B及びNはnビット長オペランドであり、Nは奇数であり、該装置は、第一及び第二の主メモリ・レジスタであって、各レジスタはnビット長オペランドを保持し、それぞれ、乗数B、法Nを格納するように適合せしめられたものと、第一の値を第二の値によって、及び第三の値を第四の値によって、同時に乗算し、両方の結果を合計するデバイスであって、該デバイスへの入来ビットとしての予想Y0ビットを出力するための一つの桁上げ保存加算器を有するものと、該桁上げ保存加算器から出力される最下位kビットがゼロとなるようにY0を決定するY0センスユニットと、を具備する。【選択図】図１Ｂ
2009230153.tif 000002
【特許請求の範囲】
【請求項１】
ρ（Ａ・Ｂ）Ｎのモントゴメリー・モジュラ乗算を実行する小型電子論理演算装置（ＡＬＵ）であって、ここでρ（Ａ・Ｂ）Ｎは Ａ・Ｂ・Ｉ ｍｏｄ Ｎ にモジュラ演算上の合同であり、Ｉ・２n≡１ ｍｏｄ Ｎ であり、Ａ、Ｂ及びＮはｎビット長オペランドであり、Ｎは奇数であり、該装置は、
第一（７０，８０；１０００）及び第二（２００，２１０；１００５）の主メモリ・レジスタであって、各レジスタはｎビット長オペランドを保持し、それぞれ、乗数Ｂ、法Ｎを格納するように適合せしめられたものと、
第一の値を第二の値によって、及び第三の値を第四の値によって、同時に乗算し、両方の結果を合計するデバイス（３９０）であって、該デバイスへの入来ビットとしての予想Ｙ0ビットを出力するための一つの桁上げ保存加算器（４１０）を有するものと、
該桁上げ保存加算器から出力される最下位（ＬＳ）ｋビットがゼロとなるようにＹ0を決定するＹ0センスユニット（４３０）と、
を具備する小型電子論理演算装置。
【請求項２】
被乗数を収集し及び直列に合計するように動作し、該合計が該桁上げ保存加算器から直列に出る、請求項１に記載の小型電子論理演算装置。
【請求項３】
少なくともｋ個の下位ゼロを伴うように結果を強制するように動作する、請求項２に記載の小型電子論理演算装置。
【請求項４】
Ｙ0を出力するために、少なくともＡ0・Ｂd、ＣＯ0及びＳＯ1の排他的論理和をとるように動作する、請求項３に記載の小型電子論理演算装置。
【請求項５】
該Ｙ0センスを使用しないことによって、正規整数の乗算及び合計を実行するように動作する、請求項１に記載の小型電子論理演算装置。
【請求項６】
前もってモントゴメリー定数Ｊ0を計算せずに、モントゴメリー乗算を実行し、モジュラ・リダクションを実行するように動作する、請求項１に記載の小型電子論理演算装置。
【請求項７】
該Ａiオペランド値及び該Ｂオペランド値の両方をゼロにリセットし、部分結果値Ｓ0を１にセットすることによって、モントゴメリーＪ0定数を計算するように適合せしめられた、請求項１に記載の小型電子論理演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モジュラ乗算及び累乗と、直列整数除算のための装置と方法に関する。
【背景技術】
【０００２】
大きな数についてモジュラ乗算及び累乗を行うコンパクトな小型電子装置は、その開示を引用によって本明細書の記載に援用する、本出願人の米国特許第５，５１３，１３３号で説明されている。
【０００３】
その明細書で言及されているすべての出版物と本明細書に引用されている出版物の開示は、引用によって本明細書の記載に援用する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第５５１３１３３号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、モジュラ乗算及び累乗と直列整数除算のための改善された装置と方法を提供しようとする。
【課題を解決するための手段】
【０００６】
本発明の好適実施形態によれば、１つの桁上げ保存加算器を含む１つの乗算器と、好適には任意のビット長の被除数と任意のビット長の除数を受信し、商と剰余を計算するよう動作する直列除算装置とを含む直並列論理演算装置（ＡＬＵ）を含むモジュラ乗算及び累乗システムが提供される。
【０００７】
さらに本発明の好適実施形態によれば、本システムは任意のビット長の少なくとも１対の整数入力を乗算するよう動作する。
【０００８】
またさらに本発明の好適実施形態によれば、少なくとも１対の整数入力には２対の整数入力が含まれる。
【０００９】
さらに追加して本発明の好適実施形態によれば、ＡＬＵは前もってゼロ強制モントゴメリー定数Ｊ0を計算せずに、整数入力の積を生成し積の大きさを換算するよう動作する。
【００１０】
また、本発明の別の好適実施形態によれば、任意のビット長の被除数と任意のビット長の除数を受信し商と剰余を計算するよう動作する直列除算装置を含む直列除算装置が提供される。
【００１１】
さらに本発明の好適実施形態によれば、本装置は１対の整数入力を保存する１対のレジスタを含み、少なくとも１つがそれぞれのレジスタのビット長を越える１対の整数入力をインタリーブなしに乗算するよう動作する。
【００１２】
また、本発明のまた別の好適実施形態によれば、１つだけの桁上げ保存累算器を有し１対の乗算を行いその結果を合計するよう動作する直並列乗算装置を含むモジュラ乗算及び累乗システムが提供される。
【００１３】
さらに追加して、本発明のまた別の好適実施形態によれば、モジュラ乗算及び累乗方法が提供されるが、本方法には、１つの桁上げ保存加算器を有する１つのモジュラ乗算装置を含む直並列論理演算装置（ＡＬＵ）を提供するステップと、モジュラ乗算及び累乗を行うために直並列ＡＬＵを利用するステップとが含まれる。
【００１４】
さらに、本発明のまた別の好適実施形態によれば、大きな整数の自然（非モジュラ）乗算の方法が提供されるが、本方法には、１つの桁上げ保存加算器を有する１つのモジュラ乗算装置を含む直並列論理演算装置（ＡＬＵ）を提供するステップと、大きな整数の自然（非モジュラ）乗算を行うために直並列ＡＬＵを利用するステップとが含まれる。
【００１５】
さらに、本発明の好適実施形態によれば、利用ステップには、第１積を得るために任意のビット長の第１整数を任意のビット長の第２整数で乗算するステップと、第２積を得るために任意のビット長の第３整数を任意のビット長の第４整数で乗算するステップと、合計を得るために第１及び第２積を任意のビット長の第５整数と合計するステップとが含まれる。
【００１６】
またさらに、本発明の好適実施形態によれば、利用ステップには、任意のビット長の被乗数、乗数及び法によるモジュラ乗算及び累乗を行うステップが含まれる。
【００１７】
さらに追加して、本発明の好適実施形態によれば、本システムにはまた、１つの事前計算定数だけでモントゴメリー・モジュラ乗算を実行する二重被乗数事前計算システムが含まれる。
【００１８】
さらに、本発明のまた別の好適実施形態によれば、利用ステップには、モントゴメリー乗算を行うステップが含まれ、そこには、乗数と被乗数を含む整数入力の積を生成するステップと、前もってモントゴメリー定数Ｊ0を計算せずにモジュラ換算（リダクション）を実行するステップが含まれる。
【００１９】
さらに、本発明の好適実施形態によれば、モントゴメリー定数Ｊ0にはＮｍｏｄ２kが含まれるが、ここでＮはモジュラ換算の法であり、ｋは被乗数のビット長である。
【００２０】
またさらに、本発明の好適実施形態によれば、利用ステップには、一連のインタリーブド・モントゴメリー乗算演算を行うステップが含まれる。
【００２１】
さらに追加して、本発明の好適実施形態によれば、各インタリーブド・モントゴメリー乗算演算は、少なくともｋの有意ゼロを伴う結果を出すために法を乗算演算の合同に合計しなければならない回数を前もって計算せずに行われる。
【００２２】
またさらに、本発明の好適実施形態によれば、本システムにはまた、ｉ番目のインタリーブド・モントゴメリー乗算演算で生成される被乗数を収集及び直列合計し、それによって合計を生成し合計を（ｉ＋１）番目のモントゴメリー乗算演算に供給するよう動作するデータ・プロセッサが含まれる。
【００２３】
さらに追加して、本発明の好適実施形態によれば、関数にはＮｍｏｄ２kの乗法的逆元の加法的逆元が含まれる。
【００２４】
さらに、本発明の好適実施形態によれば、本方法はまた、Ａi及びＢをゼロにリセットしＳ0＝１を設定することでＪ0を計算するステップを含む。
【００２５】
本発明はまた、非常に大きな整数のモジュラ及び正規（整数の自然で負でない範囲）の乗算、除算、加算、減算及び累乗を行うコンパクトな小型電子論理演算装置ＡＬＵに関する。モントゴメリー法を使用するモジュラ乗算及び平方に言及する場合、装置の特定の部分はモジュラ演算コプロセッサと呼ばれ、ＭＡＰという頭字語が使用される。また、モントゴメリー乗算法はＭＭと呼ばれる。
【００２６】
本発明はまた、大きな整数の演算処理に関する。こうした大きな数は、（負でない）整数の自然範囲、または素数及び複合素数の法のガロア域ＧＦ（ｐ）にある。すなわち、本発明は、公開鍵暗号認証及び暗号化プロトコルにとって不可欠な演算を行うのに適した大きな数のモジュラ乗算／累乗を実現できる装置に関するが、こうした演算は次第に大きなオペランドに対して行われるようになっており、現世代のモジュラ演算コプロセッサでは効率的に実行できず、ソフトウェアによる実現では確実に実行できないものである。本発明は任意の４ビットまたはそれ以上のプロセッサで動作し、現在のデジタル信号プロセッサを越える速度を達成している。
【００２７】
本発明はまた、特に暗号化ソフトウェア指向システムで使用されることの多いインタリーブド・モントゴメリー・マルチプレシジョン・モジュラ乗算方法として知られる処理と、長いオペランドの整数に対する基本算術演算、すなわちＡ・Ｂ＋Ｃ・Ｄ＋Ｓ（ここでＡ、Ｂ、Ｃ、ＤまたはＳの大きさには理論的な制限はない）における固有の値との派生物の数値操作に関する大きなオペランドの整数演算のハードウェアによる実現に関する。さらに、本装置は特に、モジュラ乗算及び累乗を行うよう調整されている。基本装置は、モジュラ演算コプロセッサ（ＭＡＰ）に特に適しており、非常に大きな整数の除算を行う装置をも含むが、ここで除数は法レジスタＮと同じ長さのビット長を有し、被除数のビット長は２つの連結レジスタのビット長と同じ長さである。
【００２８】
この装置は好適には、同じ次数の論理ゲートによって、半分未満の機械クロックサイクルで、米国特許第５、５１３，１３３号のすべての機能を行う。これは主として、同じ桁上げ保存累算器機構（従来の直並列乗算器の主要構成要素）を使用する２つの半分の大きさの乗算器の代わりに、１つだけの二重動作直並列乗算器が存在するためである。新しい論理演算装置ＡＬＵ、すなわちモジュラ演算コプロセッサＭＡＰは好適には本質的に新しい処理の前の別個の乗算処理を不要にする。この処理はまた２次モントゴメリー定数Ｊ0を必要としたが、これも好適には不要になる。別言すれば、以前のモントゴメリー処置の２つの定数と、遭遇する遅延の代わりに、ここでは１つの定数だけが計算され、今では余分なＪ形乗算（後で説明する）によって発生する遅延は好適には除去される。
【００２９】
さらに、ＣＰＵとこの周辺装置の間のデータ操作の制御向上によって、装置の自然レジスタ・サイズより長いオペランド上で行われるオペランドは、好適には少ない一時記憶メモリを使用して短縮された処理時間で行われる。
【００３０】
モントゴメリーの方法論によってモジュラ乗算を行う３つの関連する方法が知られている。［Ｐ．Ｌ．Ｍｏｎｔｇｏｍｅｒｙ、「試行除算を行わないモジュラ乗算」、計算の数学、第４４巻、５１９〜５２１ページ、１９８５年］（以下「モントゴメリー」と呼ぶ）、［Ｓ．Ｒ．Ｄｕｓｓｅ及びＢ．Ｓ．Ｋａｌｉｓｋｉ Ｊｒ．「モトローラＤＳＰ ５６０００用暗号ライブラリ」、暗号化会議録’９０、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、ベルリン、１９９０年］（以下「Ｄｕｓｓｅ」と呼ぶ）及びＭｉｙａｇｕｃｈｉへの米国特許第４，５１４，５９２号の方法、及びＥｖｅｎへの米国特許第５，１０１，４３１号の方法、及びＩｗａｍｕｒａへの米国特許第５，３２１，７５２号の方法、及びＡｒａｚｉへの米国特許第５，４４８，６３９号の方法、及びＧｒｅｓｓｅｌへの米国特許第５，５１３，１３３号の方法。
【００３１】
好適なアーキテクチャは、ホスト・コンピュータのメモリにマップされた何らかの小型制御装置の設計に統合される機械のものであり、これはデータ供給機構との間で絶えずオペランドをスワップまたはやりとりする非常に長いコマンドについて、何らかの一般的な長さのモジュラ算術計算を可能にする制御装置と平行して動作するが、ここで操作のために必要なコプロセッサの揮発性メモリのサイズが最大オペランドの長さの３倍を越えることはまれである。
【００３２】
このソリューションは、前の実現例で本質的に２つの乗算装置の役目を果たす１つの乗算装置だけを使用する。現在の一般的な技術を使用して、４×４．５×０．２ｍｍの小型電子回路の上にメモリと共に小型制御装置を含むソリューション一式を集積することが可能である。
【００３３】
本発明はまた、以下詳細に説明されるような、モントゴメリー及びＤｕｓｓｅによって発表された処理に関する計算、論理及びアーキテクチャの新しい特徴を有する従来のデジタル・プロセッサの周辺装置であることを企図するデジタル装置のアーキテクチャに向けられる。
【００３４】
並列処理と独特のハードウェア・アーキテクチャが提供され、除算なしに、好適には従来の乗算／除算装置で行われるのと同じ数の演算でモジュラ累乗を行うが、その際従来の装置は各演算毎に乗算と除算の両方を行う。本発明の好適実施形態の特定の特徴は、基本的な大オペランド整数演算機能を考慮した、割込みのないリソースの効率的な使用による、無制限のオペランド長を考慮する装置によって行われる演算の同時性である。
【００３５】
本発明の好適実施形態によって実現される利点は直列処理の同期シーケンスに起因するが、これはｎビット・オペランドに対して同時に（平行して）３つの乗算演算を達成するためにマージされ、（ｎ＋ｋ）有効クロックサイクルで１つの多重化ｋビット直並列乗算器を使用し、モントゴメリーによって規定されたように３つの乗算計算と同等の結果を達成する。
【００３６】
次に使用されるオペランドの同期、実行中検出、実行中事前ロード及び同時追加によって、機械は決定論的に動作するが、その際すべての乗算及び累乗は所定の数のクロックサイクルで行われる。条件付き分岐はローカル検出及び補償装置によって置換され、それによって簡単な種類の制御機構の基礎を提供するが、これは、洗練された場合、通常一連の自励カスケード・カウンタを含む。ここで説明される基本演算は、スコットランドのＥａｓｔ ＫｉｌｂｒｉｄｅにあるＭｏｔｏｒｏｌａ（商品名ＳＣ−４９）と、フランスのＲｏｕｓｓｅｔにあるＳＧＳ−Ｔｈｏｍｓｏｎ（商品名ＳＴ１６−ＣＦ５４）の２社によって製造されるような、米国特許第５，５１３，１３３号で説明される装置を使用して決定論的時間で実行される。
【００３７】
この機械は、演算の合計長さについてオペランドが装置にロードされ保存される際、大部分の演算の場合揮発性メモリに対する要求は特にわずかである。しかし、この機械は好適には機械が追加された先のＣＰＵを活用し、簡単なロードとアンロード、機械へのコマンドの順序付けを実行する一方で、機械は大きな数の演算を行う。累乗処理時間は、事実上それを制御するＣＰＵと無関係である。実際には、機械を何らかのＣＰＵに追加する際アーキテクチャの変更は不必要である。ハードウェア装置は自己完結型であり、任意のＣＰＵバスに追加できる。
【００３８】
モジュラ乗算及び累乗処理を加速する装置が好適には提供されるが、これには必要な定数を事前計算する手段が含まれる。
【００３９】
ここで説明される本発明の好適実施形態は、携帯型スマートカードの公開鍵暗号適用業務のためのモジュラ数学的演算子を提供するが、このスマートカードは通常、一般的な磁器ストライプ・クレジット及び銀行カードと形状と寸法が同一である。同様のスマートカード（米国特許第５，５１３，１３３号）が、新世代公開鍵暗号装置で、コンピュータ、データベース及び重要な施設へのアクセスの管理、商業用、軍事用及び家庭用のトランザクションにおけるデータフローの調整と保護、スクランブルされた有料テレビ番組のスクランブル解除等のために使用されている。こうした装置はまた、コンピュータ及びファックス端末、ドアロック、自動販売機等にも組み込まれることが認識されるだろう。
【００４０】
説明されるハードウェアはρ演算子を新しい方法で適用することでモジュラ乗算及び累乗を実行する。さらに、それを互いに等しい被乗数と乗数に適用することで、同じ方法で平方が実行される。モジュラ累乗にはモジュラ乗算と平方の連続が含まれるので、上記の乗算、平方及び累乗法の反復される、適切に結合され方向付けされた応用を含む方法によって実行される。
【００４１】
ＡＬＵの好適実施形態の動作を説明する際、有効クロックサイクルでの同期が説明されるが、これは実際のクロックサイクルとは異なって装置が算術演算を行っているサイクルのことであり、実際のクロックサイクルには、新しい演算段階の準備のために、ＡＬＵが停止し、乗算器、フリップフロップ及び他の装置の設定が変更されるアイドル・サイクルが含まれている。
【００４２】
好適実施形態では、ＣＰＵの揮発性ＲＡＭまたはＳAレジスタ１３０の何れかに保存される被乗数Ａ、７０と８０の連結であるＢレジスタ１０００の乗数Ｂ、及び２００と２１０の連結であるＮレジスタ１００５の法Ｎが各ｋビットのｍ文字を含み、被乗数と乗数は一般に法より大きくない、（平方と正規乗算に関連する）モントゴメリー・モジュラ乗算を実行する方法は、
【００４３】
１）乗数Ｂと法Ｎをｎビット長のそれぞれのレジスタにロードするステップであって、ここでｎ＝ｍ・ｋであるステップと、
｛正規フィールドで正、自然、整数を乗算し、Ｎは第２乗数である｝
【００４４】
｛ｎがＢ、Ｎ及びＳレジスタより長い場合、値は通常反復の過程でこれらのレジスタにロード及びアンロードされ、機械が事実上あらゆる長さの法を操作できるようにする｝
【００４５】
２）レジスタＳBの出力をゼロに設定するステップであって、最初の反復についてＳ＊ｄフラッシュ（２５０）＝１であるステップと、
【００４６】
３）無縁借り及び桁上げフラグをリセットするステップ（特許で規定されていない制御）と、
４）ｍ回の反復を実行するステップであって、各反復が次の演算を含むステップと、を含む。
（０≦ｉ≦ｍ−１）
ａ）被乗数Ａの次の文字Ａi-1を揮発性記憶装置からＡｉロード・バッファ２９０に転送する。
ｂ）Ａｉロード・バッファのコンテントを回転する一方で、Ｎ0（ＮのＬＳ ｋビット）を伴うＣｉロード・バッファを同時直列ロードすることで、直列加算器ＦＡ１、３３０によってＮ0を伴うＡｊロード・バッファのコンテントを直列加算し、それによって合計Ｎ0＋Ａi-1を伴うＡｉ＋Ｃｉロード・バッファを直列ロードする。
【００４７】
事前ロード段階はここで終了する。この段階は通常、ＭＡＰが前の乗算反復を行っていた間に行われる。処理ａ）及びｂ）は同時に実行することができ、その際Ａi-1文字は対応するレジスタにロードされ、ＡｉストリームはＮ0レジスタの回転、Ｒ２、３２０のロードに同期する。同時に、ＡｉストリームとＮ0ストリームは合計され、Ｒ３レジスタ、３４０にロードされる。
【００４８】
Ｂレジスタからの量の平方が実行されるが、そこでは初期化、ステップａ）及びｂ）で、Ｂ0レジスタが回転される際に、Ｎ0レジスタと同時に、Ｂｄの最初のｋビットがＲ１に挿入される。次のｋビットＢi文字列が、ＡＬＵに直列供給される際にＲ１レジスタに事前ロードされる。
【００４９】
ｃ）機械が停止する。バッファＲ１、Ｒ２及びＲ３のオペランドはラッチＬ１、３６０、Ｌ２、３７０及びＬ３、３８０にラッチされる。
【００５０】
Ｌ０−“０”ラッチは疑似ラッチであり、これは単に、３９０、乗算器の入力または出力の各ＡＮＤゲートに入るリテラル・コマンド信号である。
【００５１】
ｄ）次のｋ回の有効クロックサイクルについて、
ｉ）各有効クロックサイクルについて、Ｙ０ ＳＥＮＳＥはＹ0の次のビットを予想し、このビットをＭ３乗算器を通じてＣｉロード・バッファにロードする一方で、ＡｉビットをＲ１レジスタからシフトアウトすると同時にＣｉロード・バッファにＹ0のｋビットをロードし、Ｒ１の出力にＹ0を加算し、この値をＲ３バッファにロードする。
【００５２】
ii）Ｍ Ｋ乗算器３９０によって４つのラッチＬ０、Ｌ１、Ｌ２またはＬ３の１つから望ましい値を論理的に選択することで、同時にＮ0（Ｌ２、Ｃｉラッチ）を入力Ｙ0ビットで乗算し、ＡｉをＢｄの次の入力ビットで乗算して、２つの結果を加算する。Ｙ0ビットとＢビットのどちらも１でない場合、すべてのゼロ値はＣＳＡに多重化され、Ｎ0ビットだけが１である場合、Ｎ0だけがＣＳＡに多重化／加算され、Ｂビットだけが１である場合、Ａi-1がＣＳＡに加算され、ＢビットとＮ0ビットの両方が１である場合、Ａi-1＋Ｎ0がＣＳＡに加算される。
【００５３】
iii）この合計は桁上げ保存ｋ＋１ビット累算器をビット毎に直列に出るので（Ｘストリーム）、直列加算器ＦＡ２、４６０を通じてＳｄの次の関連ビットをこの合計に加算する。
【００５４】
ＭＭでは、Ｚストリームの最初のｋビットはゼロである。
この第１段階で、Ｙ0・Ｎ0＋Ａi-1・Ｂ0＋Ｓ0の結果が計算され、ＬＳ ｋ全ゼロ・ビットがＺ*ｏｕｔストリームに現れ、乗算装置のＭＳ ｋ＋１ビットがＣＳＡ桁上げ保存累算器で保存される。Ｒ１、Ｒ２及びＲ３事前ロード・バッファはそれぞれ値Ａi-1、Ｙ0及びＹ0＋Ａi-1を保持する。
【００５５】
ｅ）最後の有効な（ｍ＋１）・ｋ番目のクロックサイクルで、機械は停止し、バッファＲ２及びＲ３はＬ２及びＬ３にラッチされる。
Ｌ１の値は変化しない。
【００５６】
次のｋ・（ｍ−１）有効クロックサイクルの初期および継続条件は次の通りである。
乗数は、Ｂのｋ番目のビットから開始されるＢのビット・ストリームであり、Ｎからの残りのビット・ストリームもＮのｋ番目のビットから開始される。
【００５７】
Ｌ１、Ｌ２及びＬ３の被乗数はＡi-1、Ｙ0及びＹ0＋Ａi-1であり、開始時にＣＳ加算器はｄ）で説明された値を含み、Ｓストリームは次のｋ・（ｍ−１）ビットをＦＡ２全加算器に供給する。
【００５８】
次のｋ・ｍ有効クロックサイクルの間に、ユニット４７０のＮｄ、遅延ｋクロックサイクルが直列減算器４８０で、Ｚストリームから減算され、ＢまたはＳレジスタに進むその結果がＮより大きいかまたはそれ以上かを検知する（Ｚ／２kｍｏｄ２k・m）。直列減算器４６０の検知結果に関わらず、｛（ｍ＋１）・ｋ｝番目の有効クロックサイクルでＣＳＡのＳＯ1フリップフロップが１ならば、合計結果は確実にＮより大きく、Ｎは結果から減算され、その結果、部分的または最終的に、そのレジスタを出る。
【００５９】
ｆ）次のｋ・（ｍ−１）有効クロックサイクルについて、
Ｎ０レジスタ２１０は、入力Ａｉビットと同期してか、または他の適切なタイミングで回転し、ａ）及びｂ）で説明されたように、次の反復のためにＲ１、Ｒ２及びＲ３をロードする。
【００６０】
このｋ・（ｍ−１）有効クロックサイクルで、Ｎの残りのＭＳビットがここでＹ0を乗算し、残りのＭＳ ＢビットはＡi-1を乗算し続ける。ＮビットとＢビットがどちらも１でない場合、全ゼロ値がＣＳＡに多重化される。Ｎビットだけが１である場合、Ｙ0だけがＣＳＡに多重化／加算される。Ｂビットだけが１である場合、Ａi-1がＣＳＡに加算される。ＢビットとＹ0ビットの両方が１である場合、Ａi-1＋Ｙ0がＣＳＡに加算される。
【００６１】
同時に、ＣＳＡからの直列出力が、Ｚストリームを出力するＦＡ２加算器、ユニット４６０を通じて次のｋ・（ｍ−１）Ｓビットに加算される。
【００６２】
Ｚ出力ストリームの関連部分は、Ｚの最初の非ゼロｋ・（ｍ−１）ビットである。
【００６３】
Ｚストリームは、最初のｍ−１回の反復についてＳBレジスタにスイッチされ、最後の反復について定義されたように、ＳBまたはＢレジスタにスイッチされる。
【００６４】
最後の反復で、Ｚストリームは、ＬＳｋゼロ・ビットを無視し、最後のＢ*ストリームである。このストリームはＢレジスタに送られ、次の乗算及び平方で使用される際必要ならばＮだけ減らされる。
【００６５】
最後の反復で、Ｎｄ、遅延ｋクロックサイクルが直列減算器によってＺストリームから減算され、Ｂに進むその結果がＮより大きいかまたはそれと等しいかを検知する。
【００６６】
この段の終了時に、Ｎ、Ｂ及びＳBレジスタからのすべてのビットはＡＬＵに供給されており、結果の最終ｋ＋１ビットはＣＳＡにあり、フラッシュアウトの用意が整っている。
【００６７】
ｇ）装置が停止する。Ｓフラッシュ２５０、Ｂフラッシュ２４０及びＮフラッシュ２６０が出力ゼロ文字列に設定され、次の段階で最後のｋ＋１最上位ビットが確実にＣＳＡからフラッシュアウトされるようにする（正規乗算では、Ｍ７ ＭＵＸ４５０はＳの前の反復から最終桁上げを受け入れるよう設定される）。Ｓはｍ・ｋ＋１有効ビットを有するが、Ｓレジスタはこのデータを受信するｍｋセルだけを有する。この最終ビットは本質的にオーバフロー機構で保存される。
【００６８】
ｅで説明されたように、４７０のＮｄ、遅延ｋクロックサイクルはＺストリームから減算され、Ｘからの有効出力と同期されて、ＢまたはＳレジスタに進むその結果がＮより大きいかまたはそれ以上かを判定する検知機構の微調整を提供する。４８０及び４９０は直列比較装置を備え、ここでモジュラ計算の場合の最後の借りコマンド・ビットだけと整数の自然範囲の正規乗算の場合の（ｋ・ｍ＋１）番目のビットが保存される。
【００６９】
このオーバフロー／借りコマンドはｍ・ｋ番目の有効クロックサイクルで検出される。
【００７０】
ｈ）装置は別のｋサイクルでクロックされ、ＣＳＡから完全にフラッシュアウトされるが、一方別のｋビットは定義された出力レジスタに出るＺである。
【００７１】
次の出口ストリームでＮの減算を実行する関連フリップフロップ・コマンド直列減算器９０または５００への命令は、（Ｚ／２k−Ｎ）≧Ｎ（Ｚはｍ・ｋ番目のＭＳビットを含む）が、次の信号、すなわち、
ＣＳＡの第２最下位セルからのデータ出力ビットであるＳＯ1ビットが１であるか、
または、Ｘ＋Ｓ加算器４６０の内部キャリーアウトであるＣＯ2ビットが１であるか、
または、４８０センス減算器からの借りビットが設定されていない、によって検知されるならば、反復の最後の有効な（ｍ＋１）ｋ番目のクロックサイクルに設定される。
【００７２】
この機構はＭｏｔｏｒｏｌａ及びＳＧＳ−Ｔｈｏｍｓｏｎの２社によって製造されるものとして米国特許第５，５１３，１３３号に現れる。
【００７３】
自然数範囲の乗算の場合、ｍ・ｋ番目のＭＳビットが１であるならばスーパースカラ乗算器で発生し、米国特許第５、５１３，１３３号の機構では発生しないオーバフローを検出することが好適である。その後このオーバフローを次の反復で使用して、Ｓ（一時的結果）ストリームでＭＳ１を挿入することができる。
【００７４】
ｊ）これは最後の反復か。
いいえ、ならばｃ）に戻る。
はい、ならばｍ）に進む。
【００７５】
ｋ）結果の正確な値をここでＢまたはＳレジスタから出すことができる。
【００７６】
Ｙ０ビットは、５つの決定論的量からＹ０Ｓ−Ｙ０ＳＥＮＳＥユニット４３０で次の方法で予想される。
ｉ  Ａi−Ｌ１のＬＳビットとＢｄストリームの次のビット、Ａ0・Ｂd
ii  桁上げ保存累算器からのＬＳキャリーアウト・ビット、ＣＯ0
iii ＣＳＡの第２ＬＳセルからのＳoutビット、ＳＯ1
iv  Ｓストリームからの次のビット、Ｓd
ｖ  ４６０、全加算器からのキャリーアウト・ビット、ＣＯ2
【００７７】
これらの５つの値は一緒に排他的論理和演算され、次のＹ0ビット、Ｙ0iを生成する。（＋）は、排他的論理和を表す。
Ｙ0i＝Ａ0・Ｂd（＋）ＣＯ0（＋）ＳＯ1（＋）Ｓd（＋）ＣＯZ
Ｙ0iビットが１である場合、（必要な２の累乗を乗算された）同じランクの別のＮが通常加算されるが、そうでない場合、Ｎ（法）は通常加算されない。
【００７８】
数の正規範囲での長い自然整数の乗算。
この装置は、正規整数の乗算及び合計を効率的に行うのに適している。こうしたオペランドがすべてｋビット長より長くない場合、処理は好適にはインタリーブなしで実行されるが、そこでは２ｋ＋１ビットのＺストリームが最終記憶装置に送られる。ｋビットより長い整数の場合、処理は所定のインタリーブド・モジュラ演算処理と同様であるが、結果がここでは潜在的に最長オペランドの長さの２倍より１ビット長いことが異なっている。さらに、本発明の装置は、説明された装置で利用可能なリソースを使用して、被乗数Ａ（好適にはＲ１−Ａｉレジスタのセグメントにロードされる）×Ａの乗数Ｂ（好適には前もって指定されたＢレジスタにロードされる）＋第２乗数Ｎ（好適にはＮレジスタにロードされる）×オペランドＣ（Ｒ２レジスタにロードされる）＋装置に入るビット・ストリームＳといった２つの別個の乗算を、最初の反復で、Ｓｄ信号ラインだけから、好適にはＳAレジスタから同時に行うことができる。Ｙ０ ＳＥＮＳＥ装置は使用されない。被乗数は、反復開始前にＲ３レジスタに合計される。反復開始時に、レジスタＲ１、Ｒ２及びＲ３は、反復終了までラッチＬ１、Ｌ２及びＬ３にコピーされる。一方、反復のｍｋ＋ｋ＋１有効クロックサイクル中、Ａ及びＣの次のセグメントが再び事前ロード及び合計されて、次の反復を準備する。
【００７９】
各反復で、Ｚストリームに関する結果の最初のＬＳ ｋビットは、ここでは（ＭＭの場合のように、定義ゼロによってではなく）別個の記憶装置に向けられ、空にされて結果のＬＳ部分、ここでも適切にはＳAレジスタを累算する。最上位ｍｋ＋１ビットは、次の反復の一時量ＳBを含む。最終段階では、ｇ、ｉ及びｊと同様に、ＣＳＡは累算値をフラッシュアウトする。乗数レジスタより長い数に関するＬＳ部分は、正規データアウト・レジスタとアンローダ（それぞれユニット６０及び３０）によって出ることができる。
【００８０】
結果のＭＳ ２ｍ番目のビットは、ＯＶＥＲＦＬＯＷ信号ラインを通じてＦＡ２、ユニット４６０のＬＡＳＴ ＣＡＲＲＹビットから読み出される。
【００８１】
本発明は、図面と共に行われる以下の詳細な説明から理解され認識されるだろう。
【図面の簡単な説明】
【００８２】
【図１Ａ】図１Ａ〜図１Ｂは、一緒に取り上げられ、本発明の１つの実施形態によって構成され動作する直並列スーパースカラ論理演算装置（ＡＬＵ）の単純化された構成図を形成する。
【図１Ｂ】図１Ａ〜図１Ｂは、一緒に取り上げられ、本発明の１つの実施形態によって構成され動作する直並列スーパースカラ論理演算装置（ＡＬＵ）の単純化された構成図を形成する。
【図２】図２は、特に非常に長い数の直列整数除算適用業務について単独でも有益である、図１Ａの直列整数除算装置の好適実現例の単純化された構成図である。
【図３】図３は、図１Ａ〜図１Ｂの直並列論理演算装置を含む、スマートカードまたは端末用の公開鍵暗号計算の単純化された構成図である。
【図４】図４は、除数の有効ビット長が被除数の有効ビット長の半分である例について、図２の除算装置を使用する除数による被除数の除算の演算の段階を示す表である。
【図５】図５は、除数の有効ビット長が被除数の有効ビット長の半分より少ない例について、図２の除算装置を使用する除数による被除数の除算の演算の段階を示す表である。
【発明を実施するための形態】
【００８３】
図１Ａ〜図１Ｂは、一緒に取り上げられ、本発明の好適実施形態によって構成され動作する直並列論理演算装置（ＡＬＵ）の単純化された構成図を形成する。図１Ａ〜図１Ｂの装置には、好適には次の構成要素が含まれる。
【００８４】
単一多重装置−制御されたスイッチング素子であり、多数の信号入力から１つの信号またはビット・ストリームを選択し、この選択された信号を１つの出力に送る。多重装置はＭ１〜Ｍ１３の記号が付けられ、大きな要素の組み込み部分である。
【００８５】
Ｍ Ｋ多重装置３９０はｋ＋１の単一多重装置のアレーであり、４つのｋまたはｋ＋１入力のどれをＣＳＡ４１０に加算するかを選択する。
【００８６】
Ｂ（１０００）、ＳA（１３０）、ＳB（１８０）及びＮ（１００５）は好適実施形態における４つの主直列主レジスタである。ＳAは概念上及び実際上冗長であるが、非常に長い数の計算をかなり加速し、特に法の長さが２・ｋ・ｍビット長である場合揮発性メモリ・リソースを節約し、かつ長い除算計算を単純化する。
【００８７】
直列加算器と直列減算器は２つの直列入力と１つの直列出力を有する論理要素であり、ビットの２つの長い文字列に対して合計または減算を行う。構成要素９０及び４８０は減算器であり、３３０及び４６０は直列加算器である。入力から出力への伝播時間は非常に小さい。直列減算器９０は、Ｂ*がＮより大きいかまたはそれと等しいである場合、Ｂ*をＢに換算する。直列減算器４８０が、比較器構成要素の一部として使用され、Ｂ*がＮより大きいかまたはそれと等しいかを検出する。全加算器３３０は、ロード・バッファ３４０に、２９０及び３２０ロード・バッファの値の合計に等しい値を供給する２つのビット・ストリームを加算する。
【００８８】
高速ローダ及びアンローダ（それぞれ１０及び２０、及び３０及び４０）は、ＣＰＵ制御装置からのデータフローを加速する装置である。これは、好適実施形態ではＤＭＡまたは他のハードウェア・アクセラレータから構成される。２０及び４０はデータ語を逆転するためのもので、図２の除算入力及び出力を調和させるために必要である。
【００８９】
データ入力５０は並列入力直列出力装置であるが、本ＡＬＵ装置は直列供給シストリック・プロセッサであるので、データは並列に入力され、直列に出力される。
【００９０】
データ出力６０は直列入力並列出力装置であり、コプロセッサから結果を出力する。商生成器は、除算機構の各反復で商ビットを生成する図２のその部分である。
【００９１】
Ｂｄ、２４０、Ｓ*ｄ、２５０及びＮｄ、２６０に対するフラッシュ信号は、最後のｋ＋１ビットが確実にＣＳＡからフラッシュアウトされるようにするために作成されているが、代替物は複雑化ｋ＋１ビット並列出力要素であり、累算器のＭＳ ｋ＋１ビットを検索する。
【００９２】
ロード・バッファＲ１、２９０、Ｒ２、３２０及びＲ３、３４０は直列入力並列出力シフトレジスタであり、３つの可能なゼロより多い被乗数の組み合わせを受信することができる。
【００９３】
ラッチＬ１、３６０、Ｌ２、３７０及びＬ３、３８０はロード・バッファからの出力を受信するよう作成されるので、ロード・バッファは、データが好適にもＬ２、Ｌ２及びＬ３にラッチされる前に、このデータの次の段階の処理が一時的にできるようになる。
【００９４】
Ｙ０センス、４３０は、ＬＳゼロのｋビット文字列がモントゴメリー乗算及び平方でＺで出るようにするため、法が累算される回数を決定する論理装置である。
【００９５】
１ビット遅延装置１００、２２０及び２３０はそれぞれのデータ・ストリームに挿入され、図１Ａのデータ準備装置と図１Ｂのデータ処理装置の間の同期の問題を調停する。
【００９６】
ｋビット遅延、シフトレジスタ、４７０は、Ｚ／２kがＮより大きいかまたはそれと等しければ、Ｚ／２kとＮの比較が同期して確実になされるようにする。
【００９７】
桁上げ保存累算器は直並列乗算器とほとんど同一であるが、普通直並列乗算器の入力にラッチされる１つの値の代わりに、３つの異なったゼロより大きい値を合計することができる点が異なっている。
【００９８】
挿入最終桁上げ、４４０は、Ｓストリームのｍｋ＋１番目のビットを挿入するために使用されるが、Ｓレジスタはｍｋビット長しかない。
【００９９】
借り／オーバフロー検出、４９０は、結果が（Ｎからの）法より大きいかまたはそれと等しいか、またはｍｋ番目のビットが１かの何れかを検出することができる。
【０１００】
制御機構は示されないが、好適にはシストリック・データフローのためのスイッチセットを有する１組のカスケード計数装置であるものと理解される。
【０１０１】
数の素数及び複合素数範囲でのモジュラ乗算について、ここでＡ及びＢを被乗数及び乗数として定義し、Ｎを法として定義するが、Ｎは普通ＡまたはＢより大きい。Ｎはまた、法の値が保存されるレジスタをも示す。Ｎは、場合によっては、Ａより小さいことがある。Ａ、Ｂ及びＮはｍ・ｋ＝ｎビット長オペランドとして定義される。各ｋビットのグループは文字と呼ばれ、グループの大きさは乗算装置の大きさによって定義される。次に、Ａ、Ｂ及びＮは各々ｍ文字長である。以下のステップ毎に手順を追う説明を容易にするために、Ａ、Ｂ及びＮは５１２ビット長（ｎ＝５１２）であると想定し、ｋは６４ビット長であると想定するが、これはこうした乗算器の現在の費用効果的な長さと、簡単なＣＰＵのデータ操作速度のためである。またｍ＝８はオペランド中の文字数であり、また５１２ビット・オペランドの平方または乗算ループにおける反復の数でもある。すべてのオペランドは正の整数である。より一般的には、Ａ、Ｂ、Ｎ、ｎ、ｋ及びｍは任意の適切な値を想定する。
【０１０２】
非モジュラ関数では、Ｎ及びＳレジスタは、他の演算オペランドの一時記憶装置として使用できる。
【０１０３】
記号≡が使用され、例えば１６≡２ｍｏｄ７というように、モジュラ数の合同を示すが、ここで、１６を７で割った時剰余が２であるので１６は２モジュロ７に合同であるという。ＹｍｏｄＮ≡ＸｍｏｄＮと書く時、ＹとＸはどちらもＮより大きいが、正のＸ及びＹについて、剰余は同一である。また、負の整数Ｙの合同はＹ＋ｕＮであるが、ここでＮは法であり、Ｙの合同がＮより小さい場合、ｕは正の結果を与える最小の整数である。
【０１０４】
記号￥が使用され、より制限された意味での合同を示す。ここで説明される処理中、値は望ましい値、または望ましい値プラス法の何れかである。例えばＸ￥２ｍｏｄ７という場合、Ｘは２または９に等しい。Ｘは２ｍｏｄ７と制限的合同であるという。
【０１０５】
Ｘ＝ＡｍｏｄＮと書く場合、ＸはＡをＮで割った剰余として定義される。例えば、３＝４５ｍｏｄ７である。
【０１０６】
数論では、モジュラ乗算逆が基本概念である。例えば、Ｘのモジュラ乗算逆はＸ-1と書かれるが、これはＸＸ-1ｍｏｄＮ＝１によって定義される。Ｘ＝３でＮ＝１３の場合Ｘ-1＝９である。すなわち、３・９を１３で割った剰余は１である。
【０１０７】
頭字語ＭＳ及びＬＳは、デジタル用語で慣用されているように、ビット、文字及びフルオペランド値に関連する場合、最上位及び最下位を示すために使用される。
【０１０８】
本明細書を通じて、Ｎは値Ｎと、Ｎを収容するシフトレジスタの名称の両方を示す。数値の上に付いた星印は、数値が現状では潜在的に不完全または変化する可能性があることを示す。Ａは累乗される数の値であり、ｎはＮオペランドのビット長である。初期化の後、ＡがＡ*に「モントゴメリー正規化」される場合（Ａ*＝２nＡ、後で説明される）、Ａ*とＮは累乗の中間ステップを通じて一定の値である。最初の反復中、累乗の初期化後、ＢはＡ*に等しい。Ｂはまた、最終的に累乗の望ましい結果に等しい累算値が存在するレジスタの名前でもある。Ｓ*は一時値を示し、Ｓ、ＳA及びＳBはまた、Ｓの単一ＭＳビットだけが保存されるレジスタ（単数または複数）を示す（このＭＳビットと連結されたＳ*はＳと同一である）。Ｓ（ｉ−１）はｉ番目の反復の開始時のＳの値を示し、Ｓ0は、Ｓ（ｉ）番目の値のＬＳ文字を示す。
【０１０９】
Ｐ範囲での乗算として処理ρ（Ａ・Ｂ）Ｎ（後で定義される）または、簡単に乗算演算が言及される。
【０１１０】
二重動作直並列乗算器を構成する基礎として標準構造の直並列乗算器を使用したため、我々は桁上げ保存累算に基づく乗算器の合計部分を（桁上げ先見加算器またはリップル加算器、前者はかなり複雑になり、後者は非常に低速である、と）区別して、それを桁上げ保存加算器または累算器と呼び、事前ロード機構及び多重装置及びラッチと別個に扱うが、これによってＡ×ＢとＣ×Ｄの乗算を同時に行い２つの結果を加算すること、すなわちＡ×Ｂ＋Ｃ×Ｄが可能になり、この累算器を非常に強力なエンジンに変換する。付加的論理がこの乗算器に追加され、モジュラ減算と直列合計のために必要な予想センス操作を提供するが、これは非常に大きな数の強力なモジュラ演算と普通の整数演算を提供する。
【０１１１】
モントゴメリー・モジュラ乗算
モジュラ乗算を計算する従来のアプローチでは、Ａ・ＢｍｏｄＮ、すなわち積Ａ・Ｂの剰余が除算処理によって計算される。大きなオペランドの従来の除算を実現するのは、直並列乗算を行うより困難である。
【０１１２】
モントゴメリーのモジュラ換算法を使用すると、除算は本質的に２つの事前計算定数を使用する乗算によって置き換えられる。ここで示される手順では、法の関数である１つの事前計算定数だけが存在する。この定数はこのＡＬＵ装置を使用して計算される。
【０１１３】
この装置で使用されるモントゴメリー処理の単純化した表示がここで提供され、それに完全な好適説明が続く。
【０１１４】
奇数（ＬＳビット１）、例えば１０１０００１（＝８１10）がある場合、それに奇数を補償する別のフィクシング、例えば１１１１（＝１５10）を加算することでこの奇数を偶数（１つのＬＳビットがゼロ）に変換することができる、すなわち、１１１１＋１０１０００１＝１１０００００（９６10）である。この特定の場合では、前もって全体の文字列８１を知っていたため５つのＬＳゼロを生じる数を発見し、８１に加算する二進数を容易に発見し、必要な数のＬＳゼロを有する新しい二進数を生成した。このフィクシング数は奇数であり、さもなければ結果のＬＳビットを累加する作用はない。
【０１１５】
行うべき処理がクロックされた直並列桁上げ保存処理で、ＬＳゼロの連続数を有することが望ましく、各クロックサイクルで次のビットを固定しなければならないだけだとすれば、次のビットが潜在的に１である場合フィクシングを加算し、潜在的ビットが０であった場合加算しないことで十分である。しかし、ビット間オーバフロー（二重キャリア）を発生しないために、このフィクシングは好適には前もって被乗数と合計され、関連乗数ビットが１であり、Ｙセンスも１を検出する時累算器に加算される。
【０１１６】
ここでは、モジュラ演算の場合のように、法で割った値の剰余だけに関心があり、法の任意の倍数をその値に加算しても、同じ剰余を有することを知っている。これは任意の整数にＹＮ＝Σｙi２iＮを加算しても同じ剰余を有するということを意味するが、ここでＹは必要なＬＳゼロを生成するために加算する倍数である。説明されたように、加算することのできる法は奇数だけである。偶数の法が、ｉが偶数中のＬＳゼロの数である時生じる奇数の２i倍として定義される方法が存在する。
【０１１７】
モントゴメリー・インタリーブド変化によって解決される問題は、数について有する制限された場所を低減し、乗算器の費用効果的な大きさを得ることを目指している。これは公開鍵暗号関数を行う場合特に有益であるが、そこでは絶えず大きな整数、たとえばｎ＝１０２４ビットと別の大きな整数の乗算が行われ、普通２倍の長さである２０４８ビットの整数を生成する。
【０１１８】
乗算（または平方）の処理中、十分な倍数のＮｓ（法）がＡ・Ｂ＝ＸまたはＡ・Ｂ＋Ｓ＝Ｘに加算されるので、ｎ個のＬＳゼロと、最大ｎ＋１個のＭＳビットを有する数Ｚが得られる。
【０１１９】
これらのゼロを無視することで望ましい結果を２nで除算したことを思い出すならば、ＬＳ ｎビットを無視してこの数を使用し先に進むことができる。
【０１２０】
ＬＳ ｎビットが無視され、最上位ｎ（またはｎ＋１）ビットだけを使用する場合、結果は２-n、すなわち２nのモジュラ逆によって乗算された。次にこの結果に再び２nｍｏｄＮ（または２n）を乗算するならば、（同じ剰余を有する）望ましい結果と合同な値をＡ・Ｂ＋ＳｍｏｄＮとして得ることができる。見られるように、ＭＭを使用すると、結果は好適には２2nによって乗算され、ＭＭによって導入される２-n寄生要素を克服する。
【０１２１】
例：
A・B + S mod N ＝ (12・11+10) mod 13 ＝ (1100・1011+1010)2 mod 11012
ｎＬＳビットにフィクシングが必要な場合常に２iＮを加算する。
【０１２２】
Ｂ          １０１１
×Ａ          １１００
加算Ｓ          １０１０
【０１２３】
加算Ａ（０）・Ｂ      ００００
−−−−ＬＳビットの合計＝０   Ｎを加算しない
加算２0（Ｎ・０）     ００００
合計              ０１０１→０    ＬＳビットは桁上げ保存加算器を出る
【０１２４】
加算Ａ（１）・Ｂ      ００００
−−−−ＬＳビットの合計＝１   Ｎを加算する
加算２1（Ｎ・１）     １１０１
合計              １００１→０    ＬＳビットはＣＳ加算器を出る
【０１２５】
加算Ａ（２）・Ｂ      １０１１
−−−−合計ＬＳビット＝０   Ｎを加算しない
加算２2（Ｎ・０）     ００００
合計              １０１０→０    ＬＳビットはＣＳ加算器を出る
【０１２６】
加算Ａ（３）・Ｂ      １０１１
−−−−合計ＬＳビット＝１   Ｎを加算する
加算２3（Ｎ・１）     １１０１
合計            １０００１→０    ＬＳビットはＣＳ加算器を出る
【０１２７】
結果は１０００１ ００００2ｍｏｄ１３＝１７・２4ｍｏｄ１３である。
【０１２８】
１７は１３より大きいので１３を減算し、結果は次のようになる。
１７・２4≡４・２4ｍｏｄ１３
正式には２-n（ＡＢ＋Ｓ）ｍｏｄＮ＝９（１２・１１＋１０）ｍｏｄ１３＝４となる。
【０１２９】
モントゴメリー演算ではＭＳ非ゼロ結果（４）だけを利用し、真の結果は２nで除算され、ｎゼロはＭＭ結果にされることを有効に記憶する。
【０１３０】
結果に２4ｍｏｄ１３≡３を有効に乗算した（８＋２）・１３＝１０・１３を加算した。実際には、余分のゼロを使用したので、Ａ・Ｂ＋Ｙ・Ｎ＋Ｓ−（１２・１１＋１０・１３＋１０）を１つの処理で行ったと言うことができるが、これは好適実施形態で可能であることが説明される。
チェック−（１２・１１＋１０）ｍｏｄ１３＝１２；４・３＝１２
【０１３１】
要約すると、モントゴメリー乗算の結果は２-nで乗算された望ましい結果である。
【０１３２】
前の結果から同じ乗算法を使用した望ましい結果を検索するために、前の結果を２2nによってモントゴメリー乗算しなければならないが、各ＭＭは２-nの寄生要素を残すので２2nはＨと呼ばれる。
【０１３３】
モントゴメリー乗算関数ρ（Ａ・Ｂ）ＮはＰ範囲（上記の例で４を導出した）へのＡ・Ｂ積の乗算モジュロＮを行う。Ｐ範囲から正規モジュラ範囲への検索は、事前計算定数Ｈを使用してρ（Ａ・Ｂ）Ｎの結果にＰを規定することによって行われる。ここではＰ≡ρ（Ａ・Ｂ）Ｎならば、ρ（Ｐ・Ｈ）Ｎ≡Ａ・ＢｍｏｄＮということになり、２つのＰ範囲乗算で正規モジュラ乗算を行う。
【０１３４】
モントゴメリー・モジュラ減算は、ｎまたはｎ＋１ビット長であるオペランドに対して一連の乗算、加算及び減算を行うことによって、ｎ及び２ｎビット長であるオペランドに対する一連の乗算及び除算演算を回避する。処理全体はＮより小さいかまたはそれと等しい結果を生じる。所与のＡ、Ｂ及び奇数Ｎについて、Ａ・Ｂ＋Ｑ・Ｎが、ｎＬＳビットがゼロであるような数、または
Ｐ・２n＝Ａ・Ｂ＋Ｑ・Ｎ
であるようなＱが常に存在する。これは、ｎＬＳビットがゼロである、２ｎビット長の式を有することを意味する。
【０１３５】
ここで、Ｉ・２n≡１ｍｏｄＮ（Ｉはすべての奇数Ｎについて存在する）とする。前の等式の両側にＩを乗算することで次の合同が生じる。
等式の左辺から、
Ｐ・Ｉ・２n≡ＰｍｏｄＮ（Ｉ・２n≡１ｍｏｄＮを想起されたい）
また右辺から、
Ａ・Ｂ・Ｉ＋Ｑ・Ｎ・Ｉ≡ＡＢ・ＩｍｏｄＮ（Ｑ・Ｎ・Ｉ≡０ｍｏｄＮを想起されたい）
従って、
Ｐ≡Ａ・Ｂ・ＩｍｏｄＮ
これはまた、Ｐ範囲乗算が行われる度毎に寄生要素Ｉ＝２-nｍｏｄＮが導入されることを意味する。
【０１３６】
ρ演算子は次のように定義されるが、
Ｐ≡Ａ・Ｂ・ＩｍｏｄＮ≡ρ（Ａ・Ｂ）Ｎ
これを「Ｐ範囲でのＡ×Ｂの乗算」またはモントゴメリー乗算と呼ぶ。
【０１３７】
Ｐ範囲からの検索はＰ・Ｈに対するρの演算によって計算され、次式を生じる。
ρ（Ｐ・Ｈ）Ｎ≡Ａ・ＢｍｏｄＮ
前の合同でＰを減算することでＨの値が導出され、次式が発見される。
ρ（Ｐ・Ｈ）Ｎ≡（Ａ・Ｂ・Ｉ）（Ｈ）（Ｉ）ｍｏｄＮ
（次を参照：Ａ・Ｂ・Ｉ←Ｐ、Ｈ←Ｈ、Ｉ←及びすべての乗算演算は寄生Ｉを導入する）
【０１３８】
ＨがＩ2の倍数の逆と合同な場合、合同は有効であり、すなわち次式である。
Ｈ＝Ｉ-2ｍｏｄＮ≡２2nｍｏｄＮ
（ＨはＮの関数であり、Ｈパラメータと呼ばれる）
【０１３９】
従来のモントゴメリー法では、Ａ・Ｂにρ演算子を定めるため、事前計算定数Ｊを使用する次の処理が利用される。
１） Ｘ＝Ａ・Ｂ
２） Ｙ＝（Ｘ・Ｊ）ｍｏｄ２n（ｎＬＳビットだけが必要である）
３） Ｚ＝Ｘ＋Ｙ・Ｎ
４） Ｓ＝Ｚ／２n（Ｊに対する要求はＺを２nで割り切れるものにするということである）
５） Ｐ￥ＳｍｏｄＮ（Ｓ≧Ｎの場合、ＮはＳから減算される）
【０１４０】
最後に、ステップ５）で、
Ｐ￥ρ（Ａ・Ｂ）Ｎ
［Ｎの減算の後、必要ならば、
Ｐ＝ρ（Ａ・Ｂ）Ｎ］
【０１４１】
上記に続いて、
Ｙ＝Ａ・Ｂ・Ｊｍｏｄ２n（ｎＬＳビットだけを使用する）
かつ
Ｚ＝Ａ・Ｂ＋（Ａ・Ｂ・Ｊｍｏｄ２n）・Ｎ
【０１４２】
Ｚが２nで割り切れるようにするため（ＺのｎＬＳビットは好適にはゼロ）かつ次の合同が存在する。
［Ａ・Ｂ＋（Ａ・Ｂ・Ｊｍｏｄ２n）・Ｎ］ｍｏｄ２n≡０
【０１４３】
この合同が存在するためには、Ｎ・Ｊｍｏｄ２nが−１と合同であるか、または
Ｊ≡−Ｎ-1ｍｏｄ２n
であり、定数Ｊが発見された。
【０１４４】
従って、ＪはＮだけの関数である事前計算定数である。しかし、ＭＭ結果をビット毎に出力する機械では、ＬＳ文字列の出力ビットがＮｓを加算しなければゼロになる場合毎にＮｓを加算することを規定し、Ｊを事前計算し、次いでＹ＝Ａ・Ｂ・Ｊｍｏｄ２n（Ｙはハードワイヤード論理を使用してビット毎に検出される）を計算する必要を回避すべきである。また、この方法は奇数のＮｓに対してだけ使用できることも説明した。
【０１４５】
従って、明らかなように、説明された処理は、所与のＡ、Ｂ、Ｎ及び事前計算定数について３つの乗算、１つの合計及び最大１つの減算を使用してρ（Ａ・Ｂ）Ｎを得る。この結果と、同じ処理及び事前計算定数Ｈ（モジュロＮの関数）を使用して、ＡＢｍｏｄＮを求めることができる。ＡはＢと等しくてもよいので、この基本演算子は平方またはモジュラ演算での乗算のための装置としても使用することができる。
【０１４６】
インタリーブド・モントゴメリー・モジュラ乗算
本節は、全てｎビット長でありその結果が２ｎ＋１ビットの記憶領域を必要とする乗算を含んだモジュラ乗算の方法を説明する。
【０１４７】
（Ｄｕｓｓｅによる上記の論文で説明された）モントゴメリーのインタリーブド減算を使用すると、より短いオペランド、レジスタ及びハードウェア乗算器で乗算演算を行うことができ、比較的少ない論理ゲートを有する電子装置の実現が可能になる。
【０１４８】
まず、インタリーブの各反復毎に、Ｊ0定数を使用してＮを加算する回数を計算する装置の動作方法を説明する。その後、Ｙ0のハードワイヤ導出を使用するインタリーブの方法を説明するが、これは各乗算のＪ0+段階を除去し｛次の例の２）｝、２つの別個の直列乗算器の機能を、新しい単一汎用乗算器に統合することができるが、これは同様のシリコン・リソースを使用して２倍を越える速度でＡ・Ｂ＋Ｃ・Ｎ＋Ｓを行うことができる。
【０１４９】
ｋビット乗数を使用すると、ｋビット長の文字を定義することが好都合である。ｎビットにはｍ文字が存在する、すなわちｍ・ｋ＝ｎである。
Ｊ0はＪのＬＳ文字である。
従って、
Ｊ0≡−Ｎ0-1ｍｏｄ２k（Ｊ0はＮが奇数の時存在する）
【０１５０】
Ｊ及びＪ0は、補償数であり、あり得る出力に対して規定される場合、最下位ゼロの所定の数を得るために何回法を加算すべきかを知らせることに注意されたい。後でこの直列装置に対する付加的な利点を説明するが、出力の次の直列ビットが容易に判定できるので、常に法（常に奇数）を次の中間結果に加算することができる。これは、この加算なしで、出力ビットである、ＣＳＡを出るＬＳ直列ビットが「１」であり、それによって法を前の偶数中間結果に加算し、それによって出力文字列で次のＬＳゼロを約束する場合そうである。法を何回結果に加算しようとも、剰余は一定であるので、合同が維持されることを想起されたい。
【０１５１】
モントゴメリーのインタリーブド減算の従来の使用では、ρ（Ａ・Ｂ）Ｎはステップ（１）〜（５）で説明されるように、ｍ回の反復で規定される。
【０１５２】
まずＳ（０）＝０（最初の反復開始時のＳの￥値）
ｉ＝１，２，・・・，ｍについて、
１） Ｘ＝Ｓ（ｉ−１）＋Ａi-1・Ｂ（Ａi-1はＡのｉ−１番目の文字、Ｓ（ｉ−１）はｉ番目の反復開始時のＳの値）
２） Ｙ0＝Ｘ0・Ｊ0ｍｏｄ２k（Ｘ0・Ｊ0の積のＬＳｋビット）
（この処理は、ｋＬＳビットだけ、例えば最下位６４ビットを使用し計算する）
好適実現例では、直列機械ではＹ0はビット毎に予想できるためこのステップは回避される。
３） Ｚ＝Ｘ＋Ｙ0・Ｎ
【０１５３】
４） Ｓ（ｉ）＝Ｚ／２k（ＺのｋＬＳビットは常に０であるので、Ｚは常に２kで割り切れる。ＺのＬＳｋビットはすべてゼロであるのでこの除算はｋビット右シフトと同等である、または回路に見られるように、ＺのＬＳｋビットは単純に無視される）
【０１５４】
５） Ｓ（ｉ）＝Ｓ（ｉ）ｍｏｄＮ（Ｎは、Ｎより大きいＳ（ｉ）から減算される）
【０１５５】
最後に、最後の反復で（必要な場合Ｎの減算の後で）、Ｃ＝Ｓ（ｍ）＝ρ（Ａ・Ｂ）Ｎである。Ｆ＝Ａ・ＢｍｏｄＮを導出するために、Ｐ範囲計算、ρ（Ｃ・Ｈ）Ｎが行われる。
【０１５６】
好適実施形態では、すべてのＳ（ｉ）について、Ｓ（ｉ）が２Ｎより小さいことを知ることが望ましい。これはまた、最終結果（Ｓ（ｍ））が常に、最大１回のＮの減算で、Ｎより小さい量まで減らせることを意味する。
【０１５７】
この処理で使用されるオペランドについて以下が観察される。
Ｓ（ｉ−１）＜２n+1（一時レジスタはＢまたはＮレジスタより１ビット長いことがある）
Ｂ＜Ｎ＜２nかつＡi-1＜２k
【０１５８】
定義：
Ｓ（ｉ）＝Ｚ／２k（あり得る減算の前の、処理終了時のＳの値）
により、すべてのＺについて、Ｚ（ｉ）＜２n+k+1 
Ｘmax＝Ｓmax＋Ａi・Ｂ＜２n+1−１＋（２k−１）（２n−１）
Ｑmax＝Ｙ0Ｎ＜（２k−１）（２n−１）
従って、
Ｚmax＜２k+n+1−２k-1＋１＜２k+n+1−１
であり、Ｚmaxを２kで除算すると、
Ｓ（ｍ）＜２n+1−２1
Ｎmin＞２n−２なので、Ｓ（ｍ）maxは常に２・Ｎminより小さく、従って最終結果のために必要なのは１つの減算だけである。
Ｓ（ｍ）max−Ｎmin＝（２n+1−２1−１）−（２n−１）＝２n−４＜Ｎmin
【０１５９】
モントゴメリー・インタリーブド・モジュラ乗算の例：
１６進法形式での次の計算はインタリーブド法の意味を明らかにする。
Ｎ＝ａ５９（モジュロ）、Ａ＝９９ｂ（乗数）、Ｂ＝５ｃ３（被乗数）、ｎ＝１２（Ｎのビット長）、ｋ＝４（乗数のビット単位のサイズ、かつ文字のサイズ）及びｎ＝ｋ・ｍなのでｍ＝３
７・９≡−１ｍｏｄ１６及びＨ≡２2・12ｍｏｄ ａ５９≡４４ｂなのでＪ0＝７
予想される結果は、Ｆ≡Ａ・ＢｍｏｄＮ≡９９ｂ・５ｃ３ｍｏｄ ａ５９≡３７５８１１ｍｏｄ ａ５９＝２２０16
【０１６０】
初め、Ｓ（０）＝０
ステップ１
Ｘ＝Ｓ（０）＋Ａ0・Ｂ＝０＋ｂ・５ｃ３＝３ｆ６１
Ｙ0＝Ｘ0・Ｊ0ｍｏｄ２k＝７（Ｙ0−新しいＭＡＰにおけるハードワイヤ予想）
Ｚ＝Ｘ＋Ｙ0・Ｎ＝３ｆ６１＋７・ａ５９＝８７ｄ０
Ｓ（１）＝Ｚ／２k＝８７ｄ
【０１６１】
ステップ２
Ｘ＝Ｓ（１）＋Ａ1・Ｂ＝８７ｄ＋９・５ｃ３＝３ｃ５８
Ｙ0＝Ｘ0・Ｊ0ｍｏｄ２k＝８・７ｍｏｄ２4＝８（ハードワイヤ予想）
Ｚ＝Ｘ＋Ｙ0−Ｎ＝３ｃ５８＋５２ｃ８＝８ｆ２０
Ｓ（２）＝Ｚ／２k＝８ｆ２
【０１６２】
ステップ３
Ｘ＝Ｓ（２）＋Ａ2・Ｂ＝８ｆ２＋９・５ｃ３＝３ｃｃｄ
Ｙ0＝ｄ・７ｍｏｄ２4＝ｂ（ハードワイヤ予想）
Ｚ＝Ｘ＋Ｙ0・Ｎ＝３ｃｃｄ＋ｂ・ａ５９＝ａｅａ０
Ｓ（３）＝Ｚ／２k＝ａｅａ
Ｓ（３）＞Ｎなので、
Ｓ（ｍ）＝Ｓ（３）−Ｎ＝ａｅａ−ａ５９＝９１
従ってＣ＝ρ（Ａ・Ｂ）Ｎ＝９１16
【０１６３】
Ｐ範囲からの検索がρ（Ｃ・Ｈ）Ｎを計算することによって行われる。
再び初め、Ｓ（０）＝０
【０１６４】
ステップ１
Ｘ＝Ｓ（０）＋Ｃ0・Ｈ＝０＋１・４４ｂ＝４４ｂ
Ｙ0＝ｄ（新しいＭＡＰにおけるハードワイヤ予想）
Ｚ＝Ｘ＋Ｙ0・Ｎ＝４４ｂ＋８６８５＝８ａｄ０
Ｓ（１）＝Ｚ／２ｋ＝８ａｄ
【０１６５】
ステップ２
Ｘ＝Ｓ（１）＋Ｃ1・Ｈ＝８ａｄ＋９・４４ｂ＝２ｆ５０
Ｙ0＝０（新しいＭＡＰにおけるハードワイヤ予想）
Ｚ＝Ｘ＋Ｙ0・Ｎ＝２ｆ５０＋０＝２ｆ５０
Ｓ（２）＝Ｚ／２k＝２ｆ５
【０１６６】
ステップ３
Ｘ＝Ｓ（２）＋Ｃ2・Ｈ＝２ｆ５＋０・４４ｂ＝２ｆ５
Ｙ0＝３（新しいＭＡＰにおけるハードワイヤ予想）
Ｚ＝Ｘ＋Ｙ0・Ｎ＝２ｆ５＋３・ａ５９＝２２００
Ｓ（３）＝Ｚ／２k＝２２０16
これは９９ｂ ５ｃ３ｍｏｄ ａ５９の期待値である。
【０１６７】
各ステップでｋＬＳゼロを無視すると、本質的にｎＭＳビットを２kで乗算することになる。同様に、各ステップで、乗数のｉ番目のセグメントも２ikによって乗算された数であり、それにＳ（ｉ）と同じランクを与える。
【０１６８】
別の好適実施形態でも、それがＪ0定数を知るためのある予想値のものであることに注意されたい。
【０１６９】
累乗  
次のシーケンスの導出［Ｄ．Ｋｎｕｔｈ、コンピュータ・プログラミングの技術、第２巻、準数値的アルゴリズム、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ、マサチューセッツ州レディング、１９８１年］（以下「Ｋｎｕｔｈ」と呼ぶ）はモジュラ累乗を実現する平方と乗算の順序を説明する。
【０１７０】
モントゴメリー定数Ｈ＝２2nの事前計算後、この装置はＰ範囲での平方と乗算を行うことができるので、以下を計算する。
Ｃ＝ＡEｍｏｄＮ
Ｅ（ｊ）が、インデックスがＩであるＭＳビットから始まりインデックスがｑであるＬＳビットで終わる指数Ｅのバイナリ表示でｊビットを示すとすると、奇数の指数について以下のように累乗を行うことができる。
【０１７１】
Ａ*￥ρ（Ａ・Ｈ）Ｎ      Ａ*はここではＡ・２nに等しい
Ｂ＝Ａ* 
ＦＯＲ  ｊ＝２〜ｑ−１
Ｂ￥ρ（Ｂ・Ｂ）Ｎ
Ｅ（ｊ）＝１ならば、
Ｂ￥ρ（Ｂ・Ａ*）Ｎ
ＥＮＤＦＯＲ
Ｂ￥ρ（Ｂ・Ａ*）Ｎ      Ｅ（０）＝１：Ｂは２nで乗算された最終的な望ましい結果であり、ＡはもとのＡである。
Ｃ＝Ｂ
Ｃ≧ＮならばＣ＝Ｃ−Ｎ
最後の反復後、値Ｂは￥からＡEｍｏｄＮであり、Ｃは最終的な値である。
【０１７２】
これを明らかにするために、次の例を使用する。
Ｅ＝１０１１→Ｅ（１）；Ｅ（２）＝０；Ｅ（３）＝１；Ｅ（４）＝１
【０１７３】
Ａ1011ｍｏｄＮ；ｑ＝４を発見するために、
Ａ*＝ρ（Ａ・Ｈ）Ｎ＝ＡＩ-2Ｉ＝ＡＩ-1ｍｏｄＮ
Ｂ＝Ａ* 
ｊ＝２〜ｑについて、
Ｂ＝ρ（Ｂ・Ｂ）Ｎ、これはＡ2（Ｉ-1）2Ｉ＝Ａ2・Ｉ-1を生じる
Ｅ（２）＝０、Ｂ＝Ａ2・Ｉ-1 
ｊ＝３      Ｂ＝ρ（Ｂ・Ｂ）Ｎ＝Ａ2（Ｉ-1）2Ｉ＝Ａ4Ｉ-1 
Ｅ（３）＝１Ｂ＝ρ（Ｂ・Ａ*）Ｎ＝（Ａ4・Ｉ-1）（ＡＩ-1）・Ｉ＝Ａ5・Ｉ-1 
ｊ＝４      Ｂ＝ρ（Ｂ・Ｂ）Ｎ＝Ａ10・Ｉ-2・Ｉ＝Ａ10・Ｉ-1
Ｅ（４）は奇数だったので、最後の乗算はＡによって、寄生Ｉ-1を除去するために行われる。
Ｂ＝ρ（Ｂ・Ａ）Ｎ＝Ａ10・Ｉ-1・Ａ・Ｉ＝Ａ11 
Ｃ＝Ｂ
逆数処理によってＨパラメータを計算する方法は米国特許第５，５１３，１３３号で説明されている。
【０１７４】
長い除算処理
図２は、図１Ａのプロセッサで利用可能なデータ操作装置を使用して長い除算を行う決定論的処理装置の好適実施形態を例示する。
【０１７５】
図４及び図５は、図２の装置の演算の例である。
【０１７６】
除数ｄがｄ、２n-1＜ｄ＜２nの範囲内で、被除数ＤがＤ、２2n-1＜Ｄ＜２2nの範囲内である除算処理では、装置は最も簡単に使用される。ｄが図２のＮ右シフトレジスタ１００５（Ｎ０及びＮ１レジスタ、２１０及び２００の連結）に事前ロードされ、被除数ＤのＭＳｎビットがＢ右シフト・レジスタ（１０００）に事前ロードされた後、ＤのＬＳビットがＳA右シフト・レジスタ（１３０）に逆ロードされる。これは本質的に、手動の長い除算のために数字を配置するように、新しい試行減算毎に新しいＬＳビットがＳAからＳBに供給されることを実現する。ＳBレジスタはすべてゼロで事前ロードされる。
【０１７７】
初期化反復では、図２のオーバフロー・フリップフロー１７０がまずリセットされる。ここでは除数ｄを含むＮレジスタがＤＣのＭＳビットであるＢから試行減算される一方、Ｂ及びＮが回転されるが、ここでそれらの出力は直列減算器９０に供給され、その出力はＢ−ｆＮであり、減算の場合ｆ＝１、減算しない場合ｆ＝０である。商生成器１２０はＢ≧Ｎかを判定する検出器であり、９０で次の反復の際ｄがＢから減算されるかを判定する「次の減算」を送信する。この信号は、ＢがＮより大きいかそれと等しい場合、かつその場合のみ１である。この「次の減算」ビットは成功を示し、商の最上位ビットであり、やはりＳBレジスタ１８０にクロックされる。これがＳBレジスタにクロックされているので、ゼロはＳBレジスタからＳAレジスタにシフトされ、「新しいＬＳビット」をＳAレジスタから出す。これらのレジスタは全て右シフトレジスタなので、ＳBの商の値とＳAの被除数の値はどちらも逆の順序で保持されることに注意されたい。
【０１７８】
次の反復では、最初の有効クロックサイクルで、ＳAからシフトされた「新しいＬＳビット」が９０の出力Ｒの前に置かれ、それによってＲに２を乗算し、「新しいＬＳビット」の値を２Ｒに加算する。この連結値は回転されてＢレジスタに戻され、１２０で試験されて、次のラウンドでｆ＝１かｆ＝０かを判定する。
【０１７９】
最後に、剰余がＢレジスタにあり、商のｎビットがＳBレジスタにあり、商の最上位ビットがＳAレジスタにある。
【０１８０】
被除数と除数両方の最上位は好適には、すべての大きさのＤとｄについて、ＢレジスタとＮレジスタの最上位ビット・セルにある。結果を得るために必要な反復の数は２2n-1より小さいＤｓの場合減少し、２n-1より小さいｄｓの場合増大する。装置はハードウェア駆動型であり、装置をアンロードする際オペランドをシフトするファームウェア補償が提供される。
【０１８１】
図３の不揮発性メモリにあるプログラムは、好適にはレジスタがロードされていることを確認し、制御レジスタのために除算処理を成功させるために必要な反復の数を定義する。逆データ出力アンローダ、ユニット６０及び４０を通じて処理される場合、商ビットはバイト毎に再逆転される。
【０１８２】
このプロセッサはＨパラメータの計算に有益な要素であり、また好適にはユークリッド関数の計算でも使用される。
【０１８３】
図１Ａの直列整数除算装置と、Ａ×Ｂ＋Ｃ×Ｄ＋Ｓを行う図１Ｂの二重動作乗算器は、通常同時に動作しない。
【０１８４】
図４の例では、被除数Ｂは１８７（１０１１１０１１）であり、除数Ｎは７（１１１）であり、除算が実行されると、商は２０（１０１００）となり余りは７（１１１）となる。
【０１８５】
図５の例では、被乗数Ｂは１７３（１０１０１１０１）、除数Ｎは５（１０１）であり、除算か実行されると、商は３４（１０００１０）となり余りは３（１１）となる。
【０１８６】
桁上げ保存累算器はＧｒｅｓｓｅｌに対する米国特許第５，５１３，１３３号の図５に例示されている。
【０１８７】
直列全加算器はＧｒｅｓｓｅｌに対する上記の米国特許の図７に例示されている。
【０１８８】
直列減算器はＧｒｅｓｓｅｌに対する上記の米国特許の図８に例示されている。
【０１８９】
除算装置はＧｒｅｓｓｅｌに対する上記の米国特許の図９に例示されている。
【０１９０】
「整数の正規範囲」という術語は負でない整数、例えば自然数のことである。
【０１９１】
本発明の好適実施形態によれば、ここで示され説明されたシステムはａ及びｂをゼロにリセットしＳ0＝１を設定することでＪ0を計算するよう動作する。
【０１９２】
この特許書類の開示の一部は著作権保護の対象となる資料を含んでいる。著作権所有者は特許書類または特許開示が特許商標局の特許ファイルまたは記録にある限り、その何者かによるファクシミリ複写に反対しないが、そうでない場合は何があろうともすべての著作権を留保する。
【０１９３】
本発明のソフトウェア構成要素は、望ましい場合、ＲＯＭ（読み出し専用記憶素子）の形態で実現される。ソフトウェア構成要素は、一般に、望ましい場合、従来の技術を使用してハードウェアで実現される。
【０１９４】
本発明の様々な特徴は、わかりやすくするために別個の実施形態の文脈で説明されたが、１つの実施形態に組み合わせて提供されることもあることが認識されるだろう。逆に、簡潔にするために１つの実施形態の文脈で説明された様々な特徴が個別または何らかの適切な形でさらに組み合わされて提供されることもある。
【０１９５】
当業技術分野に熟練した者には、本発明はここに示され説明されたものに制限されないことが認識されるだろう。むしろ、本発明の範囲は以下の請求項のみによって定義される。
【図１Ａ】
2009230153.tif 000003
【図１Ｂ】
2009230153.tif 000004
【図２】
2009230153.tif 000005
【図３】
2009230153.tif 000006
【図４】
2009230153.tif 000007
【図５】
2009230153.tif 000008