(57)【要約】出願人によって先に実装されたような同時縮小を有する直列／並列モンゴメリモジュラー乗算法の拡張であって、素体及びＧＦ（２ｑ）多項式ベースのフィールドの両方において、先のモジュラー乗算手順を拡張する複数の予測関数を実行することによりオペランドのフローを簡略化して実行するのに革新的に適している。
2004501396.tif 000002
【特許請求の範囲】
【請求項１】
多項式ベースのＧＦ（２ｑ）及びＧＦ（ｐ）の両フィールドの演算において▲○×▼乗算及び平方を実行するマイクロエレクトロニクス装置であって、
平方及び減算が直列供給される基数２▲ｌ▼の乗数Ｂをｋ文字の被乗数セグメントＡｉ及びｋ文字の▲○＋▼アキュムレーターと共に使用し、限定された合同がモジュラスＮ上で被乗数Ａｉに乗数Ｂを掛け合わせてシストリックな態様で「即座に」実行され、その結果が多くとも２ｋ＋１文字長さであり、保存されないｋの最初に発生し無視されたゼロ文字を含み、ｋ文字がモジュラスと同等のビットを有する前記演算が二つの段階で行われ、
各々が少なくともｎビット長さのオペランドを保持するように動作し、夫々符号Ｂの乗数値及び符号Ｎの２ｎより小さなモジュラスを保存するように動作する第一主メモリレジスタ手段Ｂ及び第二主メモリレジスタ手段Ｎと、
装置から発生する全ての最初のｋ文字がゼロにされるように▲○＋▼アダーアキュムレーターデバイスにおける値にモジュラス値が▲○＋▼加算されるような場合に、「即座に」予測するように動作するデジタル論理検知検出器Ｙ０と、
ただ一つの少なくともｋ文字長さの▲○＋▼加算器と、ｋ文字の被乗数を受け入れるように動作する▲○＋▼加算装置と、順番に被乗数値を▲○＋▼アキュムレーターデバイス内に入れ替え、順番にＢレジスタから乗数値を受け入れるように動作する▲○×▼乗算装置と、第一段階においてｋの最初に発生するゼロ文字を出力させるように動作する乗数と同時に生成した「即座の」予測値とを有し、各々の有効マシンサイクルで少なくとも一つの指定された被乗数が▲○＋▼加算装置に▲○＋▼加算される、少なくともｋ文字の入力被乗数のためのモジュラー乗算装置と、
全ゼロ文字列の値である第一被乗数、被乗数Ａｉである第二被乗数、モジュラスのＮ０セグメントである第三被乗数のうちの一つ若しくは二つの被乗数からなる、順番に▲○＋▼アキュムレーションデバイス内に入れ替えられる被乗数値と、
▲ｌ▼ビットのｋ文字直列入力Ｙ０乗数値を予測する装置と、
第一段階において乗算装置に順番に入力されるＢオペランドである乗数値と、同時に、最初に発生するゼロを出力させるための「即座の」予測されたｋ文字列であるＹ０からなる第二乗数値と、
▲○＋▼アキュムレーションデバイスであって、被乗数が該アキュムレーションデバイスへ▲○＋▼加算されると同時に値を出力するように動作する▲○＋▼アキュムレーションデバイスと、
第二段階において▲○＋▼アキュムレーションデバイスからの最終のモジュラー▲○×▼乗算の結果を出力するように動作する出力転送機構とからなるマイクロエレクトロニクス装置。
【請求項２】
▲○＋▼アキュムレーションデバイスへの▲○＋▼加算が、各々の新たな直列にロードされた高位乗数により始まる請求項１記載のマイクロエレクトロニクス装置。
【請求項３】
乗数が、入力されたＢ文字と対応する入力されたＹ０文字の両方がゼロの場合は、▲○＋▼アキュムレーションデバイスへの▲○＋▼加算はされず、
入力されたＢ文字が１であり、対応するＹ０がゼロである場合は、Ａｉ被乗数のみが▲○＋▼加算され、
入力されたＢ文字がゼロであり、対応するＹ０が１である場合は、モジュラスＮのみが▲○＋▼加算され、
入力されたＢ文字と対応するＹ０文字の両方が１である場合は、被乗数Ａｉと共にモジュラスＮが▲○＋▼加算されるように動作する請求項１記載のマイクロエレクトロニクス装置。
【請求項４】
被乗数値Ａｉ，Ｎを二つの指定されたプリロードバッファにプリロードし、これらの値を第三プリロードバッファに▲○＋▼加算するように動作して、各々の被乗数値を別々に▲○＋▼加算する必要をなくす請求項１記載のマイクロエレクトロニクス装置。
【請求項５】
乗数値が入力において直列単一文字であり、▲○＋▼アキュムレーションデバイスの出力が直列単一文字出力であり、Ｙ０検出装置が一回のクロックで一文字のみ予測するように動作する請求項１記載のマイクロエレクトロニクス装置。
【請求項６】
▲○＋▼アキュムレーションデバイスが２を法としてＸＯＲ加算／減算の計算を実行し、加算成分及び減算成分中の全ての桁上げビットが無視されることにより、計算における桁溢れや更に限定する有益性が排除される請求項１記載のマイクロエレクトロニクス装置。
【請求項７】
全ての桁上げ入力がゼロ（▲Ｓ▼＝０を意味する）まで実行不能とされ、概して、多項式ベースの乗算を実行するように動作する請求項１記載のマイクロエレクトロニクス装置。
【請求項８】
▲Ｓ▼がＧＦ（２ｑ）において計算する回路方程式中の要素に影響するゼロに等しく、▲Ｓ▼が除かれた回路を示し、▲○＋▼で表される全ての加算器及び減算器が縮小されて、２を法とした加算／減算要素の排他的論理和を求める請求項１記載のマイクロエレクトロニクス装置。
【請求項９】
ｋの最初に発生するゼロが次のＹ０文字を予測する際に、
ｉ．　Ａｉレジスタの右側文字にＢストリームのＢｄ文字を掛けた▲ｌ▼ビット毎の２▲ｌ▼を法とする▲○×▼乗算の結果の▲ｌ▼ビットのＳｏｕｔビット　Ａ０・Ｂｄ ｍｏｄ ２▲ｌ▼、
ｉｉ．　▲○＋▼アキュムレーションデバイスから最初に発生する桁上げ文字▲Ｓ▼（ＣＯ０）、
ｉｉｉ．　▲○＋▼アキュムレーションデバイスの右側の発生セルからの次に発生する桁上げ文字からの▲ｌ▼ビットのＳｏｕｔ文字ＳＯ１、
ｉｖ．　Ｎ０モジュラス被乗数レジスタにおける右側文字の負の逆数である▲ｌ▼ビットのＪ０値、
の四つの数量によって調整される装置から発し、
前記Ａ０・Ｂｄ ｍｏｄ ２▲ｌ▼、▲Ｓ▼（ＣＯ０）、ＳＯ１の値が、共に文字に▲○＋▼加算される文字であり、▲ｌ▼ビットのゼロを発する有効なＹ０ゼロ強制予測文字を出力するために「即座に」Ｊ０文字によって乗算される請求項１記載のマイクロエレクトロニクス装置。
【請求項１０】
多項式ベースのオペランドでの▲○×▼乗算が逆モードで実行され、右側のＭＳ文字から左側のＬＳ文字を乗算し、モンゴメリ型寄生関数なしでモジュラー縮小された▲○×▼乗算を実行するように動作する請求項１記載のマイクロエレクトロニクス装置。
【請求項１１】
プリロードバッファが直列供給され、被乗数値が複数の記憶装置から即座にプリロードバッファにプリロードされる請求項１記載のマイクロエレクトロニクス装置。
【請求項１２】
プロセスにおいて用いられる有限体に適するように、▲○＋▼が加算を定義し、▲○×▼が乗算を定義し、
Ｙ０検出器が▲○＋▼アキュムレーションデバイスにおいて▲○＋▼加算にモジュラスを▲○＋▼加算する必要性を検出ように動作する時に、最初に発生する出力文字がゼロであるように、▲ｌ▼ビットの▲○＋▼加算器回路を経由して、更なるｎビットのレジスタＳから発生する先の値が▲○＋▼アキュムレーションデバイスの出力値に▲○＋▼加算され、Ｙ０検出器が、次に順番に加算した文字Ａ０・Ｂｄ ｍｏｄ ２、▲Ｓ▼（ＣＯ０）、ＳＯ１、Ｓｄ、▲Ｓ▼（ＣＯＺ）を利用して、▲ｌ▼ビットのＪ０値により即座に▲○×▼乗算される有限フィールドであるように▲○＋▼加算される文字の合成を検出するように動作する請求項１記載のマイクロエレクトロニクス装置。
【請求項１３】
▲ｌ▼＝１で、ハードウェアを追加することなく、Ｊ０が暗黙的に１であり、Ｊ０▲○×▼乗算が暗黙的である請求項１記載のマイクロエレクトロニクス装置。
【請求項１４】
コンパレータが、最初の右側の発生するｋゼロ文字が無視されるＧＦ（ｐ）において機能し、▲○×▼モジュラー乗算装置からの有限フィールド出力を検知するように動作し、その出力がモジュラスＮより大きいことにより、モジュラー縮小をを調整するように動作し、前記値が、乗算装置からの出力ストリームの行き先であるメモリレジスタから出力されることにより、より小さな積の値に第二の記憶装置を割り当てる必要がなくなる請求項１記載のマイクロエレクトロニクス装置。
【請求項１５】
ＧＦ（２ｑ）における▲○×▼モジュラー乗算で、前記マイクロエレクトロニクス装置が外部で予め計算された▲ｌ▼ビットより大きなゼロ強制因子なしで乗算するように動作する請求項１記載の装置。
【請求項１６】
Ａオペランド値又はＢオペランド値のいずれかをゼロに再設定し、部分的な結果値Ｓ０を１に設定することにより、Ｊ０定数を計算するように動作する請求項１記載の方法。
【請求項１７】
ＡにＢを掛けてモジュラスがＮとなる出力ストリームを生成するように動作する、整数Ａ及びＢのインタリーブされた有限体▲○×▼モジュラー乗算を実行するマイクロエレクトロニクス装置であって、モジュラスオペランドレジスタにおける文字の数ｎがｋよりも大きく、▲○×▼乗算プロセスが反復で実行され、各々のインタリーブされた反復で▲○×▼乗算装置に入力されるオペランドは、モジュラスＮ、乗数Ｂ、予め計算された部分的な結果Ｓ、被乗数Ａのｋ文字列セグメントからなり、セグメントはＡ０文字列セグメントからＡｍ−１文字列セグメントまで進行し、各々の反復の結果は次の順番の一時的結果Ｓに▲○＋▼加算され、反復結果の最初に発生する文字はゼロであって、
各々がオペランドを保存、出力でき、夫々乗算値、部分的な結果値、Ｎで示されるモジュラスを保存するように動作する第一主メモリレジスタＢ、第二主メモリレジスタＳ、第三主メモリレジスタＮと、
反復▲○×▼乗算プロセスの間、順番に複数の被乗数値の一つ又は二つを▲○＋▼アキュムレーションデバイスに▲○＋▼加算し、順番に第一の値であるＢレジスタからの入力と、各々の反復において最初の右側ゼロを出力させる乗数である第二の値である「即座の」予測値Ｙ０の入力と、Ｎレジスタからの第三の値であるモジュラスの入力とを乗数として受け入れるように動作するモジュラー乗算装置と、
少なくとも、Ａ，Ｂ，Ｎレジスタ資源からの値を順番に受け入れ、続いて被乗数ゼロ強制値Ｙ０をも受け入れるように動作する被乗数並列レジスタと、
第一段階の間乗数となるように動作し、第二段階の間被乗数となるように動作する二進列（ｂｉｎａｒｙ ｓｔｒｉｎｇ）を生成するように動作する最初に発生するゼロ強制Ｙ０検出装置と、
第一にゼロ、第二に被乗数Ａのｋ文字列セグメントであるＡｉ、第三にモジュラスＮの最初に発生するｋ文字であるＮ０からなる、第一段階で▲○＋▼アキュムレーションデバイスに入れ替える被乗数値と、
次の反復で並列の結果を生成するために、アキュムレーションデバイスから発する値に加算される先の反復の結果である一時的結果値Ｓと、
第一にゼロ、第二に第一段階から残存するオペランドＡｉ、第三に第一段階で予測されたＹ０値である、第二段階でアキュムレーションデバイスに順番に入力される被乗数値と、
Ｂオペランドの最初に発生する文字列セグメントである、最初に発生する文字列Ｂ０であり、第二段階でプリロードされた被乗数バッファに生成すると同時に文字毎にロードされる予測されたＹ０文字列からなる第二の乗数値と並行して乗算する第一段階で乗算装置に入力される乗数値と、
夫々、Ｂで表されるＢオペランドからの左側ｎ−ｋ文字の値と、Ｎで表されるＮモジュラスの左側ｎ−ｋ文字である、第二段階の間に装置に入力される二つの乗数値と、
アキュムレーションデバイスに残存する結果値の左側セグメントを結果レジスタに転送するように最終段階で動作する乗算フラッシュアウト装置とからなるマイクロエレクトロニクス装置。
【請求項１８】
ＭＳ文字からＬＳ文字まで乗算する逆モードにおいて多項式ベースのオペランドで乗算が実行され、モンゴメリ型寄生関数なしでモジュラー縮小を実行するように動作する請求項１７記載のマイクロエレクトロニクス装置。
【請求項１９】
被乗数の最初に発生する値、Ｂ乗数の現在の入力、アキュムレーションデバイスからの桁上げ値、アキュムレーションデバイスからの加算値、先に計算された部分的な結果からの現在の値、先の部分的な結果にアキュムレーションデバイスからの結果を加算する加算器からの桁上げ値を用いてＹ０値を予測するように動作する装置。
【請求項２０】
ｋの最初に発生するゼロが、次の順番のＹ０文字を予測する際に、
ｉ．　Ａｉレジスタの右側文字にＢストリームのＢｄ文字を掛けた▲ｌ▼ビット毎の２▲ｌ▼を法とする乗算の結果の▲ｌ▼ビットのＳｏｕｔビット　Ａ０・Ｂｄ ｍｏｄ ２▲ｌ▼、
ｉｉ．　アキュムレーションデバイスから最初に発生する桁上げ文字▲Ｓ▼（ＣＯ０）、
ｉｉｉ．　アキュムレーションデバイスの右側の発生セルからの第二からの▲ｌ▼ビットのＳｏｕｔ文字ＳＯ１、
ｉｖ．　Ｓストリームからの次の順番の文字値Ｓｄ、
ｖ．　Ｚ出力全加算器からの▲ｌ▼ビット桁上げ文字▲Ｓ▼（ＣＯＺ）、
ｖｉ．　Ｎ０モジュラス被乗数レジスタにおける右側文字の負の逆数である▲ｌ▼ビットのＪ０値、
の六つの数量によって調整される装置から発し、
前記Ａ０・Ｂｄ ｍｏｄ ２▲ｌ▼、▲Ｓ▼（ＣＯ０）、ＳＯ１、Ｓｄの値が、共に文字に▲○＋▼加算される文字であり、▲ｌ▼ビットのゼロ文字列を発するように有効なＹ０ゼロ強制予測文字を出力するために「即座に」Ｊ０文字によって▲○×▼乗算される請求項１９記載の装置。
【請求項２１】
出力結果をモジュラスＮと比較するように動作する少なくとも一つのセンサからなり、その機構が、結果レジスタの出力に第二の減算器を動作させることにより、出力された結果値と限定された合同であるモジュラー縮小された値を出力するように動作し、より小さな結果に第二の記憶装置を割り当てる必要を排除する請求項１７記載のマイクロエレクトロニクス装置。
【請求項２２】
最初の値の一つがプリロードバッファにロードされるのと並行して、二つの被乗数の加算である値が、少なくとも一つのｋ文字メモリ手段レジスタでプリロード文字バッファにロードされる請求項１７記載のマイクロエレクトロニクス装置。
【請求項２３】
一連のインタリーブされた▲○×▼モジュラー乗算及び平方を実行するように動作し、三つの自然数乗算演算と同等のものを並行して実行する、結果がべき算である単一のアキュムレーションデバイス及び予測ゼロ強制機構を有する装置。
【請求項２４】
次の順番に用いられる被乗数が、即座にプリロードレジスタバッファ手段にプリロードされる請求項１７記載のマイクロエレクトロニクス装置。
【請求項２５】
二つの被乗数の合計である値が、その一つの値がそのプリロードバッファにロードされるのと並行して少なくとも一つのｋ文字レジスタに加算される請求項１７記載のマイクロエレクトロニクス装置。
【請求項２６】
装置のバッファ及びレジスタは外部メモリー資源からの値をロードされるように動作し、前記バッファ及びレジスタは計算の間に外部メモリー資源にアンロードされるように動作し、オペランドの最大サイズが利用できるメモリー手段に依存する請求項１７記載のマイクロエレクトロニクス装置。
【請求項２７】
メモリーレジスタ手段が、概して、直列単一文字入力／直列単一文字出力、並列少なくともｋ文字入力／並列少なくともｋ文字出力、直列単一文字入力／並列少なくともｋ文字出力、並列少なくともｋ文字入力／直列単一文字出力である請求項１７記載のマイクロエレクトロニクス装置。
【請求項２８】
乗算型反復の最終段階の間、乗数入力が桁上げ保存累算メモリーの左側セグメントをフラッシュアウトするように動作するゼロ文字である請求項１７記載のマイクロエレクトロニクス装置。
【請求項２９】
次の順番の被乗数が、即座にプリロードメモリーバッファにプリロードされる請求項１７記載のマイクロエレクトロニクス装置。
【請求項３０】
被乗数値が、中央記憶装置から即座にプリロードバッファにプリロードされる請求項１７記載のマイクロエレクトロニクス装置。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は暗号の共同処理用周辺装置（ｃｒｙｐｔｏｇｒａｐｈｉｃ ｃｏ−ｐｒｏｃｅｓｓｉｎｇ ｐｅｒｉｐｈｅｒａｌｓ）を速めるための演算装置に関するものであり、更に、楕円曲線及びＲＳＡ型の計算のために設計されたモジュラー演算公開鍵暗号コプロセッサ（ｍｏｄｕｌａｒ ａｒｉｔｈｍｅｔｉｃ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｃｏｐｒｏｃｅｓｓｏｒ）における整数体の計算範囲及び直列の入力オペランド幅を拡張する多項式ベースで素数フィールド（ｐｒｉｍｅ ｎｕｍｂｅｒ ｆｉｅｌｄ；素体）の演算のための加速された演算装置に関するものである。
【０００２】
（背景技術）
計算装置のセキュリティ強化及び機能高速化は、出願人による米国特許第５７４２５３０号明細書（以下Ｐ１と称す）、第５５１３１３３号明細書、第５４４８６３９号明細書、第５２６１００１号明細書、第５２０６８２４号明細書、公開された国際出願第ＰＣＴ／ＩＬ９８／００１４８号（国際公開第９８／５０８５１号パンフレット）、対応する米国特許出願公開第０９／０５０９８号明細書（以下Ｐ２と称す）、オニスチャック（Ｏｎｙｓｚｃｈｕｋ）らの米国特許第４７４５５６８号明細書、オムラらの米国特許第４５８７７６２７号明細書、及び出願人の米国特許出願公開第０９／４８０１０２号明細書に記載されているが、本願はこれらの開示を参考文献として取り込んでいる。
出願人の米国特許第５２０６８２４号明細書には、多項式ベースの乗算及び平方を実行する初期の演算装置が示されているが、素数フィールドにおける演算（ｏｐｅｒａｔｉｏｎ）を行うことはできず、多項式ベースの計算においてインタリーブする（ｉｎｔｅｒｌｅａｖｅ）ように設計されていない。
更なる解析が、パール・シー（Ｐａａｒ， Ｃ．），エフ・フライシュマン（Ｆ． Ｆｌｅｉｓｃｈｍａｎｎ），ピー・ソリア−ロドリゲス（Ｐ． Ｓｏｒｉａ−Ｒｏｄｒｉｇｕｅｚ）著、「素数ではない数（合成数）を有するガロア体における公開鍵アルゴリズムのための高速演算（Ｆａｓｔ Ａｒｉｔｈｍｅｔｉｃ ｆｏｒ Ｐｕｂｌｉｃ−Ｋｅｙ Ａｌｇｏｒｉｔｈｍｓ ｉｎ Ｇａｌｏｉｓ Ｆｉｅｌｄｓ ｗｉｔｈ Ｃｏｍｐｏｓｉｔｅ Ｅｘｐｏｎｅｎｔｓ）」、コンピュータに関するＩＥＥＥ論文集、第４８巻、第１０号、１９９９年１０月（ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ， ｖｏｌ． ４８， Ｎｏ． １０， Ｏｃｔｏｂｅｒ １９９９）（以下パールと称す）で、多項式ベースの演算における拡大体を利用するアプローチによりなされている。
ダブリュー・ウエズレー・ピーターソン（Ｗ． Ｗｅｓｌｅｙ Ｐｅｔｅｒｓｏｎ），イー・ジェー・ウェルドン・ジュニア（Ｅ． Ｊ． Ｗｅｌｄｏｎ Ｊｒ．）著、「エラー訂正コード（Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ Ｃｏｄｅｓ）」、第二版、エムアイティープレス（ＭＩＴ Ｐｒｅｓｓ）、ケンブリッジ、マサチューセッツ州（Ｍａｓｓ．）、１９７２年、ｐ．１７４−１７９（以下ピーターソンと称す）、では、多項式ベースの剰余表現ＧＦ（２ｑ）における除算実行回路を示している。
ピーターソンの回路は、乗数がまさにモジュラス（ｍｏｄｕｌｕｓ；剰余）の長さである装置においてのみ利用され得る。
典型的には、それは本装置より２倍の長さがある装置を必要とし、コンパクトなインプリメンテーション（ｉｍｐｌｅｍｅｎｔａｔｉｏｎ；実装）には経済的ではない。
また、マルチビット文字（ｍｕｌｔｉｂｉｔ ｃｈａｒａｃｔｅｒ；マルチビットキャラクター）のＹ０を決定する従来装置を備えていないので、インタリーブされた（ｉｎｔｅｒｌｅａｖｅｄ）インプレメンテーションにも使用できず、▲ｌ▼が１より長い場合は有効でない。
【０００３】
クヌース『ディー・クヌース（Ｄ．Ｋｎｕｔｈ）著、「コンピュータプログラミングの技法（Ｔｈｅ ａｒｔ ｏｆ ｃｏｍｐｕｔｅｒ ｐｒｏｇｒａｍｍｉｎｇ）」、第２巻、準数値算法（Ｓｅｍｉｎｕｍｅｒｉｃａｌ ａｌｇｏｒｉｔｈｍｓ）、アディソン・ウェズリー（Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ）、リーディング、マサチューセッツ州、１９８１年、ｐ．４０７』は、多項式ベースの除算において、単一の▲ｌ▼ビット文字に通常の除算プロセスを使用する旨を暗示しているのに対し、我々は商における次の文字を予測する方法を仮定でき、本発明が論理構成（ｌｏｇｉｃ ｃｏｎｆｉｇｕｒａｔｉｏｎ）を利用して決定論的に商の次の文字を予測する方法を開示する。
【０００４】
（発明の開示）
本発明の目的は、様々な基数での乗算器においてインタリーブされたモジュラー乗算（ｉｎｔｅｒｌｅａｖｅｄ ｍｏｄｕｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）及び縮小（ｒｅｄｕｃｔｉｏｎ）を同時に実行するために同じ予測法（ａｎｔｉｃｉｐａｔｉｎｇ ｍｅｔｈｏｄ）を利用して、多項式ベース（ｐｏｌｙｎｏｍｉａｌ ｂａｓｅｄ）及び素数ベースの数値体フィールド（ｎｕｍｂｅｒ ｆｉｅｌｄ）における大数計算（ｌａｒｇｅ ｎｕｍｂｅｒ ｃｏｍｐｕｔａｔｉｏｎｓ）を実行するように機能するマイクロエレクトロニクス専用の算術演算装置を提供することである。
【０００５】
本発明の更なる目的は、非常に大きな整数でのモジュラー及びノーマルな（自然数であって負でない整数の体）乗算、除算、加算、減算、べき算を実行するためのコンパクトなマイクロエレクトロニクス専用の算術論理演算装置に関するものである。
簡略化された多項式ベースの乗算及び平方のためにモンゴメリ法及び逆フォーマット法（ｒｅｖｅｒｓｅｄ ｆｏｒｍａｔ ｍｅｔｈｏｄ）の両方を利用するモジュラー乗算及び平方に言及する場合、スーパースカラ（ｓｕｐｅｒｓｃａｌａｒ）モジュラー算術コプロセッサ、ＳＭＡＰ、ＭＡＰ、若しくはＳｕｐｅｒＭＡＰ（商標）のような装置の特定部分が参照され、また、出願人の１９９８年３月３１日に提出された米国特許出願公開第０９／０５０９５８号明細書及び２０００年１月１０日に提出された米国一部継続出願公開第０９／４８０１０２号明細書に存在する改良に関するものが参照される。
【０００６】
本願明細書において記載される本発明の好ましい実施例は、携帯型スマートカードで、概して一般に普及している磁気帯付クレジット及びバンクカードと形状及びサイズが同一の公開鍵暗号アプリケーションのためのモジュラー計算演算子を提供する。
出願人の米国特許第５５１３１３３号、５７４２５３０号明細書の技術及び出願人の上述した出願の技術による同様のスマートカードは、コンピュータ、データベース、商取引、軍事用取引、家庭内取引におけるデータフローを調整し保全するため及びスクランブルされた有料テレビプログラムを復号する等のための重要な装置、同様の応用のための端末装置としての重要な装置へのアクセスを制御するための新世代の公開鍵暗号装置において利用される。
典型的には、これらの装置は、コンピュータ−ファクシミリ端末、ドアロック、自動販売機等にも組み込まれている。
【０００７】
好ましい構成（ａｒｃｈｉｔｅｃｔｕｒｅ；アーキテクチャ）は、多数のマイクロコントローラ及びデジタル信号処理装置並びに減少した命令セット計算設計（ｒｅｄｕｃｅｄ ｉｎｓｔｒｕｃｔｉｏｎ ｓｅｔ ｃｏｍｐｕｔａｔｉｏｎａｌ ｄｅｓｉｇｎ）に集積されて動作する装置である一方で、該装置はホストの処理装置と並列に演算する。
【０００８】
この実施例は、好ましくは、本質的に２〜３つの乗算装置の役割を果たすたった一つの乗算装置を利用するものであり、該乗算装置は、出願人の米国特許第５５１３１３３号明細書に記載され、米国特許出願公開第０９／０５０９５８号明細書及び国際出願ＰＣＴ／ＩＬ９８／００４８で改良された構成に、基本的には近似している。
従来のマイクロエレクトロニクス技術を利用して、本発明の装置は、スマートカード超小形電子回路上へ記憶装置と共に制御ユニットを集積化される。
【０００９】
多項式ベースの体（ｆｉｅｌｄ）におけるハードウェア実装と素数からなる体（ｆｉｅｌｄ：フィールド）におけるハードウェア実装との間の主な差異は、多項式ベースの加算及び減算が、ＬＳからＭＳへの桁上げ信号の伝搬のない単純なＸＯＲ論理演算であるということである。
従って、ハードウェア実装における隣接するセル間で相互作用がなく、減算と加算が同一の手順（ｐｒｏｃｅｄｕｒｅ）となる。
著者が知っている最初の公表は、１９９４年にイタリアのペルージャで開催されたユーロクリプト・コンフェレンス・ランプ・セッション（Ｅｕｒｏｃｒｙｐｔ Ｃｏｎｆｅｒｅｎｃｅ Ｒｕｍｐ Ｓｅｓｓｉｏｎ）でフォンダツィオーネ・ウーゴ・ボルドーニ（Ｆｏｎｄａｚｉｏｎｅ Ｕｇｏ Ｂｏｒｄｏｎｉ）のマルコ・ブッチ（Ｍａｒｃｏ Ｂｕｃｃｉ）による短い講演であるが、この時でさえ当業者であるエンジニアの間にこの構成はよく知られていた。
【００１０】
Ｐ１，Ｐ２に記載された出願人の先の装置は、概して、ＧＦ（ｐ） 体における楕円曲線暗号プロトコルを効率的に計算するために備えられたものである。
本発明においては、ＧＦ（２ｑ） 体における使用のために、我々は、多項式体における隣接する二進数ビット間で相互作用がないので、モンゴメリ関数やモンゴメリ寄生要素（Ｍｏｎｔｇｏｍｅｒｙ ｐａｒａｓｉｔｅ）を導入することなくスーパースカラ乗算装置で縮小（Ｒｅｄｕｃｔｉｏｎ）及び乗算を同時に実行して、計算が効率的に行われることを示す。
計算機が好ましくは最上位の部分積から始めて、ＧＦ（２ｑ）における乗算が実行される。
縮小は、ＭＳの１をゼロに再設定するのに必要なだけモジュラスを加算することによって実行される。
これらの加算において、桁上げはないので、結果は自動的にモジュラー方式で（ｍｏｄｕｌａｒｌｙ）縮小される。
本発明において、多項式計算は同じ構成を利用して実行されるが、そこにおいて、ＧＦ（２ｑ）ではオペランドは最初にＭＳ文字において供給され、全ての内部桁上げ信号はゼロにされる。
ＧＦ（ｐ）計算は好ましくはＰ１及びＰ２に記載のように実行され、そこにおいて、ＬＳ文字は最初に処理され、ＭＳ文字は最後に処理される。
【００１１】
該構成は、直列乗算器が▲ｌ▼ビットの幅広文字（▲ｌ▼ ｂｉｔ ｗｉｄｅ ｃｈａｒａｃｔｅｒｓ）であり、各々のクロックで、▲ｌ▼ビット文字が桁上げ保存累算器ＣＳＡから発生される（ｂｅ ｅｍｉｔｔｅｄ；エミットされる）という点で、潜在的により速い進行（ｐｒｏｇｒｅｓｓｉｏｎ；数列）を可能にするように拡張されてきた。
このことは、単一ビットの広さのバスで２ｘを法とした奇数の反転（ｉｎｖｅｒｓｉｏｎ；逆転）も奇数であるという点で予測プロセス（Ｙ０）をいくらか複雑にし、被乗数（Ｊ０）の最下位ビットが常に１であった。
しかし、両方の数値体で、我々が、ｋ文字がゼロの文字列を出力することのみが目的であることを覚えており、Ｙ０関数をゼロ強制ベクトル（ｚｅｒｏ ｆｏｒｃｉｎｇ ｖｅｃｔｏｒ；ゼロフォーシングベクトル）としてのみ見なす場合は、桁上げをなくする（制限する）と仮定すると、縮小プロセスは同一である。
【００１２】
本発明は、米国特許第５５１３１３３号明細書に記載されたプロセスに関連する計算的、論理的、算術的な新規な特徴を有する従来のデジタルプロセッサの周辺機器であるデジタル装置の構成を提供しようとするものでもある。
【００１３】
好ましくは、概して各々の演算で大スケールの乗算及び除算を実行する古典的な乗算／除算装置により実行されるのと同様の演算数で除算することなくモジュラーべき算を実行するために、並列プロセス及びハードウェアアーキテクチャが提供される。
本発明の好ましい実施例の特別の特徴は、より大きなスケールの予測ゼロ強制関数（ａｎｔｉｃｉｐａｔｏｒｙ ｚｅｒｏ ｆｏｒｃｉｎｇ ｆｕｎｃｔｉｏｎ）の並列化（ｃｏｎｃｕｒｒｅｎｃｙ；同時進行）、数値体の拡張、及び安全な通信のためのこの種のユニットを集積化する能力である。
【００１４】
本発明の好ましい実施例によって認識される利点は、直列プロセスの同期シーケンスから生じる。
これらのプロセスは、ｎの有効クロックサイクル（ｅｆｆｅｃｔｉｖｅ ｃｌｏｃｋ ｃｙｃｌｅ）において一つの多重化されたｋ文字の直列／並列乗算器を用いて、同時に（並列的に）ｎ文字のオペランドで三つの乗算演算を成し遂げるように組み合わされ、結果の左側の最後のｋ文字は乗算装置の出力バッファに存在する。
この手順は、モンゴメリによって記載されるように、素数からなる体（ｆｉｅｌｄ：フィールド）で両体における三つの乗算計算と同等のものを得ることができ、ＧＦ（２ｑ）において二つの乗算及び一つの除算プロセスと同等のものを得ることができる。
【００１５】
ＳｕｐｅｒＭＡＰへのオペランドのロード及びオペランド数値の即座の（ｏｎ ｔｈｅ ｆｌｙ；高速の）検出と、即座のプリローディング（ｐｒｅｌｏａｄｉｎｇ）及び使用されたオペランドの隣の同時の加算とを同期することにより、装置は決定論的に（ｉｎ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｆａｓｈｉｏｎ）計算を実行するように機能する。
次の反復の平方シーケンスで三つの初めのｋ文字変数を即座にプリロードする全ての乗算及びべき算回路が好ましくは加わる。
好ましくは検出装置が備えられ、ｋの有効クロックサイクル待ち状態を排除して、三つのオペランドのうちの二つだけが次の反復の被乗数に選択される。
条件付き分岐（ｃｏｎｄｉｔｉｏｎａｌ ｂｒａｎｃｈ）が、局所検出及び補正装置（ｌｏｃａｌ ｄｅｔｅｃｔｉｏｎ ａｎｄ ｃｏｍｐｅｎｓａｔｉｏｎ ｄｅｖｉｃｅ）と置換されることにより、単純な制御機構での基準を備えることとなる。
ここに記載された基本的な演算は、典型的には、グレッセル（Ｇｒｅｓｓｅｌ）らに付与された米国特許第５５１３１３３号明細書に記載された装置又はフランスのルーセ（Ｒｏｕｓｓｅｔ）にあるエスティマイクロエレクトロニクス社（ＳＴＭｉｃｒｏｅｌｅｃｔｒｏｎｉｃｓ）による商品名ＳＴ１９−ＣＦ５８の装置を用いて、ＧＦ（ｐ）において決定論的な時間で実行される。
【００１６】
オペランドが全演算に亘って外部の揮発性記憶装置へロードされ装置内に保存されるので、本発明の装置は、ほとんどの演算について外部の揮発性記憶装置に特に依存する。
装置は、好ましくは、ＭＡＰがその大数計算を実行する間に、単純なロード及びアンロード並びに装置へのコマンドのシーケンスを実行するために、装置が追加されたＣＰＵを利用する。
現在、スマートカードに応用されている大数は、１２８ビットから２０４８ビットまでの自然数の応用に及ぶ。
べき算処理時間は仮想的にＣＰＵから独立しており、これによりＣＰＵを制御する。
実際には、ＣＰＵに装置を追加する時に、設計上の変更は典型的には不必要である。
ハードウェアデバイスは自己内蔵型であって、好ましくはいかなるＣＰＵバスにも追加される。
【００１７】
一般的に、本発明は、大きな整数の演算処理にも関するものである。
これらの大数は典型的には、（ゼロ以上の）整数の自然数体（ｎａｔｕｒａｌ ｆｉｅｌｄ：自然数フィールド）におけるものか、又は、素数のガロア体ＧＦ（ｐ）、合成数モジュラス（ｃｏｍｐｏｓｉｔｅ ｐｒｉｍｅ ｍｏｄｕｌｕｓ）、多項式ベースの数のガロア体ＧＦ（２ｑ）におけるものである。
とりわけ、本発明の好ましい実施例は、大数のモジュラー演算及びべき算を実行することができる装置を提供しようとするものである。
このような装置は、素数フィールドにおいて次第に大きなオペランドで機能し、現存のモジュラー演算コプロセッサでは効率的に実行できず、ソフトウェア構築でも、しっかりと実行できないような公開鍵暗号認証（Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｉｃ ａｕｔｈｅｎｔｉｃａｔｉｏｎ）及び暗号化プロトコルの演算を実行することに適している。
好ましくは、より小さい桁である整数に関して、同じ全体的な構成が楕円曲線の実装（ｉｍｐｌｅｍｅｎｔａｔｉｏｎ）において利用される。
新規な乗算の逆モード法（ｒｅｖｅｒｓｅ ｍｏｄｅ ｍｅｔｈｏｄ；リバースモード法）を利用して、ゼロを生成することにより計算の際に寄生的な２−ｎ因子の負担がないので、多項式演算は有利である。
【００１８】
該構成は、直列単一文字のバス（ｓｅｒｉａｌ ｓｉｎｇｌｅ ｃｈａｒａｃｔｅｒ ｂｕｓ）を広げることによって、即ちより大きな基数の使用によって可能になった標準的な小さなオペランドの演算を可能する一方で、大きなオペランド整数の演算のモジュラー実行をも可能にする。
概して、これは、計算を高速化し、ＳｕｐｅｒＭＡＰを実行するためのシリコン領域を減少し、一般に普及しているデジタル信号プロセッサ（ＤＳＰ）で互換性がある長さの装置を生成することに有効である。
【００１９】
奇数の素体及び合成数体（ｃｏｍｐｏｓｉｔｅ ｆｉｅｌｄ；合成体）におけるモジュラー乗算について、Ａ及びＢは、夫々被乗数及び乗数と定義され、Ｎはモジュラー演算におけるモジュラスと定義される。
Ｎは、Ａ又はＢより概して大きい。
Ｎは、モジュラスの値が保存される合成レジスタ（ｃｏｍｐｏｓｉｔｅ ｒｅｇｉｓｔｅｒ；複合レジスタ）を意味する。
Ｎは、若干の場合において、概してＡより小さい。
Ａ，Ｂ，Ｎは概してｎ文字長さであり、その文字は概して１〜８ビットの長さである。
ｋは、乗算装置のサイズ（セル数）により定められる群のサイズにおける▲ｌ▼ビットの文字の数である。
同様に、多項式ベースのＧＦ（２ｑ）計算において、モジュラスＮは、ＭＳビットが１である（モニック（ｍｏｎｉｃ）である）ｎビットの長さであり、Ａ，Ｓ，Ｂのオペランドも適切に縮小された場合はｎビットの長さである。
ＧＦ（２ｑ）計算の結果がモニックである場合、前記結果の値からモジュラスで排他的論理和を求める（ＸＯＲ）ことにより、好ましくはＭＳゼロを有する値へ「縮小される（ｂｅ ｒｅｄｕｃｅｄ）」。
好ましい実施例において、ＧＦ（２ｑ）の最初の有効ビットが逆モードにおいて形成されるので、ＭＡＰはそのビットが１であるか否かを検知する（ｓｅｎｓｅ）ことができ、好ましい縮小を実行できる。
【００２０】
素体において、≡、或いは、若干の場合の＝は、例えば１６ ≡ ２ ｍｏｄ ７のように、モジュラー数の合同を意味するように利用される。
１６を７で割った場合、２が剰余であるので、１６は７を法として（ｍｏｄｕｌｏ ７）２と「合同である」と言う。
Ｙ ｍｏｄ Ｎ ≡ Ｘ ｍｏｄ Ｎの場合、Ｙ，Ｘの両方がＮより大きくてもよいが、正のＸ，Ｙについては、剰余は同一である。
負の整数Ｙの合同がＹ＋ｕ・Ｎ（Ｎはモジュラス）であることにも留意する必要があり、Ｙの合同がＮ未満となるような場合は、ｕは正の結果を与える最も小さい整数である。
【００２１】
ＧＦ（２ｑ）において、加算及び減算が同一であり、通常の計算は、概して実質的な桁溢れを残さないので、合同はより単純である。
Ｎ＝１１０１，Ａ＝１００１について、左側のＡのＭＳビットが１であるので、我々は２を法とした演算、Ａ ＸＯＲ Ｎ＝１００１ ＸＯＲ １１０１＝０１００を利用することにより、ＡからＮを縮小（「減算」）しなければならない。
【００２２】
円記号￥は、ＧＦ（ｐ）において特に有用な限定された意味（ｌｉｍｉｔｅｄ ｓｅｎｓｅ）における合同を意味するように用いられる。
ここに記載されるプロセスの間、値はしばしば所望の値か、若しくは所望の値にモジュラスを加えた値と等しいかのいずれかである。
例えばＸ ￥ ２ ｍｏｄ ７の場合である。
Ｘは、２又は９と等しくなり得る。
Ｘは、７を法として２が限定された合同（ｌｉｍｉｔｅｄ ｃｏｎｇｒｕｅｎｃｅ ｔｏ ２ ｍｏｄ ７）を有すると定義される。
円記号がＢ￥のように上付文字として用いられる場合、０≦Ｂ￥＜２Ｎであり、別の表現をすれば、Ｂ￥はＢ￥と合同である最小の正のＢと等しいか、又は最小の正のＢにモジュラスＮを加えたものと合同のものと等しいかのいずれかである。
本発明に特有のその他の記号は、後でまとめて説明する。
【００２３】
Ｘ＝Ａ ｍｏｄ Ｎの場合、ＸはＡをＮで割った剰余として定義され、即ち、３＝４５ ｍｏｄ ７であり、ＧＦ（２ｑ）ではより単純であり、即ち、１１１１ ｍｏｄ １００１＝０１１０である。
【００２４】
数論において、Ｘのモジュラー逆数（ｍｏｄｕｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｉｎｖｅｒｓｅ）はＸ−１と記述され、Ｘ・Ｘ−１ ｍｏｄ Ｎ＝１によって定義される。
Ｘ＝３、Ｎ＝１３の場合、Ｘ−１＝９であり、即ち、ＧＦ（ｐ）において３・９を１３で割った剰余は１である。
【００２５】
両方の数値からなる体で、我々は概して、指数関数を利用して、Ａの逆数を計算する方を選択するので、例えば、Ａ−１ ｍｏｄ ｑ≡Ａｑ−２ ｍｏｄ ｑである。
【００２６】
略語ＭＳ及びＬＳは、デジタル用語で一般に用いられているように、ビット、文字、全オペランド値に言及する場合に夫々「最上位」及び「最下位」を意味するように用いられるが、逆モードの多項式ベースにおいて、オペランドは最初にＭＳデータをロードされ、最後にＬＳデータをロードされ、そこにおいて、データ語（ｄｅｔａ ｗｏｒｄ）のビットオーダー（ｂｉｔ ｏｒｄｅｒ）は、ロード時に逆にされる（ｂｅ ｒｅｖｅｒｓｅｄ）。
【００２７】
この明細書の全体に亘って、Ｎは値Ｎ、及び、Ｎを保存する送りレジスタ（ｓｈｉｆｔ ｒｅｇｉｓｔｅｒ）の名称の両方を示す。
値上のアスタリスクの上付き文字は、その値が潜在的に不完全であるか変化する可能性があることを意味する。
Ａは累乗されるべき数値であり、ｎはＮオペランドのビット長さである。
初期状態設定の後、ＡがＡ＊に「モンゴメリＰ体に標準化された（Ｍｏｎｔｇｏｍｅｒｙ Ｐ ｆｉｅｌｄｎｏｒｍａｌｉｚｅｄ）」（Ｐ１に記載したＡ＊＝２ｎ・Ａ）場合、Ａ＊及びＮは、概してべき算における中間段階を通じて一定値である。
計算がビットの標準的な逆にされていない位置（ｕｎｒｅｖｅｒｓｅｄ ｐｏｓｉｔｉｏｎｉｎｇ）によって実行されるＧＦ（２ｑ）計算において、我々はこの同じプロトコルによって結合される（ｂｅ ｂｏｕｎｄ）。
しかし、桁上げがないので、逆フォーマットを利用して、我々の計算は最上位ゼロを生成し、それを無視し、乗算のシフト（ｓｈｉｆｔ；桁送り）を表さない。
【００２８】
第一の反復の間、べき算の初期状態設定の後、ＢはＡ＊に等しい。
Ｂは、最終的にべき算の所望の結果と等しくなる累算された値が存在するレジスタの名称でもある。
Ｓ又はＳ＊は一時的な値を示し、Ｓは、ＧＦ（ｐ）のＳにおける数の単一のＭＳビット以外の全てを保存するレジスタを示す。
（このＭＳビットに連結されるＳ＊は、Ｓと同一である。）
Ｓ（ｉ−１）は、ｉ番目の反復の最初でのＳの値を意味する。
これらの多項式計算において、Ｓ上のモジュラー縮小を実行する必要はない。
【００２９】
概して、素数フィールドにおけるＸ，Ｙのモンゴメリ乗算は、実際に（Ｘ・Ｙ・２−ｎ） ｍｏｄ Ｎの実行であり、ｎは概してモジュラスにおける文字数である。
これは
【外１】
2004501396.tif 000003
と記述され、Ｐ体におけるＭＭ又は乗算を意味する。
モンゴメリ数学のコンテクスト（ｃｏｎｔｅｘｔ）において、我々は、Ｐ体及び多項式ベースの体における乗算及び平方を乗算及び平方演算と称す。
【００３０】
我々は、ＧＦ（２ｑ）におけるモンゴメリ型演算のこの革新的な拡張を、逆フォーマットのデータ順序（ｄａｔａ ｏｒｄｅｒ）を意味するように再定義するが、ＭＳゼロ強制（ＭＳ ｚｅｒｏ ｆｏｒｃｉｎｇ）は合同を変更させず、若しくは、厄介な寄生要素（ｐａｒａｓｉｔｉｃ ｆａｃｔｏｒ）を開始させない。
従って、我々は、演算の拡張を受け入れるため及びより広い直列乗算器バスを有する構成を可能にするために、新たな記号のセットを導入する。
自然数のスーパースカラ乗算器を可能にするために、１ビットを越える直列乗算器ストリームが好ましい。
このような乗算器装置は、同時にモジュラー算術乗算及び縮小を実行することができる装置に、３２ビット被乗数及び４ビット乗数を受け入れることができる。
【００３１】
直列／並列のスーパースカラモジュラー乗算器の拡張における記号
【外２】
2004501396.tif 000004
文字のビット数（桁）
ｒ：乗数（ｍｕｌｔｉｐｌｉｅｒ ｃｈａｒａｃｔｅｒ）の基数　ｒ＝２▲ｌ▼
ｎ：文字におけるオペランド（乗数、被乗数、モジュラス）のサイズ。
モンゴメリ演算のＧＦ（ｐ） 体における計算の実証において、▲ｌ▼は１に等しく、ｎはモジュラスのオペランドのビット長である。
ｋ：文字における直並列の乗数の長さ
ｍ：被乗数のインタリーブされたスライス（ｓｌｉｃｅ）（セグメント）の数で、ｍ＝ｎ／ｋ
Ｓｉ：ｉ番目のＭＭ反復の部分積の結果で、０≦ｉ≦ｍ−１，Ｓ０＝０
Ｓｉ０：Ｚの第一のｋ文字の右側ゼロを無視した後の、ｉ番目の反復結果の右側の文字Ｓｉ：ｉ番目の結果の左側のｎ−ｋ文字
Ｓｉｊ：Ｓｉのｊ番目の文字
Ａ：ｍ・ｋ文字からなる並列の被乗数
Ａｉ：Ａのｉ番目のｋ文字のスライス（及び／又は文字列Ａｉ）
Ａｉｔ：Ａｉのｔ番目の文字
Ｂ：直列乗数（及び／又はＢのレジスタ記憶装置）
Ｂ０：Ｂの最初の右側のｋ文字
Ｂ：Ｂの最後の左側の（ｎ−ｋ）文字
Ｂ０ｊ：Ｂ０のｊ番目の文字
Ｂｊ：Ｂのｊ番目の文字
Ｎ：モジュラスのオペランド。｛及び／又は前記乗数を保存するレジスタ。｝
Ｎ０：Ｎの右側のｋ文字。｛ＧＦ（ｐ）におけるＬＳ文字，ＧＦ（２ｑ）におけるＭＳ文字｝
Ｎ：Ｎの左側の（ｎ−ｋ）文字。｛ＧＦ（ｐ）におけるＭＳ文字，ＧＦ（２ｑ）におけるＬＳ文字｝
Ｎ０ｊ：Ｎ０のｊ番目の文字
Ｎｊ：Ｎのｊ番目の文字
Ｙ０：ＧＦ（ｐ）におけるモンゴメリ乗算及び縮小の両方に必要なゼロ強制変数。
Ｙ０は、ｋ文字長さである。
Ｙ０ｊ：Ｙ０のｊ番目の文字
Ｒ：桁上げ保存アキュムレーターに存在する値の総和（未解の内部桁上げ挿入（ｃａｒｒｙ ｉｎｓ）を含む）及び最終の直列加算器（ｓｅｒｉａｌ ｓｕｍｍａｔｏｒ；直列総和器）４６０からの桁上げビット（ｃａｒｒｙ ｏｕｔ ｂｉｔ）。
Ｊ００：「即座の」有限体乗算及び縮小のためのモジュラスＮのゼロ強制文字関数。　▲ｌ▼＝１ではＪ００は常に１に等しい。
Ｃａｒｒｙｊ：基数ｒの直並列乗算器のｊ番目の内部桁上げ文字
Ｃａｒｒｙａ：ＧＦ（ｐ）計算のための出力直列加算器の基数ｒの桁上げ
Ｓｕｍｊ：基数ｒの直並列乗算器のｊ番目の内部の和の文字。
ＬＳ：最下位
ＭＳ：最上位
‖：連結（ｃｏｎｃａｔｅｎａｔｉｏｎ）　例えばＡ＝１１０，Ｂ＝１１０１の時、Ａ‖Ｂ＝１１０１１０１
右側：全てのＧＦ（ｐ）計算データブロックの最下位の部分と逆にされたＧＦ（２ｑ）フォーマットのＭＳ部分
左側：全てのＧＦ（ｐ）計算データブロックの最上位の部分と逆にされたＧＦ（２ｑ）フォーマットのＬＳ部分
ＧＦ（ｐ）：ガロア体。厳密に言うと、加算、減算、乗算、擬除算（ｐｓｅｕｄｏ−ｄｉｖｉｓｉｏｎ）を許容する合成数（二つの非常に大きな素数の積）を使用する素数での有限体。
ＧＦ（２ｑ）：ガロア体で２を法とする演算を利用する有限体。
【外３】
2004501396.tif 000005
特定の記数法に適するように、桁上げの有無に関わらず整数を加算又は減算するために外部で切り換えられる演算子又は装置。
【外４】
2004501396.tif 000006
ＧＦ（ｐ）又はＧＦ（２ｑ）のいずれかで乗算を実行するために切り換えられる演算子又は装置。
【外５】
2004501396.tif 000007
数値体スイッチであり、▲Ｓ▼＝１の場合、スイッチはＧＦ（ｐ）計算で全ての桁上げの入出力を可能にするように機能し、▲Ｓ▼＝０の場合、スイッチはＧＦ（２ｑ）　計算で全ての桁上げ入出力を不可能にするように機能する。
ＳｕｐｅｒＭＡＰ：本発明の目的である登録商標のスーパースカラモジュラー演算プロセッサ系統（Ｓｕｐｅｒｓｃａｌａｒ Ｍｏｄｕｌａｒ Ａｒｉｔｈｍｅｔｉｃ Ｐｒｏｃｅｓｓｏｒ ｆａｍｉｌｙ）の構成要素の一つ。
ＳｕｐｅｒＭＡＰの商標は、ヨーロッパにおいて登録され、米国においては係属中である。
【００３２】
本発明の第一の態様によると、多項式ベースのＧＦ（２ｑ）及びＧＦ（ｐ）の両体の演算において▲○×▼乗算及び平方を実行するマイクロエレクトロニクス装置であって、平方及び減算が直列供給される基数２▲ｌ▼の乗数Ｂをｋ文字の被乗数セグメントＡｉ及びｋ文字の▲○＋▼アキュムレーターと共に使用し、限定された合同がモジュラスＮ上で被乗数Ａｉに乗数Ｂを掛け合わせてシストリックな（ｓｙｓｔｏｌｉｃ）態様で「即座に」実行され、その結果が多くとも２ｎ＋１文字長さであり、保存されないｋの最初に発生し無視されたゼロ文字を含み、ｋ文字がモジュラスと同等のビットを有し、前記演算が二つの段階で行われ、各々が少なくともｎビット長さのオペランドを保持するように動作し、夫々符号Ｂの乗数値及び符号Ｎの２ｎより小さなモジュラスを保存するように動作する第一主メモリレジスタ手段Ｂ及び第二主メモリレジスタ手段Ｎと、装置から発生する全ての最初のｋ文字がゼロにされるように▲○＋▼アダーアキュムレーターデバイスにおける値にモジュラス値が▲○＋▼加算されるような場合に、「即座に」予測するように動作するデジタル論理検知検出器（ｄｉｇｉｔａｌ ｌｏｇｉｃ ｓｅｎｓｉｎｇ ｄｅｔｅｃｔｏｒ）Ｙ０と、ただ一つの少なくともｋ文字長さの▲○＋▼加算器と、ｋ文字の被乗数を受け入れるように動作する▲○＋▼加算装置（▲○＋▼ ｓｕｍｍａｔｉｏｎ ｄｅｖｉｃｅ）と、順番に被乗数値を▲○＋▼アキュムレーターデバイス内に入れ替え、順番にＢレジスタから乗数値を受け入れるように動作する▲○×▼乗算装置と、第一段階においてｋの最初に発生するゼロ文字を出力させるように動作する乗数と同時に生成した「即座の」予測値とを有し、各々の有効マシンサイクル（ｅｆｆｅｃｔｉｖｅ ｍａｃｈｉｎｅ ｃｙｃｌｅ）で少なくとも一つの指定された被乗数が▲○＋▼アキュムレーターデバイスに▲○＋▼加算される、少なくともｋ文字の入力被乗数のためのモジュラー乗算装置と、全ゼロ文字列の値である第一被乗数、被乗数Ａｉである第二被乗数、モジュラスのＮ０セグメントである第三被乗数のうちの一つ若しくは二つの被乗数からなる、順番に▲○＋▼アキュムレーションデバイス内に入れ替えられる被乗数値と、▲ｌ▼ビットのｋ文字直列入力Ｙ０乗数値を予測するアンティシペーター（ａｎｔｉｃｉｐａｔｏｒ；予測回路）とからなるマイクロエレクトロニクス装置が提供され、該装置は乗数値を乗算装置に順番に入力するように動作でき、前記乗数値は第一段階においてＢオペランドであり、同時に、第二乗数値は最初に発生するゼロを出力させるための「即座の」予測されたｋ文字列であるＹ０からなり、該装置は更に、アキュムレーションデバイス▲○＋▼からなり、該アキュムレーションデバイスは被乗数が該アキュムレーションデバイスへの▲○＋▼であると同時に値を出力するように動作し、第二段階において▲○＋▼アキュムレーションデバイスからの最終のモジュラー▲○×▼乗算の結果を出力するように動作する出力転送機構（ｏｕｔｐｕｔ ｔｒａｎｓｆｅｒ ｍｅｃｈａｎｉｓｍ）からなる。
【００３３】
好ましい実施例によると、▲○＋▼アキュムレーションデバイスへの▲○＋▼加算は、各々の新たな直列にロードされた高位乗数（ｈｉｇｈ ｏｒｄｅｒ ｍｕｌｔｉｐｌｉｅｒ ｃｈａｒａｃｔｅｒ）により始まる。
【００３４】
好ましくは、乗数は、入力されたＢ文字と対応する入力されたＹ０文字の両方がゼロの場合は、▲○＋▼アキュムレーションデバイスへの▲○＋▼加算はされず、入力されたＢ文字が１であり、対応するＹ０がゼロである場合は、Ａｉ被乗数のみが▲○＋▼加算され、入力されたＢ文字がゼロであり、対応するＹ０が１である場合は、モジュラスＮのみが▲○＋▼加算され、入力されたＢ文字と対応するＹ０文字の両方が１である場合は、被乗数Ａｉと共にモジュラスＮが▲○＋▼加算されるように動作する。
【００３５】
好ましくは、該装置は被乗数値Ａｉ，Ｎを二つの指定されたプリロードバッファ（ｐｒｅｒｏａｄ ｂｕｆｆｅｒ）にプリロードし、これらの値を第三プリロードバッファに▲○＋▼加算するように動作して、各々の被乗数値を別々に▲○＋▼加算する必要をなくす。
【００３６】
好ましくは、乗数値は直列単一文字の形式での入力用に調整され、Ｙ０検出装置は一回のクロックで一文字のみ予測するように動作する。
【００３７】
▲○＋▼アキュムレーションデバイスが２を法としてＸＯＲ加算／減算の計算を実行する好まし実施例において、加算成分及び減算成分中の全ての桁上げビットが無視されることにより、計算における桁溢れや更に限定する有益性は排除される。
【００３８】
好ましくは、桁上げ入力はゼロ（▲Ｓ▼＝０を意味する）まで実行不能とされ、概して、多項式ベースの乗算を実行するように動作する。
【００３９】
好ましくは、該装置は桁上げ回路を除くことにより桁上げなしの算術を提供するように動作するので、▲Ｓ▼はＧＦ（２ｑ）において計算する回路方程式（ｃｉｒｃｕｉｔ ｅｑｕａｔｉｏｎ）中の要素に影響するゼロに等しく、▲Ｓ▼は除かれた回路を示し、▲○＋▼で表される全ての加算器及び減算器は２を法とした加算／減算要素の排他的論理和を求める。
【００４０】
好ましい実施例は、動作ユニットから発生した最初のｋ文字セグメントがゼロであって、次のＹ０文字を予測する際に以下の四つの数量によって調整されるように適応する。
ｉ．　Ａｉレジスタの右側文字にＢストリームのＢｄ文字を掛けた▲ｌ▼ビット毎の２▲ｌ▼を法とする▲○×▼乗算の結果の▲ｌ▼ビットのＳｏｕｔビット　Ａ０・▲○×▼ Ｂｄ ｍｏｄ ２▲ｌ▼、
ｉｉ．　▲○＋▼アキュムレーションデバイスから最初に発生する桁上げ文字▲Ｓ▼（ＣＯ０）、
ｉｉｉ．　▲○＋▼アキュムレーションデバイスの右側の発生セル（ｅｍｉｔｔｉｎｇ ｃｅｌｌ）からの次（ｔｈｅ ｓｅｃｏｎｄ）に発生する桁上げ文字からの▲ｌ▼ビットのＳｏｕｔ文字ＳＯ１、
ｉｖ．　Ｎ０モジュラス被乗数レジスタにおける右側文字の負の逆数である▲ｌ▼ビットのＪ０値。
ここで、Ａ０ ▲○×▼ Ｂｄ ｍｏｄ ２▲ｌ▼、▲Ｓ▼（ＣＯ０）、ＳＯ１の値は、共に文字に▲○＋▼加算される文字であり、▲ｌ▼ビットのゼロを発する有効なＹ０ゼロ強制予測文字（Ｙ０ ｚｅｒｏ−ｆｏｒｃｉｎｇ ａｎｔｉｃｉｐａｔｏｒｙ ｃｈａｒａｃｔｅｒ）を出力するために「即座に」Ｊ０文字によって乗算される。
【００４１】
該装置は好ましくは逆モードで実行される多項式ベースのオペランドで乗算を実行するように動作でき、右側のＭＳ文字から左側のＬＳ文字を乗算し、モンゴメリ型寄生関数（Ｍｏｎｔｇｏｍｅｒｙ ｔｙｐｅ ｐａｒａｓｉｔｉｃ ｆｕｎｃｔｉｏｎ）なしでモジュラー縮小された▲○×▼乗算を実行するように動作する。
【００４２】
好ましくは、該装置は、更に直列供給されるプリロードバッファからなり、被乗数値は一以上の記憶装置から即座にプリロードバッファにプリロードされる。
【００４３】
該装置は、好ましくは、Ｙ０検出器が▲○＋▼アキュムレーションデバイスにおいて▲○＋▼加算にモジュラスを▲○＋▼加算する必要性を検出ように動作する時に、最初に発生する出力文字がゼロであるように、▲ｌ▼ビットの▲○＋▼加算器回路を経由して、更なるｎビットのＳレジスタから発生する先の値に乗算ストリームを▲○＋▼加算するように動作し、Ｙ０検出器は、次に順番に加算した文字Ａ０ ▲○×▼ Ｂｄ ｍｏｄ ２、▲Ｓ▼（ＣＯ０）、ＳＯ１、Ｓｄ、▲Ｓ▼（ＣＯＺ）を利用して、▲ｌ▼ビットのＪ０値により即座に▲○×▼乗算される有限体であるように▲○＋▼加算される文字の合成（ｃｏｍｐｏｓｉｔｅ）を検出するように動作するが、ここで、プロセスにおいて用いられる有限体に適するように、▲○＋▼は加算を定義し、▲○×▼は乗算を定義する。
【００４４】
好ましくは、▲ｌ▼＝１で、ハードウェアを追加することなく、Ｊ０は暗黙的に（ｉｍｐｌｉｃｉｔｌｙ）１であり、Ｊ０▲○×▼乗算は暗黙的（ｉｍｐｌｉｃｉｔ）である（ｉｍｐｌｉｃｉｔ）。
【００４５】
好ましくは、コンパレータ（ｃｏｍｐａｒａｔｏｒ）は、最初の右側の発生するｋゼロ文字が無視されるＧＦ（ｐ）において機能している間、▲○×▼モジュラー乗算装置からの有限体出力を検知するように動作し、その出力がモジュラスＮより大きいことにより、モジュラー縮小をを調整するように動作し、前記値は、乗算装置からの出力ストリームの行き先であるメモリレジスタから出力されることにより、より小さな積の値に第二の記憶装置を割り当てる必要がなくなる。
【００４６】
好ましくは、ＧＦ（２ｑ）における▲○×▼モジュラー乗算で、該装置は外部で予め計算された▲ｌ▼ビットより大きなゼロ強制因子なしで乗算するように動作する。
【００４７】
好ましい実施例は、Ａオペランド値又はＢオペランド値のいずれかをゼロに再設定し、部分的な結果値Ｓ０を１に設定することにより、Ｊ０定数を計算するように動作する。
【００４８】
本発明の第二の態様によると、ＡにＢを掛けてモジュラスがＮ（Ａ ｔｉｍｅｓ Ｂ ｍｏｄｕｌｕｓ Ｎ）となる出力ストリームを生成するために、整数Ａ及びＢのインタリーブされた有限体モジュラー乗算を実行するマイクロエレクトロニクス装置であって、モジュラスオペランドレジスタにおける文字の数ｎがｋ文字のセグメント長さよりも大きく、▲○×▼乗算プロセスが複数のインタリーブされた反復で実行され、各々のインタリーブされた反復で▲○×▼乗算装置に入力されるオペランドは、モジュラスＮ、乗数Ｂ、予め計算された部分的な結果Ｓ、被乗数Ａのｋ文字列セグメントからなり、セグメントはＡ０文字列セグメントからＡｍ−１文字列セグメントまで進行し、各々の反復の結果は次の順番の一時的結果Ｓに▲○＋▼加算され、反復結果の最初に発生する文字はゼロであって、各々が夫々乗算値、部分的な結果値、モジュラスを保存するように動作する第一主メモリレジスタＢ、第二主メモリレジスタＳ、第三主メモリレジスタＮと、順番に前記Ｂレジスタからの入力と、各々の反復において最初の右側ゼロを出力させる乗数として有用な「即座の」予測値Ｙ０の入力と、前記Ｎレジスタと、少なくとも、Ａ，Ｂ，Ｎレジスタ資源からの値を順番に受け入れ、続いて被乗数ゼロ強制値Ｙ０をも受け入れるように動作する被乗数並列レジスタとからの入力で、複数の反復▲○×▼乗算プロセスの各々の間、順番に複数の被乗数値の一つ又は二つを▲○＋▼アキュムレーションデバイスに▲○＋▼加算し動作するモジュラー乗算装置と、該装置は、第一段階の間乗数となるように動作し、第二段階の間被乗数となるように動作する二進列（ｂｉｎａｒｙ ｓｔｒｉｎｇ）を生成するように動作するＹ０検出装置を更に利用し、該装置は、第一にゼロ、第二に被乗数Ａのｋ文字列セグメントであるＡｉ、第三にモジュラスＮの最初に発生するｋ文字であるＮ０からなる、第一段階で▲○＋▼アキュムレーションデバイスに入れ替えるのに適した被乗数値を得るように動作し、該装置は更に、次の反復で並列の結果を生成するために、▲○＋▼アキュムレーションデバイスから発する値に▲○＋▼加算される先の反復の結果である一時的結果値Ｓを利用するように動作し、該装置は更に、第一にゼロ、第二に第一段階から残存するオペランドＡｉ、第三に第一段階で予測されたＹ０値からなる乗算の第二段階で▲○＋▼アキュムレーションデバイスに順番に入力される被乗数値を利用するように動作し、第一段階で乗算装置に入力される乗数値は、最初に発生する文字列Ｂ０であり、前記乗算装置は、第二段階でプリロードされた被乗数バッファに生成すると同時に文字毎にロードされる予測されたＹ０文字列からなる第二の▲○×▼乗数値と▲○×▼乗算するのと並行して前記文字列セグメントを乗算するように動作し、第二段階の間、装置に入力されるように動作する二つの乗数値は夫々、Ｂで表されるＢオペランドからの左側ｎ−ｋ文字の値と、Ｎで表されるＮモジュラスの左側ｎ−ｋ文字であり、前記装置は更に、▲○＋▼アキュムレーションデバイスに残存する結果値の左側セグメントを結果レジスタに転送するように最終段階で動作する乗算フラッシュアウト装置（ｍｕｌｔｉｐｌｙｉｎｇ ｆｌｕｓｈ ｏｕｔ ｄｅｖｉｃｅ）からなる。
【００４９】
好ましくは、該装置は、ＭＳ文字からＬＳ文字まで乗算する逆モードにおいて実行される多項式ベースのオペランドで▲○×▼乗算を実行するように動作でき、出願人の米国特許第５７４２５３０号明細書に記載しているように、モンゴメリ型寄生関数なしでモジュラー縮小を実行するように動作する。
【００５０】
本発明の第三の態様によると、被乗数の最初に発生する値、Ｂ乗数の現在の入力、▲○＋▼アキュムレーションデバイスからの桁上げ値、▲○＋▼アキュムレーションデバイスからの▲○＋▼加算値、先に計算された部分的な結果からの現在の値、先の部分的な結果に▲○＋▼アキュムレーションデバイスからの結果を▲○＋▼加算する▲○＋▼加算器からの桁上げ値を用いてＹ０値を予測するように動作する装置が提供される。
【００５１】
好ましくは、該装置は、装置からのｋの最初に発生する値がゼロ文字であることを保証するのに適しており、前記適していることが以下の数量を用いる次の順番のＹ０文字の予測からなる。
ｉ．　Ａｉレジスタの右側文字にＢストリームのＢｄ文字を掛けた▲ｌ▼ビット毎の２▲ｌ▼を法とする▲○×▼乗算の結果の▲ｌ▼ビットのＳｏｕｔビット　Ａ０・Ｂｄ ｍｏｄ ２▲ｌ▼、
ｉｉ．　▲○＋▼アキュムレーションデバイスから最初に発生する桁上げ文字▲Ｓ▼（ＣＯ０）、
ｉｉｉ．　▲○＋▼アキュムレーションデバイスの右側の発生セル（ｅｍｉｔｔｉｎｇ ｃｅｌｌ）からの第二からの▲ｌ▼ビットのＳｏｕｔ文字ＳＯ１、
ｉｖ．　Ｓストリームからの次の順番の文字値Ｓｄ、
ｖ．　Ｚ出力全加算器からの▲ｌ▼ビット桁上げ文字▲Ｓ▼（ＣＯＺ）、
ｖｉ．　Ｎ０モジュラス被乗数レジスタにおける右側文字の負の逆数である▲ｌ▼ビットのＪ０値。
ここで、Ａ０・Ｂｄ ｍｏｄ ２▲ｌ▼、▲Ｓ▼（ＣＯ０）、ＳＯ１、Ｓｄの値は、共に文字に▲○＋▼加算される文字であり、有効なＹ０ゼロ強制予測文字を出力するために「即座に」Ｊ０文字によって▲○×▼乗算される。
【００５２】
更なる実施例において、出力結果をモジュラスＮと比較するように動作する少なくとも一つのセンサをも提供され、その機構は、結果レジスタの出力に第二（ｔｈｅ ｓｅｃｏｎｄ）の減算器を動作させることにより、出力された結果値と限定された合同であるモジュラー縮小された値を出力するように動作し、より小さな結果に第二の記憶装置を割り当てる必要を排除する。
【００５３】
なおも更なる実施例において、最初の値の一つが別のプリロードバッファにロードされるのと並行して、二つの被乗数の▲○＋▼加算である値が、少なくとも一つのｋ文字メモリ手段レジスタでプリロード文字バッファにロードされる。
【００５４】
本発明の第四の態様によると、一連のインタリーブされた▲○×▼モジュラー乗算及び平方を実行するように動作し、三つの自然数乗算演算と同等のものを並行して実行するのに適し、結果がべき算である単一の▲○＋▼アキュムレーションデバイス及び予測ゼロ強制機構（ａｎｔｉｃｉｐａｔｉｎｇ ｚｅｒｏ ｆｏｒｃｉｎｇ ｍｅｃｈａｎｉｓｍ）を有する装置が提供される。
【００５５】
一つの実施例において、次の順番に用いられる被乗数は、即座にプリロードレジスタバッファ（ｐｒｅｌｏａｄ ｒｅｇｉｓｔｅｒ ｂｕｆｆｅｒ）にプリロードされる。
【００５６】
更なる実施例において、装置のバッファ及びレジスタは外部メモリー資源からの値をロードされるように動作し、前記バッファ及びレジスタは計算の間に外部メモリー資源にアンロードされるように動作するので、オペランドの最大サイズが利用できるメモリー手段に依存する。
【００５７】
なおも更なる実施例において、メモリーレジスタ手段をも提供され、前記メモリー手段は、概して、直列単一文字入力／直列単一文字出力、並列少なくともｋ文字入力／並列少なくともｋ文字出力、直列単一文字入力／並列少なくともｋ文字出力、並列少なくともｋ文字入力／直列単一文字出力である。
【００５８】
好ましくは、該装置は、乗算型反復の最終段階の間、乗数入力が桁上げ保存▲○＋▼累算メモリーの左側セグメントをフラッシュアウトするように動作するゼロ文字であることを提供するように動作できる。
【００５９】
好ましくは、該装置は、次の順番の被乗数を、必要とされるよりも前に、即座にプリロードメモリーバッファにプリロードするように動作できる。
【００６０】
好ましくは、該装置は、被乗数値を中央記憶装置から即座にプリロードバッファにプリロードするように動作できる。
【００６１】
同装置は、好ましくはＡ，Ｂの両方をゼロに再設定し、Ｓ０＝１に設定することにより、モジュラスの右側ｋ文字セグメントに関するｋ文字モンゴメリ定数Ｊ０を計算するように動作でき、続いてｋビット乗算を実行する。
結果はＹ０レジスタに存在する。
【００６２】
モンゴメリ型演算を利用するモジュラー乗算シーケンス
ｋ文字桁上げ保存加算器ＣＳＡは、多項式体及び素数フィールドの両方における直列／並列のスーパースカラモジュラー乗算の基礎である。
多項式ＧＦ（２ｑ）ベースの計算は、好ましくは全ての桁上げ機構のスイッチを切られた状態で実行される。
【００６３】
直並列スーパースカラモンゴメリ乗算器は三段階のモンゴメリモジュラー積を計算するが、その一つの好ましい実施例において、最終段階はＣＳＡの桁上げにより左側のｋ文字セグメント全体の単一クロックのダンプであってもよく（ＭＳは通常の乗算で、ＬＳは逆モードの多項式計算）、よりコンパクトな実施例では、最終段階はＣＳＡの内容のｋ有効クロック直列フラッシュアウト（ｋ ｅｆｆｅｃｔｉｖｅ ｃｌｏｃｋ ｓｅｒｉａｌ ｆｌｕｓｈ ｏｕｔ）であってもよい。
【００６４】
先のＰ２の開示において、Ｙ０因子はビット毎に計算されるので、Ｊ０の右側のビット、即ち定義では一つのビットのみが重要であって、モジュラスの右側ビットの関数である。
この拡張された装置において、装置は文字直列（ｃｈａｒａｃｔｅｒ ｓｅｒｉａｌ）であり、▲ｌ▼ビット文字Ｙ０は各々のクロックサイクルで生成される。
先のＰ１の開示において、Ｙ０は累算された結果に必要な回数だけモジュラス値を加算する第一段階のゼロ強制関数であるので、関連した解が合同であってｍｋ＋１文字より決して長くなく、最初に右側で発生した文字は全てゼロであった。
ＱＮ≡０ ｍｏｄ ＮなのでＸ＋ＱＮ≡Ｘである。
【００６５】
モジュラー乗算シーケンス
計算を開始する前に、我々は装置に過去の一時的又はランダムな値がなく、オペランドＮ，Ｂ及び少なくとも最初のＡのセグメント値が装置のレジスタにおいて利用できると仮定する。
Ｓ０＝０で初めの部分積は概してゼロである。
典型的には、モジュラー演算は、概して三つの明確な段階において二以上のｋ文字セグメントからなるオペランドで実行される。
ｍセグメントのモジュラスがある通常の全乗算では、概して、ｍスーパースカラ乗算インタリーブされた反復（ｍ ｓｕｐｅｒｓｃａｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ ｉｎｔｅｒｌｅａｖｅｄ ｉｔｅｒａｔｉｏｎｓ）があり、被乗数の各々のセグメントが、典型的にはＢである全ての乗数によって掛けられる。
【００６６】
各々のインタリーブされたスーパースカラ乗算のｉ＝０番目のセグメントにおける第一段階のプロセスは、一般的なスーパースカラ乗算累算間の相互作用である。
即ち、Ｓｉ ▲○＋▼ Ａｉ・Ｂ０ ▲○＋▼ Ｙ０・Ｎ０
（Ｂ０，Ｙ０は直列的に文字毎にオペランドの最初のセグメントから乗算器に供給され、Ａｉ，Ｎ０は並列的な単一のスライスのオペランドであり、Ｓｉは先の反復／計算からの部分積である。０番目の最初の反復ではＳｉ＝０。）
【００６７】
第一段階のプロセスは、先の結果の右側セグメントへの二つのスーパースカラ積の▲○＋▼加算を実行する。
ゼロのｋ文字列は、乗算装置から発生して、無視されるが、最初のセグメントの部分積は装置バッファに存在し、第二段階の結果に加算される。
【００６８】
第一段階の結果は典型的にはＲからなり、ＣＳＡの内容が全ゼロの直列出力された右側セグメントに連結される。（ＧＦ（ｐ）計算において、Ｒへの更なるＬＳ桁上げビットがある。）
【００６９】
第二段階のプロセスは、一般的なスーパースカラ乗算累積間相互作用である。
即ち、Ｒ ▲○＋▼ Ｓｉ ▲○＋▼ Ａｉ・Ｂ ▲○＋▼ Ｙ０・Ｎ
（下線を引いた変数、例えばＢはオペランドの残存する左側の値であることに留意する。それは、典型的には一つ以上のセグメント、即ち、ｍ−１セグメントである。Ｂ，Ｎは直列的に文字毎に乗算器に供給され、第一段階から残存するＡｉと、第一段階において乗数であり次の反復において被乗数となるように第一段階においてマシンへロードされるＹ０とは並列なオペランドである。）
【００７０】
概してｍ−１回の反復からなる第二段階の終わりに、Ｓｉの左側セグメントが転送可能な状態でＣＳＡ内に残存し、右側のスライス（ｋ文字セグメント）は、装置から典型的にはＳレジスタに発せられる。
素数フィールドにおける乗算が、従来の桁上げ保存加算法で実行されることに留意すべきである。
ＧＦ（２ｑ）の逆フォーマットモードにおける乗算は、最上位文字から最下位文字まで進行した。
モジュラス値がアキュムレーターに「加算され」なければならない時、Ｙ０関数が予測した。
装置において使用できない桁上げビットを除いて、機械的処理は二つの記数法で典型的には同一である。
【００７１】
我々は、有限体におけるゼロ強制ベクトルのＹ０ｊ文字を誘導するために利用される方法を開示する。
【００７２】
Ｊ０ｊ≡−Ｎ００−１ ｍｏｄ ２▲ｌ▼を計算する。
モジュラスに対し互いに素である全ての自然数は、両数値体において逆数を有する。
Ｎ００は奇数であるので、２の因数を有しない。
ｍｏｄ ２▲ｌ▼の全ての因数は２であるので、最下位１を有する数及び唯一の因数が２であるモジュラスは、互いに素であり、Ｊ０ｊは常に存在する。
正式には、奇数Ｎ００及び２▲ｌ▼について、ｇｃｄ（Ｎ００，２▲ｌ▼）＝１となる。
【００７３】
関数のこの単一文字は、ランダムロジック、単純回路、又は単純なルックアップテーブル（ｌｏｏｋ ｕｐ ｔａｂｌｅ）で配線実装され得る。
ルックアップテーブルにおいて誘導されなければならない２ｋ−１の異なる値がある。
逆モードフォーマットにおいて、多項式のモジュラスは、右詰めで、名目上奇数でなければならない。
典型的な指数関数（ｅｘｐｏｎｅｎｔｉａｔｉｏｎａｌ ｆｕｎｃｔｉｏｎ；べき算関数）において、モジュラスビットの右側ビットは一つであり、名目上奇数であり、２ｋを法とする奇数の逆数は常に奇数である。
【００７４】
▲ｌ▼＝１である場合、Ｊ００乗数は明らかに１に等しく、計算される必要はない。
第一段階の間、Ｙ０関数によって出される文字出力の結果は常に０であるので、ＳｕｐｅｒＭＡＰのｊ番目の文字出力Ｚｉｊは、０＝（２▲ｌ▼Ｒ ▲○＋▼ Ｓｉｊ ▲○＋▼ Ａｉ０・Ｂ０ｊ ▲○＋▼ Ｙ０ｊ・Ｎ００） ｍｏｄ ２▲ｌ▼＝Ｚｉｊとなり、従って、（Ｒ ▲○＋▼ Ｓｉｊ ▲○＋▼ Ａｉ０・Ｂ０ｊ）≡−Ｙ０ｊ・Ｎ００であり、Ｙ０ｊ≡−Ｎ００−１（Ｒ ▲○＋▼ Ｓｉｊ ▲○＋▼ Ａｉ０・Ｂ０ｊ） ｍｏｄ ｒである。
【００７５】
上記の式から、Ｊ００が好ましくは両記数法でモジュラスの右側のｋ文字のモジュラー逆数の負の値であることが分かるが、２を法とする演算において、正及び負の値は同じであることに留意すべきである。
【００７６】
Ｒは、図２における最終直列加算器４６０からの桁上げビットに加算されるＣＳＡに残存する値の総和である。
Ｓｉｊは、ｉ番目の反復での部分積のｊ番目のビットである。
Ａｉ０は、Ａのｉ番目のスライスの右側文字（ＧＦ（ｐ）におけるＬＳ）である。
Ｂ０ｊは、Ｂのｊ番目の文字である。
Ｂ０は、モンゴメリ乗算の全反復の間の定数（乗数）である。
Ｙ０は、各々の（ｉ番目の）反復で生成されるｋ文字ベクトルである。
Ｙ０ｊは、反復の第一段階のｊ番目のクロックで生成されるｊ番目の文字である。
Ｎは、ｍスライスされた（ｍ ｓｌｉｃｅｄ）モジュラスである。
Ｎ０は、モジュラスの右側スライスである。
Ｎ００は、Ｎ０の右側文字である。
【００７７】
両体についてスーパースカラモジュラー乗算法の公式化（Ｆｏｒｍａｌｉｚｉｎｇ）
Ｓ０＝０
ｉ＝０〜ｍ−１（インタリーブ反復）で、
（各々のインタリーブの）第一段階
Ｒ＝０
ｊ＝０〜ｋ−１（第一段階の各々の文字）で
Ｙ０ｊ＝（Ｊ００（Ｒ ▲○＋▼ Ｓ０ｊ ▲○＋▼ Ａｉ０ ▲○×▼ Ｂ０ｊ）） ｍｏｄ ２▲ｌ▼
Ｚｉｊ＝（Ｒ ▲○＋▼ Ｓｉｊ ▲○＋▼ Ａｉ０ ▲○×▼ Ｂ０ｊ ▲○＋▼ Ｙ０ｊ ▲○×▼ Ｎ０） ｍｏｄ ２▲ｌ▼
Ｒ＝［（２▲ｌ▼Ｒ ▲○＋▼ Ｓｉｊ ▲○＋▼ Ａｉ０ ▲○×▼ Ｂ０ｊ ▲○＋▼ Ｙ０ｊ ▲○×▼ Ｎ０）］／２▲ｌ▼
【００７８】
ｋ有効クロックサイクルの後、Ｚストリームの最初のセグメントは全てゼロであって無視され、関連したＹ０（ｋ文字ベクトル）は次の段階において被乗数となるように用意され、加算されたＲの値は次の段階において利用される。
【００７９】
第二段階
ｊ＝ｋ〜ｎ−１で、
Ｚｉｊ＝（Ｒ ▲○＋▼ Ｓｉｊ ▲○＋▼ Ａｉ０ ▲○×▼ Ｂ０ｊ ▲○＋▼ Ｙ０ｊ ▲○×▼ Ｎ０ｊ） ｍｏｄ ２▲ｌ▼
Ｒ＝［２▲ｌ▼Ｒ ▲○＋▼ Ｓｉｊ ▲○＋▼ Ａｉ０・Ｂ０ｊ ▲○＋▼ Ｙ０ｊ・Ｎ０ｊ］／２▲ｌ▼
【００８０】
文字ベースの直並列乗算器での上記アルゴリズムのインプリメンテーションは、上記のプロトコルの単純な拡張である。
（Ｑｕｏｔｉｅｎｔ（商）（ｘ，ｙ）は、剰余のない整数の除算関数である。例えば、ｘ＝１０１０１ｂ，ｙ＝１００００ｂである場合は、Ｑｕｏｔｉｅｎｔ（ｘ，ｙ）＝１）。
【００８１】
Ｓ０＝０
ｉ＝０〜ｍ−１（インタリーブのループ）で、
第一段階
ｊ＝０〜ｋ−１で、
Ｙ０ｊ＝（Ｊ００・Ｓｉ０ ▲○＋▼ Ａｉ０ ▲○×▼ Ｂ０ｊ ▲○＋▼ ▲Ｓ▼・Ｃａｒｒｙ０ ▲○＋▼ Ｓｕｍ１ ▲○＋▼ Ｑｕｏｔｉｅｎｔ（Ｓｉ０ ▲○＋▼ Ｓｕｍ０， ｒ））） ｍｏｄ ｒ
ｔ＝０〜ｋ−１（一つのクロックパルスを有する全ループ）で、
Ｓｕｍｔ＝（Ｓｕｍｔ＋１ ▲○＋▼ ▲Ｓ▼・Ｃａｒｒｙｔ ▲○＋▼Ａｉｔ ▲○×▼ Ｂ０ｊ ▲○＋▼ Ｙ０ｊ ▲○×▼ Ｎ０ｔ） ｍｏｄ ｒ
Ｃａｒｒｙｔ＝（Ｑｕｏｔｉｅｎｔ（（Ｓｕｍｔ＋１ ▲○＋▼ Ｃａｒｒｙｔ ▲○＋▼ Ａｉｔ ▲○×▼ Ｂ０ｊ ▲○＋▼ Ｙ０ｊ ▲○×▼ Ｎ０ｔ）， ｒ）
（この段階の乗算器装置の出力は、『０』である。）
【００８２】
第二段階
主要部
Ｃａｒｒｙａ＝０
ｊ＝ｋ〜ｎ−１，ｔ＝０〜ｋ−１（一つのクロックパルスを有する全ループ）で、
Ｓｕｍｔ＝（Ｓｕｍｔ＋１ ▲○＋▼ ▲Ｓ▼・Ｃａｒｒｙｔ ▲○＋▼ Ａｉｔ ▲○×▼ Ｂｊ ▲○＋▼ Ｙ０ｔ ▲○×▼ Ｎｊ） ｍｏｄ ｒ
Ｃａｒｒｙｔ＝Ｑｕｏｔｉｅｎｔ（（Ｓｕｍｔ＋１ ▲○＋▼ Ｃａｒｒｙｔ ▲○＋▼ Ａｉｔ ▲○×▼ Ｂｊ ▲○＋▼ Ｙ０ｔ ▲○×▼ Ｎｊ）， ｒ）
Ｓｉ，ｊ−ｋ＝（Ｓｉ，ｊ−２ｋ ▲○＋▼ Ｓｕｍ０ ▲○＋▼ ▲Ｓ▼・Ｃａｒｒｙａ） ｍｏｄ ｒ
Ｃａｒｒｙａ＝Ｑｕｏｔｉｅｎｔ（（Ｓｉ，ｊ−２ｋ ▲○＋▼ Ｓｕｍ０ ▲○＋▼ Ｃａｒｒｙａ）， ｒ）
乗算器のフラッシング
ｊ＝ｎ〜（ｎ＋ｋ−１），ｔ＝０〜ｋ−１（一つのクロックパルスを有する全ループ）で、
Ｓｕｍｔ＝（Ｓｕｍｔ＋１ ▲○＋▼ ▲Ｓ▼・Ｃａｒｒｙｔ） ｍｏｄ ｒ
Ｃａｒｒｙｔ＝Ｑｕｏｔｉｅｎｔ（（Ｓｕｍｔ＋１ ▲○＋▼ Ｃａｒｒｙｔ）， ｒ）
Ｓｉ，ｊ−ｋ＝（Ｓｉ，ｊ−２ｋ ▲○＋▼ Ｓｕｍ０ ▲○＋▼ ▲Ｓ▼・Ｃａｒｒｙａ） ｍｏｄ ｒ
Ｃａｒｒｙａ＝Ｑｕｏｔｉｅｎｔ（（Ｓｉ，ｊ−２ｋ ▲○＋▼ Ｓｕｍ０ ▲○＋▼ Ｃａｒｒｙａ）， ｒ）
【００８３】
ＧＦ（ｐ） 体における▲ｌ▼＝１の特定の場合の例での正式な説明については、Ｐ１を参照する。
【００８４】
上記は、ＡにＢを掛けてモジュラスがＮ（Ａ ｔｉｍｅｓ Ｂ ｍｏｄｕｌｕｓ Ｎ）となる出力ストリームを生成するために、整数Ａ及びＢのインタリーブされた有限体モジュラー乗算を実行するマイクロエレクトロニクスの方法及び装置であって、ｎがモジュラスオペランドレジスタにおける文字であり、ｋ文字のセグメント長さよりも大きく、▲○×▼乗算プロセスが複数の反復で実行され、各々のインタリーブされた反復で▲○×▼乗算装置に入力されるオペランドは、モジュラスＮ、乗数Ｂ、予め計算された部分的な結果Ｓ、被乗数Ａのｋ文字列セグメントからなり、セグメントはＡ０文字列セグメントからＡｍ−１文字列セグメントまで進行し、各々の反復の結果は次の順番の一時的結果Ｓに▲○＋▼加算され、反復結果の最初に発生する文字はゼロであるマイクロエレクトロニクスの方法及び装置を説明している。
【００８５】
典型的には、乗算装置に供給される四つの直列▲ｌ▼ビット文字レジスタ、第一にＢ、第二にＳ、第三にＮ、好ましくはＡがあり、乗算器に効率的にロードされるように構成される。
【００８６】
典型的には、ＭＡＰの内部レジスタに収容されない長いオペランドでの計算のために、ＣＰＵは、そのアクセス可能なメモリーからオペランドをロードすることができる。
【００８７】
典型的には、これらの主メモリレジスタは、夫々、乗数値、部分的な結果値、モジュラスＮを保存するように動作するオペランドを保存し出力する。
モジュラー乗算装置は、反復▲○×▼乗算プロセスの間、順番に複数の被乗数値の一つ又は二つを▲○＋▼アキュムレーションデバイスに▲○＋▼加算し、順番に前記Ｂレジスタの第一の値からの入力と、各々の反復において最初の右側ゼロ文字を出力させる乗数としての「即座の」予測値Ｙ０の第二の値からの入力と、前記モジュラスＮレジスタの第三の値からの入力とを乗数として受け入れるように動作する。
【００８８】
被乗数並列レジスタは、Ａ，Ｂ，Ｎレジスタ資源からの値を順番に受け入れ、続いて被乗数ゼロ強制値Ｙ０をも受け入れるように動作する。
【００８９】
ゼロ強制Ｙ０検出装置は、演算の第一段階の間、乗数となるように動作し、各々の反復乗算の第二段階の間、被乗数となるように動作する二進列を生成するように動作する。
【００９０】
第一段階で▲○＋▼アキュムレーションデバイスに入れ替えられる被乗数値は、第一のゼロ値、被乗数Ａのｋ文字列セグメントである第二の値Ａｉ、モジュラスＮの最初に発生するｋ文字である第三の値Ｎ０からなり、四つの値のうちの一つになり得る。
図６のように、四番目のプリロードバッファがある場合は、Ｎ０値は概して、乗算の開始時に入れ替えられる。
そして、Ａのｋ文字スライスが入力される際は、Ａｉ値はＮ０値に直列的に加算され、四番目のバッファに保存される。
【００９１】
概して単一のｋ文字モジュラスでの計算の場合、Ｓレジスタ若しくは一時的結果値Ｓの必要性はない。
オペランドが２ｋ文字又はそれより長い場合、Ａｉスライスを進行させつつ、処理が反復的でなければならない。
平方演算で、Ｂのスライスは、概してＢストリームから即座に回収され（ｂｅ ｓｎａｒｅｄ）、Ａｉプリロードバッファにプリロードされる。
【００９２】
乗算操作の第一の反復で、一時的結果はゼロである。
【００９３】
先の反復からのその後の一時的結果は、次の順番の反復で部分的な結果を生成するために、▲○＋▼アキュムレーションデバイスから発生する値に▲○＋▼加算されるように動作する。
【００９４】
第二段階で▲○＋▼アキュムレーションデバイスに順番に入力される被乗数値は、第一に擬レジスタ値（ｐｓｅｕｄｏ ｒｅｇｉｓｔｅｒ ｖａｌｕｅ）であるゼロ、第二に第一段階から残存するオペランドＡｉ、第三にＮモジュラスの残存する文字を乗算し続けるように動作する第一段階で予測されたＹ０値である。
【００９５】
第一段階で乗算装置に入力される乗数値は、最初に発生する文字列Ｂ０であり、最初に発生するＢオペランドの文字列セグメントであり、第二段階でプリロードされた被乗数バッファに生成すると同時に文字毎にロードされる予測されたＹ０文字列からなる第二の▲○×▼乗数値と▲○×▼乗算するのと並行して乗算する。
【００９６】
第二段階の間、装置に入力される二つの乗数値は夫々、Ｂで表されるＢオペランドからの左側ｎ−ｋ文字の値と、Ｎで表されるＮモジュラスの左側ｎ−ｋ文字である。
【００９７】
第三段階は、▲○＋▼アキュムレーションデバイスに残存する結果値の左側セグメントを転送するように動作する装置のフラッシュアウトである。
これは、乗数入力において供給されるゼロ文字によってなされる単一クロックのデータダンプか、又はまたは単純な直列アンロードのいずれかである。
【００９８】
ダンプが並列のダンプである場合、その結果（ｒｅｓｕｌｔ）がモジュラスによって更なる縮小を必要とするか否かを決定するために比較する手段がある。
【００９９】
本発明におけるより革新的な拡張のうちの一つは、ＧＦ（２ｑ）における逆モード乗算である。
この演算において加算器セル間の相互作用がないため、積のＭＳ側から始めて乗算及び縮小を実行することができることによって、従来のモンゴメリ乗算における右側シフトを実行することに相当する無視されたゼロにより発生する厄介な寄生（ｐａｒａｓｉｔｅ）なしでモジュラー縮小された解である積を有する。
【０１００】
自動ゼロ強制を可能にする第二の革新点は、ただ一つのビットが一度に予測される装置を記載する特許出願Ｐ２のＹ０関数の拡張である。
そこでＪ００ビットは、単一ビットの排他的論理和を求められた値に掛けられるだけであった。
奇数の逆数及びその負の値は、奇数を発生させる。
これは、▲ｌ▼＝１でのＪ０値を計算するために、ルックアップテーブル又はランダム論理回路を実装して保存した。
Ｊ０は、近似していない記数法においては異なる数量であることに留意すべきである。
我々は、両方の関連した数値体で、この拡張において、Ｙ０値がどのように誘導され得るかについて示した。
【０１０１】
以下の記載は、被乗数の最初に発生する値、Ｂ乗数の現在の入力、▲○＋▼アキュムレーションデバイスからの桁上げ値、▲○＋▼アキュムレーションデバイスからの▲○＋▼加算値、先に計算された部分的な結果からの現在の値、先の部分的な結果に▲○＋▼アキュムレーションデバイスからの結果を▲○＋▼加算する▲○＋▼加算器からの桁上げ値を用いてＹ０値を予測するように動作する回路要素を記載する。
【０１０２】
別の表現をすれば、ゼロ強制関数を制御するように動作する六つの値は、
ｉ．　Ａｉレジスタの右側文字にＢストリームのＢｄ文字を掛けた▲ｌ▼ビット毎の２▲ｌ▼を法とする▲○×▼乗算の結果の▲ｌ▼ビットのＳｏｕｔビット　Ａ０ ▲○×▼ Ｂｄ ｍｏｄ ２▲ｌ▼、
ｉｉ．　▲○＋▼アキュムレーションデバイスから最初に発生する桁上げ文字▲Ｓ▼（ＣＯ０）、
ｉｉｉ．　▲○＋▼アキュムレーションデバイスの右側の発生セルからの第二からの▲ｌ▼ビットのＳｏｕｔ文字ＳＯ１、
ｉｖ．　Ｓストリームからの次の順番の文字値Ｓｄ、
ｖ．　Ｚ出力全加算器からの▲ｌ▼ビット桁上げ文字▲Ｓ▼（ＣＯＺ）、
ｖｉ．　Ｎ０モジュラス被乗数レジスタにおける右側文字の負の逆数である▲ｌ▼ビットのＪ０値、である。
ここでＡ０ ▲○×▼ Ｂｄ ｍｏｄ ２▲ｌ▼、▲Ｓ▼（ＣＯ０）、ＳＯ１、Ｓｄの値は、▲ｌ▼ビットのゼロ文字列を発生させるための共に文字に▲○＋▼加算される文字であり、有効なＹ０ゼロ強制予測文字を出力するために「即座に」Ｊ０文字によって▲○×▼乗算される。
Ｐ１の記載にあるように、出力がモジュラー縮小されなければならないか否かを決定するためには、センサが出力結果をモジュラスＮと比較するように動作し、その機構は、結果レジスタの出力に第二の減算器を動作させることにより、出力された結果値と限定された合同であるモジュラー縮小された値を出力するように動作し、より小さな結果に第二の記憶装置を割り当てる必要を排除する。
【０１０３】
乗算を実行するように構成される単独の▲○＋▼アキュムレーションデバイス及び予測ゼロ強制機構は共に、一連のインタリーブされた▲○×▼モジュラー乗算及び平方を実行するように動作する。
全装置は、従来のモンゴメリ法における三つの整数乗算と同等のものを実行し、Ｊ０はＢ０▲○×▼Ａｉ及びＳｉの最初のｋ文字加算を乗算し、最後にＮを乗算すべくＹ０を予測するｋ文字装置である。
【０１０４】
ＳｕｐｅｒＭＡＰが乗算の最後の反復を計算している間、次の乗算の第一のスライスは、即座にプリロードレジスタバッファ手段にプリロードされ得る。
この値は、図１若しくは図５のレジスタバンクにおけるレジスタセグメントの一つに残存する先の乗算の結果か、又は被乗数のスライスである。
【０１０５】
二つの被乗数の▲○＋▼加算であるプリロードされた値は、ＧＦ（２ｑ）計算でのみ、ｋ文字レジスタに▲○＋▼加算される。
ＧＦ（ｐ）計算においては、更なる桁上げビットを備えなければならない。
【０１０６】
特に非常に長いモジュラスでは、ＳｕｐｅｒＭＡＰに隣接したバッファ及びレジスタは、概して不十分なメモリ資源を有する。
プリロードバッファにオペランドを直接ロードする手段が提供され、ＣＰＵのメモリマップ（ｍｅｍｏｒｙ ｍａｐ）にオペランドを保存するように動作する。
逆フォーマット乗算では、ＣＰＵから入力された語（ｗｏｒｄ）のビットオーダーは、概してデータ入出力装置において逆にされる。
【０１０７】
図面において、太線は、ｋ文字（ｋ▲ｌ▼ビット）の広い並列バスラインを示す。
より薄い隣接した信号ラインは、▲ｌ▼ビットの広いラインを表す。
ほとんどの制御ラインは表示されていないが、ここに含まれるものは、概して手順を理解するのに必要であり、概して一点鎖線で示されている。
【０１０８】
（発明を実施するための最良な形態）
図面において、太線は、ｋ文字（ｋ▲ｌ▼ビット）の広い並列バスラインを示す。
より薄い隣接した接続信号ラインは、▲ｌ▼ビットの広いラインを表す。
概して、制御ラインは表示されていないが、手順を理解するのに好ましくは必要なものは、概して一点鎖線で示されている。
【０１０９】
図１，２は共に、本発明の好ましい実施例によって構成され作動する直並列算術論理演算ユニット（ＡＬＵ）のブロック略図である。
図１，２の装置は、好ましくは以下の部品を含む。
単一マルチプレクサ（ｓｉｎｇｌｅ ｍｕｌｔｉｐｌｅｘｅｒ）−一つの信号又は文字のストリームを多数の信号入力から選択し、この選択された信号を単一の出力に当てる制御切換素子。
マルチプレクサは、Ｍ１〜１３の符号を付され、より大きな素子が本来備える素子である。
【０１１０】
マルチプレクサ及びプリアッダー（ｐｒｅ−ａｄｄｅｒ；予加算器）３９０は、ｋ▲ｌ▼＋１のマルチプレクサの配列であり、四つのｋ若しくはｋ＋１文字入力のいずれがＣＳＡ（ｃａｒｒｙ ｓａｖｅ ａｃｃｕｍｕｌａｔｏｒ；桁上げ保存アキュムレーター）４１０に加えられるかを選択する。
【０１１１】
Ｂ（７０，８０）、ＳＡ（１３０）、ＳＢ（１８０）、Ｎ（２００，２１０）は、好ましい実施例における四つの主要な直列レジスタである。
ＳＡは、概念的に及び実際に冗長であるが、非常に長い番号の計算をかなり速めることができ、特にモジュラスの長さが２・ｋ・ｍ文字長さである場合には、揮発性記憶装置で保存する。
【０１１２】
直列加算器及び直列減算器は、二つの直列文字入力及び一つの直列文字出力を有し、二つの長い文字列を加算若しくは減算する論理素子である。
部品９０及び５００は減算器であり、３３０及び４６０は直列加算器である。入力から出力への伝搬時間は、非常に短い。
直列減算器９０及び５００は概して、Ｂ＊がＮ以上である場合、Ｂ＊をＢに減少させ、及び／又は、Ｓ＊がＮ以上である場合、Ｓ＊をＳに減少させる。
直列減算器４８０は、Ｂ＊がＮ以上であるか否かを検知するコンパレータ部品の一部として利用される。
全加算器３３０は、二つの文字ストリームを加算し、ロードバッファ（ｌｏａｄ ｂｕｆｆｅｒ）３４０に、ロードバッファ２９０及び３２０の値の合計と同じ値を供給する。
【０１１３】
高速ローダ及びアンローダ（１０，２０及び３０，４０）は夫々、ＣＰＵ制御装置からのデータフローを速める装置である。
これらの装置は概して、他の直接メモリアクセス部品の必要性を排除する。
符号２０，４０は、逆フォーマット（ｒｅｖｅｒｓｅ ｆｏｒｍａｔ）のＧＦ（２ｑ）の乗算のためのデータ語を逆にする必要がある際に、データ語を逆にするためのものである。
【０１１４】
本算術論理演算ユニット装置は直列供給されるシストリックプロセッサ（ｓｙｓｔｏｌｉｃ ｐｒｏｃｅｓｓｏｒ）であるので、データ入力（Ｄａｔａ ｉｎ）５０はパラレルイン−シリアルアウト方式の装置であり、データが並列に供給され、直列に処理される。
【０１１５】
データ出力（Ｄａｔａ ｏｕｔ）６０は、結果をコプロセッサから出力するためにシリアルイン−パラレルアウト方式の装置である。
商生成器（ｑｕｏｔｉｅｎｔ ｇｅｎｅｒａｔｏｒ）は、図２のその部分であるが、それは分割機構の各々の反復で商文字を生成する。
【０１１６】
Ｂｄ上のフラッシュ信号（ｆｌｕｓｈ ｓｉｇｎａｌ）２４０、Ｓ＊ｄ上のフラッシュ信号２５０、Ｎｄ上のフラッシュ信号２６０は、直前のｋ＋１文字が、確実にＣＳＡをフラッシュアウトできる（ｆｌｕｓｈ ｏｕｔ）ような信号である。
第二の実施例は、第二段階の終わりにＲデータを一致させ、ＣＳＡをフラッシュアウトするために単一のパラレルデータのダンプ（ｄｕｍｐ）を行う。
【０１１７】
ロードバッファＲ１，Ｒ２，Ｒ３（２９０，３２０，３４０）は、三つの可能な０以上の被乗数の組合せを受信するのに適したシリアルイン−パラレルアウト方式の送りレジスタ（ｓｈｉｆｔ ｒｅｇｉｓｔｅｒ；シフトレジスタ）である。
【０１１８】
ラッチＬ１，Ｌ２，Ｌ３（３６０，３７０，３８０）は、ロードバッファからの出力を受信し、それにより、次段階のデータが好ましくはＬ１，Ｌ２，Ｌ３にラッチされる前に、ロードバッファがこのデータを処理することが時間的に可能となる。
ラッチＬ０は概して３９０への「仮想」の一定の全ゼロの入力であり、概してラッチされた論理（ｌａｔｃｈｅｄ ｌｏｇｉｃ）では実行されない。
【０１１９】
Ｙ０検知（Ｙ０ ｓｅｎｓｅ）４３０は論理回路であり、ＬＳ（ｌｅａｓｔ ｓｉｇｎｉｆｉｃａｎｔ；最下位）ゼロのｋ文字列が▲○×▼乗算のＺで終了するために、モジュラスが累算される回数を決定する。
【０１２０】
一文字遅延装置（Ｏｎｅ ｃｈａｒａｃｔｅｒ ｄｅｌａｙ ｄｅｖｉｃｅ）１００，２２０，２３０は、計算の同期のために図１のデータ作成装置と図１のデータ処理装置との間に収容されるように、夫々のデータストリームに挿入される。
【０１２１】
ｋ文字遅延送りレジスタ４７０はＮを同期させ、減算器は、Ｎより大きな比較のために右側の出力のゼロ文字列を無視した後の結果からＮを減算する。
【０１２２】
ＣＳＡは、従来のような直列／並列乗算器の入力にラッチされるような単一の値の代わりに、三つの異なるゼロより大きな値が加算されるということを除いては、直列／並列乗算器とほとんど同一である。
多項式ベースの計算において利用される場合には、「全ての桁上げに依存する」関数は使用禁止となる。
【０１２３】
最後の桁上げ挿入（Ｉｎｓｅｒｔ Ｌａｓｔ Ｃａｒｒｙ）４４０は、Ｓレジスタがｍ・ｋ文字長さしかないので、Ｓストリームの（ｍ・ｋ・▲ｌ▼＋１）番目のビットを挿入するために利用される。
【０１２４】
借り／桁溢れ検出（ｂｏｒｒｏｗ／ｏｖｅｒｆｌｏｗ ｄｅｔｅｃｔ）４９０は、概して、結果が（Ｎからの）モジュラス以上であるか、又はＧＦ（ｐ）計算内であるかを検出する。
多項式ベースの計算において、第一の重要な結果のビットが一つである場合、桁溢れが検出される。
【０１２５】
制御機構は記載されていないが、好ましくは、ＧＦ（ｐ）及びＧＦ（２ｑ）の両方のシストリック・データ・フロー用に設定されるスイッチを有する特殊関数のための有限状態機械を有する一組のカスケード方式の計数装置であると理解される。
【０１２６】
数の素体及び合成素体（ｃｏｍｐｏｓｉｔｅ ｐｒｉｍｅ ｆｉｅｌｄ）におけるモジュラー型乗算のため、我々はＡ及びＢを被乗数及び乗数と定義し、ＮをＡ若しくはＢよりも概して大きなモジュラスと定義する。
Ｎはモジュラスの値が保存されるレジスタをも意味する。
Ｎは、若干の場合において、Ａより小さい。
我々は、Ａ，Ｂ，Ｎをｍ・ｋ＝ｎの文字長さのオペランドとして定義する。
各々のｋの文字群（ｋ ｃｈａｒａｃｔｅｒ ｇｒｏｕｐ）はセグメント（ｓｅｇｍｅｎｔ）と呼ばれ、その群のサイズは乗算装置のサイズによって定められる。
Ａ，Ｂ，Ｎは各々ｍ文字長さである。
順次手順を説明していく際の平易のために、Ａ，Ｂ，Ｎは５１２ビットの長さ（ｎ＝５１２）と仮定し、乗数の経済的な長さ及び簡単なＣＰＵのデータ操作速度を考慮して、ｋは６４文字長さと仮定し、ｍ＝８がオペランドにおけるセグメントの数及び５１２ビットのオペランドでの平方若しくは乗算ループにおける反復の数である。
全てのオペランドは、自然数である。
より一般的には、Ａ，Ｂ，Ｎ，ｎ，ｋ，ｍは、いかなる適切な値をも仮定することができる。
【０１２７】
非モジュラー関数において、Ｎ及びＳレジスタは、他の算術オペランドの一時記憶のために利用されることができる。
【０１２８】
我々は、記号≡をモジュラー数の合同を意味するものとし、例えば、２は１６を７で割った剰余となるので、１６≡２ ｍｏｄ ７ の場合、１６は、７を法として（ｍｏｄｕｌｏ ７）２と合同であると言う。
我々がＹ ｍｏｄ Ｎ≡Ｘ ｍｏｄ Ｎと記述する場合は、Ｙ，Ｘの両方ともＮより大きくてもよいが、正数のＸ，Ｙでは、剰余は同一である。
負の整数Ｙの合同がＹ＋ｕ・Ｎ（Ｎはモジュラス）であることにも留意する必要があり、Ｙの合同がＮ未満となる場合は、ｕは正の結果を与える最も小さい整数である。
【０１２９】
我々は、記号￥を、より限定された意味における合同を意味するものとして利用する。
ここに記載されるプロセスの間、値はしばしば所望の値か、若しくは所望の値にモジュラスを加えた値と等しいかのいずれかである。
例えばＸ￥２ ｍｏｄ ７の場合である。
Ｘは、２又は９と等しい。
この場合、我々は、Ｘが７を法として限定された合同（ｌｉｍｉｔｅｄ ｃｏｎｇｒｕｅｎｃｅ ｔｏ ２ ｍｏｄ ７）を有すると言う。
多項式ベースの体において、アナログは、我々がＮより大きいというところのモニック（ｍｏｎｉｃ）の値であり、モジュラスに対する排他的論理和（ＸＯＲ）を求めることにより減少される。
ＧＦ（２ｑ）においては、桁溢れがないので、￥の値は概して無視される。
【０１３０】
我々がＸ＝Ａ ｍｏｄ Ｎ と記述した場合、ＸはＡをＮで割った剰余と定義され、例えば、３＝４５ ｍｏｄ ７となる。
【０１３１】
数論において、モジュラー型逆数は基礎概念である。
例えば、Ｘのモジュラー型逆数はＸ−１と記述され、Ｘ・Ｘ−１ ｍｏｄ Ｎ＝１により定義される。
Ｘ＝３及びＮ＝１３の場合、Ｘ−１＝９であるが、これを言い換えれば、３・９を１３で割った剰余は１ということである。
【０１３２】
略語ＭＳ及びＬＳは、デジタル用語で一般に用いられているように、ビット、文字、セグメント、全オペランド値に言及する場合に最上位及び最下位を意味するように用いられる。
【０１３３】
この明細書の全体に亘って、Ｎは値Ｎ、及び、Ｎを含む送りレジスタの名称の両方を示す。
値上のアスタリスクの上付き文字は、その値が潜在的に不完全であるか変化する可能性があることを意味する。
Ａは累乗されるべき数値であり、ｎはＮオペランドの文字長さである。
初期状態設定の後、ＡがＡ＊に「モンゴメリ標準化された（Ｍｏｎｔｇｏｍｅｒｙ ｎｏｒｍａｌｉｚｅｄ）」（後述するＡ＊＝２ｎ・Ａ）場合、Ａ＊及びＮは、べき算における中間段階を通じて一定値である。
第一の反復の間、べき算の初期状態設定の後、ＢはＡ＊に等しい。
Ｂは、最終的にべき算の所望の結果と等しくなる累算された値が存在するレジスタの名称でもある。
Ｓ＊は一時的な値を示し、Ｓ，ＳＡ，ＳＢは、Ｓの単一のＭＳビット以外の全てを保存するレジスタを示す。
（このＭＳビットに連結されるＳ＊は、Ｓと同一である。）
Ｓ（ｉ−１）は、ｉ番目の反復の最初でのＳの値を意味し、Ｓ０は、Ｓ（ｉ）番目の値のＬＳセグメントを意味する。
【０１３４】
我々は、ＧＦ（ｐ）体（後に定義する）におけるプロセス▲Ｐ▼（Ａ・Ｂ）Ｎを、Ｐ体における乗算と、又は時には単に乗算演算と称する。
【０１３５】
我々は、並列／直列乗算器の標準的な構造を複動式の直列並列乗算器を構成するための基礎として利用してきたので、（かなり複雑な桁上げ先見加算器（ｃａｒｒｙ ｌｏｏｋ ａｈｅａｄ ａｄｄｅｒ）若しくは非常に遅いリップル加算器とは対照的に）、桁上げ保存累算を基礎とする乗算器の加算部との差異を認め、桁上げ保存加算器若しくは桁上げ保存アキュムレーターと呼び、プリロード機構（ｐｒｅｌｏａｄｉｎｇ ｍｅｃｈａｎｉｓｍ）とマルチプレクサ及びラッチを別々に取り扱うが、これらは、例えばＡ・Ｂ＋Ｃ・Ｄ＋Ｓのように、ＡとＢ及びＣとＤを同時に掛けることができ、連続的に両方の結果と先の結果であるＳとを加算でき、このアキュムレーターをより汎用的なエンジンに変換する。
更なるロジックが、モジュラー縮小（ｍｏｄｕｌａｒ ｒｅｄｕｃｔｉｏｎ）に必要な予測された検知演算（ａｎｔｉｃｉｐａｔｅｄ ｓｅｎｓｅ ｏｐｅｒａｔｉｏｎ）、及び、極めて大きな数におけるモジュラー演算と通常の整数演算とを提供するのに必要な直列総和（ｓｅｒｉａｌ ｓｕｍｍａｔｉｏｎ）を提供するために、この乗算器に加えられる。
【０１３６】
ＧＦ（ｐ）におけるモンゴメリモジュラー型乗算
以下の説明は、数のＧＦ（ｐ）におけるモンゴメリ演算について言及する。
本装置はＧＦ（２ｑ）における多項式ベースの数上のモンゴメリ演算に利用され得るが、計算が、全ての実行可能なオペランドが要素２ｎを乗ぜられるＰ体におけるものであるので、実行においては機能が低下する。
【０１３７】
モジュラー型乗算を計算するための古典的な方法において、Ａ・Ｂ ｍｏｄ Ｎ の場合、積Ａ・Ｂの剰余は除算によって算出される。
大きなオペランドで従来の除算を実行することは、直列／並列乗算よりも機能することが困難である。
【０１３８】
モンゴメリのモジュラー縮小法（ｍｏｄｕｌａｒ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄ）を利用して、除算は二つの予め計算された定数を利用する乗算により本質的に置換される。
本願明細書で示される手順において、一つだけ予め計算された定数があり、それはモジュラス関数である。
この定数は、算術論理演算ユニット装置を利用して計算されるか、若しくは計算され得る。
【０１３９】
この装置において利用されるようなモンゴメリプロセスは、まず簡略的に示され、その後に完全な好ましい説明がなされる。
【０１４０】
我々が、例えば１０１０００１（＝８１１０）のような奇数（ＬＳビットが１）を有する場合、我々は常に、その奇数に他の固定補正（ｆｉｘｉｎｇ， ｃｏｍｅｐｎｓａｔｉｏｎｇ）奇数、例えば１１１１（＝１５１０）を加算することにより、１１１１＋１０１０００１＝１１０００００（９６１０）として、この奇数を偶数（単一のＬＳビットが０）に変換することができる。
この具体的事例において、我々は前もって全文字列である８１を知っており、８１に加算する二進数を容易に決定でき、我々が必要とするＬＳゼロの数を有する新たな二進数を生成できたので、五つのＬＳゼロを生成する数を見つけることができた。
この固定数は右側に１を有していなければならず、さもなければ、結果として出るＬＳ文字に影響を及ぼさない。
【０１４１】
我々のプロセスが、連続したＬＳゼロの数を有することを望み、各々のクロックサイクルで次のビットを固定しさえすればよいクロックされた直列／並列桁上げ保存プロセスである場合、次のビットが１となるようなら各々のクロックでその固定数を加えれば十分であり、予測されるビットがゼロとなるようならその固定数を加えなければ十分である。
しかし、関連した乗数のビットが１であり、Ｙ検知も１と予測する場合、ビット間の桁溢れ（倍の桁上げ）を発生させないために、この固定数は好ましくは前もって被乗数に加算され、アキュムレーターに加えられる。
【０１４２】
ここで、モジュラー演算において、我々はモジュラスによって除算される値の剰余にのみ興味があるので、モジュラスを何回でも値に加算することができ、同じ剰余を有する値をなお有することができることを知っている。
これは、Ｙ・Ｎ＝Σｙｉ・ｒｉ・Ｎをあらゆる整数に加えることができ、なおも同じ剰余を有することを意味する。
ここで、Ｙは、必要なｋ▲ｌ▼の右側ゼロを生成するために、モジュラスＮにおいて加算した回数である。
上記したように、我々が加えるモジュラスは奇数のみである。
（偶数モジュラスが、ｒｉが、ｉが偶数におけるＬＳゼロの数である場合に得られる奇数との積として定義される方法は存在する。）
【０１４３】
モンゴメリのインタリーブされた縮小は、概して保存必要量を減少させ、乗算装置の経済的なサイズを小さくする。
このことは、例えばｎ＝１０２４ビットのような一つの大きな整数に、別の同じ長さの整数を掛けるような、通常倍の長さの整数を生成するプロセスである公開鍵暗号機能を実行する際に、特に有効である。
【０１４４】
我々は、ｎのＬＳゼロと、多くともｎ＋１のＭＳ文字を有する数Ｚを有するように、乗算（若しくは平方）プロセスの間、Ｎｓ（モジュラス）においてＡ・Ｂ＝Ｘ若しくはＡ・Ｂ＋Ｓ＝Ｘに十分な回数加算することができる。
【０１４５】
これらのゼロを無視することにより、ｒｎで所望の結果を除算したことを留意していれば、このような数を利用し続け、ＬＳのｎ文字を無視し続けることができる。
【０１４６】
ＬＳのｎ文字を無視し、最上位のｎ（若しくはｎ＋１）文字のみを使用すると、その結果にｒｎの逆数であるｒ−ｎを効果的に乗算した。
我々が続けてこの結果にｒｎ ｍｏｄ Ｎ（若しくはｒｎ）を再乗算する場合、Ａ・Ｂ＋Ｓ ｍｏｄ Ｎとして、（同じ剰余を有する）所望の結果と合同な値を得る。
ここで見られるように、ＭＭ（Ｍｏｎｔｇｏｍｅｒｙ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）を利用した場合、その結果は、ＭＭによって再導入されたｒ−ｎ寄生要素（ｐａｒａｓｉｔｉｃ ｆａｃｔｏｒ）を克服するために、好ましくはｒ２ｎを乗算される。
【０１４７】
例
Ａ・Ｂ＋Ｓ ｍｏｄ Ｎ＝（１２・１１＋１０） ｍｏｄ １３＝（１１００・１０１１＋１０１０）２ ｍｏｄ １０１１２
▲ｌ▼＝１，ｒ＝２
【０１４８】
我々は、固定数がｎのＬＳビットのうち一つで必要な場合はいつでも２ｉＮを加算する。
Ｂ　　　　　１０１１
×　　Ａ　　　　　１１００
Ｓ　　　　　　　　１０１０　を加算する。
Ａ（０）・Ｂ　　　　　００００　を加算する。
ＬＳビットの合計＝０なのでＮを加算しない。
２０（Ｎ・０）　　　　　００００　を加算する。
合計しシフトする ０１０１　→０のＬＳビットが桁上げ保存加算器を離れる。
Ａ（１）・Ｂ　　　　　００００　を加算する。
ＬＳビットの合計＝０なのでＮを加算する。
２１（Ｎ・１）　　　　 １１０１　を加算する。
合計しシフトする １００１　→０のＬＳビットが桁上げ保存加算器を離れる。
Ａ（２）・Ｂ　　　　　１０１１　を加算する。
ＬＳビットの合計＝０なのでＮを加算しない。
２２（Ｎ・０）　　　　　００００　を加算する。
合計しシフトする　１０１０　→０のＬＳビットが桁上げ保存加算器を離れる。
Ａ（３）・Ｂ　　　　　　１０１１　を加算する。
ＬＳビットの合計＝１なのでＮを加算する。
２３（Ｎ・１）　　　　　 １１０１　を加算する。
合計しシフトする　１０００１　→０のＬＳビットが桁上げ保存加算器を離れる。
結果は１０００１ ００００２ ｍｏｄ １３＝１７・２４ ｍｏｄ １３となる。
【０１４９】
１７は１３より大きいので、１３を減じて、１７・２４≡４・２４ ｍｏｄ １３となり、正式には２−ｎ（Ａ・Ｂ＋Ｓ） ｍｏｄ Ｎ＝９（１２・１１＋１０） ｍｏｄ １３≡４である。
【０１５０】
モンゴメリ演算において、我々はＭＳゼロでない結果である４のみを利用し、実際の結果が２ｎで割られｎのゼロがＭＭの結果に押し込められたことを効果的に留意する。
【０１５１】
我々は、２４ ｍｏｄ １３≡３により結果を効果的に乗算した（８＋２）・１３＝１０・１３において追加した。
結局、我々は不必要なゼロを利用したので、一プロセスでＡ・Ｂ＋Ｙ・Ｎ＋Ｓ−（１２・１１＋１０・１３＋１０）を実行したと言うことができ、好ましい実施例でできるだけ後述する。
【０１５２】
チェックすると、（１２・１１＋１０） ｍｏｄ １３＝１２、４・３＝１２
【０１５３】
結局、モンゴメリ乗算の結果は、２−ｎによって乗算される所望の結果である。
【０１５４】
各々のＭＭは２−ｎの寄生要素を残すので、前の結果を同じ乗算法を利用する所望の結果へ戻すために、我々は２２ｎにより前の結果をモンゴメリ乗算する必要があり、これをＨと呼ぶ。
【０１５５】
モンゴメリ乗算関数▲Ｐ▼（Ａ・Ｂ）Ｎは、Ｐ体で積Ａ・ＢのＮを法とする乗算を実行する。（上記の例では４を誘導した部分である。）
Ｐフィールドから通常のモジュラー体へ戻すことは、予め計算された定数Ｈを利用して、▲Ｐ▼（Ａ・Ｂ）Ｎの結果におけるＰを定めることにより実行される。
ここでＰ＝▲Ｐ▼（Ａ・Ｂ）Ｎである場合、▲Ｐ▼（Ｐ・Ｈ）Ｎ≡Ａ・Ｂ ｍｏｄ Ｎに従うことにより、二つのＰ体の乗算において通常のモジュラー乗算を行う。
【０１５６】
モンゴメリモジュラー縮小（Ｍｏｎｔｇｏｍｅｒｙ ｍｏｄｕｌａｒ ｒｅｄｕｃｔｉｏｎ）は、ｎ若しくはｎ＋１文字長さであるオペランドでの一連の乗算、加算、減算を実行することにより、ｎ若しくは２ｎ文字長さであるオペランドでの一連の乗算、除算を回避する。
全体のプロセスは、Ｎより小さいかＮと同じ結果となる。
与えられたＡ，Ｂ，奇数Ｎについては、Ａ・Ｂ＋Ｑ・ＮがｎのＬＳ文字がゼロである数となるか、又は、Ｐ・２ｎ＝Ａ・Ｂ＋Ｑ・ＮとなるようなＱが常にある。
【０１５７】
これは、我々がｎのＬＳ文字がゼロである（可能な１ビットの桁溢れを有する）２ｎ文字長さである表現を有することを意味する。
【０１５８】
ここで、基数ｒ＝２▲ｌ▼で、Ｉ・ｒｎ≡１ ｍｏｄ Ｎとする（Ｉは全ての奇数Ｎで存在する）。
上式の両側にＩを乗算することで、以下の合同が得られる。
式の左側からはＰ・Ｉ・ｒｎ≡Ｐ ｍｏｄ Ｎ（Ｉ・ｒｎ≡１ ｍｏｄ Ｎより）、式の右側からはＡ・Ｂ・Ｉ＋Ｑ・Ｎ・Ｉ≡Ａ・Ｂ・Ｉ ｍｏｄ Ｎ（Ｑ・Ｎ・Ｉ≡０ ｍｏｄ Ｎより）、
従って、Ｐ≡Ａ・Ｂ・Ｉ ｍｏｄ Ｎ
これは、Ｐ体乗算が実行される毎に、寄生要素Ｉ＝ｒ−ｎ ｍｏｄ Ｎが導入されることをも意味する。
▲Ｐ▼演算子は、Ｐ≡Ａ・Ｂ・Ｉ ｍｏｄ Ｎ≡▲Ｐ▼（Ａ・Ｂ）Ｎとなるように定義され、これを「Ｐ体におけるＡ×Ｂの乗算」又はモンゴメリ乗算と呼ぶ。
Ｐ体からの戻しは、Ｐ・Ｈで▲Ｐ▼を演算することによって計算でき、▲Ｐ▼（Ｐ・Ｈ）Ｎ≡Ａ・Ｂ ｍｏｄ Ｎとする。
我々は、前出の合同式のＰを置換することによってＨの値を誘導することができる。
我々は、▲Ｐ▼（Ｐ・Ｈ）Ｎ≡（Ａ・Ｂ・Ｉ）（Ｈ）（Ｉ） ｍｏｄ Ｎを見出した。
（Ａ・Ｂ・Ｉ←Ｐ、Ｈ←Ｈ、Ｉ←であり、あらゆる乗算演算が寄生要素Ｉを導入することを参照）
【０１５９】
ＨがＩ２の逆数と合同である場合、合同式は有効であるので、Ｈ＝Ｉ−２ ｍｏｄ Ｎ≡ｒ２ｎ ｍｏｄ Ｎ（Ｈは、Ｎの関数であり、Ｈパラメーターと呼ぶ。）
【０１６０】
従来のモンゴメリ法において、Ａ・Ｂでの▲Ｐ▼演算子を定めるためには、予め計算された定数Ｊを用いて以下のプロセスを行う。
１）Ｘ＝Ａ・Ｂ
２）Ｙ＝（Ｘ・Ｊ） ｍｏｄ ｒｎ（ｎのＬＳ文字のみが必要）
３）Ｚ＝Ｘ＋Ｙ・Ｎ
４）Ｓ＝Ｚ／ｒｎ（Ｊの必要条件は、Ｚをｒｎによって割り切れるようにすることである。）
５）Ｐ￥Ｓ ｍｏｄ Ｎ（Ｓ≧Ｎの場合、ＮはＳから減算される。）
最後に第５段階で、
Ｐ￥▲Ｐ▼（Ａ・Ｂ）Ｎ
［Ｎの減算の後、必要ならばＰ＝▲Ｐ▼（Ａ・Ｂ）Ｎ］
上記に続いて、Ｙ＝Ａ・Ｂ・Ｊ ｍｏｄ ｒｎ（ｎのＬＳ文字のみを使用）
Ｚ＝Ａ・Ｂ＋（Ａ・Ｂ・Ｊ ｍｏｄ ｒｎ）・Ｎ
【０１６１】
Ｚをｒｎで割り切れるようにするため（ＺのｎのＬＳ文字は好ましくはゼロである）、以下の合同式がある。
［Ａ・Ｂ＋（Ａ・Ｂ・Ｊ ｍｏｄ ｒｎ）・Ｎ］ ｍｏｄ ｒｎ≡０
【０１６２】
この合同式が存在するために、Ｎ・Ｊ ｍｏｄ ｒｎは−１と合同であるか、又は、
Ｊ≡−Ｎ−１ ｍｏｄ ｒｎ
我々は、定数Ｊを見つけた。
【０１６３】
従って、ＪはＮのみの関数である予め計算された定数である。
しかし、ＭＭの結果を出力するマシンにおいて、ＬＳ文字列で出力される文字が別にゼロであった各々の場合で、文字毎にＮに加えられる用意がなされているべきであり、それにより、Ｙが配線論理を利用して文字毎に検出されるので、Ｊを予め計算し、続いてＹ＝Ａ・Ｂ・Ｊ ｍｏｄ ｒｎを計算する必要性はなくなる。
我々は、この方法が奇数のＮｓについてのみ機能できることを述べた。
【０１６４】
従って、明らかなように、上述したプロセスは、▲Ｐ▼（Ａ・Ｂ）Ｎを得るために、与えられたＡ，Ｂ，Ｎ及び予め計算された定数で三つの乗算、一つの加算、多くても一つの減算を用いる。
この結果、同じプロセス及び予め計算された定数Ｈ（モジュールＮの関数）を利用して、我々はＡ・Ｂ ｍｏｄ Ｎを見つけることができる。
ＡはＢと等しくてもよいので、この基本演算器は、モジュラー演算において平方又は乗算する装置として使用できる。
【０１６５】
インタリーブされたモンゴメリモジュラー型乗算
上記では、全てｎ文字長さであるオペランド及び２ｎ＋１文字の保存空間を必要とした結果の乗算を含んだモジュラー型乗算の方法を説明している。
【０１６６】
Ｐ１に記載したモンゴメリのインタリーブされた縮小を利用して、より短いオペランド、レジスタ及びハードウェア乗算器で乗算演算を実行することが可能であり、比較的少ない論理ゲートでの電子装置のインプリメンテーション（ｉｍｐｌｅｍｅｎｔａｔｉｏｎ）を可能にする。
【０１６７】
まず、我々は、インタリーブの各々の反復で、Ｊ０定数を利用してＮが加算される回数を計算する場合に、装置がどのように機能するかについて説明する。
後で我々は、Ｙ０の配線誘導（ｈａｒｄｗｉｒｅ ｄｅｒｉｖａｔｉｏｎ）を利用したインタリーブする方法を説明するが、これは各々の乗算のＪ０＋段階を排除し（後述の例の（２）参照）、二つの別々の直列／乗算器を、同様のシリコン資源を利用して、倍速以上の速度でＡ・Ｂ＋Ｃ・Ｎ＋Ｓを実行できる新たな単一の汎用乗算器に組み込むことを可能にする。
【０１６８】
ｋ文字の乗数を利用して、ｎ文字にｍのセグメントを有する、即ちｍ・ｋ＝ｎとなるようにｋ文字長さのセグメントを定めることは便利である。
Ｊ０は、ＪのＬＳセグメントである。
従って、Ｊ０≡−Ｎ０−１ ｍｏｄ ｒｋである（Ｎとして存在するＪ０は奇数である）。
【０１６９】
Ｊ及びＪ０定数は、所定数の最下位ゼロを有するように、減少していない出力を定める場合に、モジュラスを加える回数を伝える補正数（ｃｏｍｐｅｎｓａｔｉｎｇ）であることに留意すべきである。
次の出力の直列ビットを容易に決めることができるように、次の中間結果に常にモジュラス（常に奇数）を加算するので、我々は本発明に係るシリアルデバイスの更なる利点を後述する。
これは、この加算がなければＣＳＡに存在するＬＳ直列ビットである出力文字が「１」であった場合であり、それにより、先の中間結果にさえモジュラスを加算し、出力文字列に別のＬＳゼロを約束する。
どんなにモジュラスが結果に加算されようとも、剰余が一定であるので、合同が維持されることを思い出すべきである。
【０１７０】
モンゴメリのインタリーブされた縮小の従来の使用において、▲Ｐ▼（Ａ・Ｂ）Ｎは、（１）〜（５）の段階で説明されるように、ｍ回の反復で定められる。
まずＳ（０）＝０とする（第一の反復の最初でのＳの￥の値）。
ｉ＝１，２では、ｍ：
１）Ｘ＝Ｓ（ｉ−１）＋Ａｉ−１・Ｂ（Ａｉ−１はＡのｉ−１番目の文字であり、Ｓ（ｉ−１）は、ｉ番目の反復の最初でのＳの値である。）
２）Ｙ０＝Ｘ０・Ｊ０ ｍｏｄ ｒｋ（Ｘ０・Ｊ０の積のＬＳｋ文字）
（このプロセスは、ｋのＬＳ文字のみ、例えば最下位６４文字のみを使用し計算する。）
直列マシンにおいて、Ｙ０は文字毎に予測されるから、好ましいインプリメンテーションにおいて、この段階は不要である。
３）Ｚ＝Ｘ＋Ｙ０・Ｎ
４）Ｓ（ｉ）＝Ｚ／ｒｋ
（ＺのｋのＬＳ文字は常にゼロであるので、Ｚは常にｒで割り切れる。
ＺのＬＳｋ文字は全てのゼロであるので、この除算はｋ文字の右側へのシフト（ｓｈｉｆｔ；桁送り）に相当し、または、回路に示されるように、ＺのＬＳｋ文字は単に無視される。
５）Ｓ（ｉ）＝Ｓ（ｉ） ｍｏｄ Ｎ（Ｎは、Ｎより大きなそれらのＳ（ｉ）から減算されることになる）。
最後に、（必要な場合はＮの減算の後）最後の反復で、Ｃ＝Ｓ（ｍ）＝▲Ｐ▼（Ａ・Ｂ）Ｎ
【０１７１】
Ｆ＝Ａ・Ｂ ｍｏｄ Ｎを誘導するために、Ｐ体計算▲Ｐ▼（Ｃ・Ｈ）Ｎが実行される。
【０１７２】
好ましい実施例において、全てのＳ（ｉ）でＳ（ｉ）が２Ｎより小さくなることを知ることが望ましい。
これは、最後の結果（Ｓ（ｍ））が常に、多くとも一回のＮの減算で、Ｎより少ない数量に減算され得ることをも意味する。
【０１７３】
我々は、以下のプロセスにおいて利用されるオペランドでそのことを観察する。
即ち、Ｓ（ｉ−１）＜ｒｎ＋１
（一時レジスタは、Ｂ又はＮレジスタよりも１ビット長くてもよい）、
Ｂ＜Ｎ＜ｒｎ、及び、Ａｉ−１＜ｒｋ
定義により、Ｓ（ｉ）＝Ｚ／ｒｋ（可能な減算前のプロセスの終わりのＳの値）
全てのＺで、Ｚ（ｉ）＜ｒｎ＋ｋ＋１
Ｘｍａｘ＝Ｓｍａｘ＋Ａｉ・Ｂ＜ｒｎ＋１−１＋（ｒｋ−１）（ｒｎ−１）
Ｑｍａｘ＝Ｙ０Ｎ＜（ｒｋ−１）（ｒｎ−１）
従って、Ｚｍａｘ＜ｒｋ＋ｎ＋１−ｒｋ＋１＋１＜ｒｋ＋ｎ＋１−１
Ｚｍａｘはｒｋで割り切れるので、
Ｓ（ｍ）＜ｒｎ＋１＜−ｒ１
Ｎｍｉｎ＞ｒｎ−ｒなので、Ｓ（ｍ）ｍａｘは常に２・Ｎｍｉｎよりも小さく、従って、一回の減算が最後の結果で必要なだけである。
Ｓ（ｍ）ｍａｘ−Ｎｍｉｎ＝（ｒｎ＋１−ｒ１−１）−（ｒｎ−１）＝ｒｎ−４＜Ｎｍｉｎ
【０１７４】
モンゴメリのインタリーブされたモジュラー型乗算の例
十六進数での以下の計算は、インタリーブされた方法の意味を明らかにする。
Ｎ＝ａ５９（モジュロ（ｍｏｄｕｌｏ））、Ａ＝９９ｂ（乗数）、Ｂ＝５ｃ３（被乗数）、ｎ＝１２、 ｒ＝２）（Ｎの文字長さ）、ｋ＝４（乗数の文字におけるサイズ、更にはセグメントのサイズ）、ｎ＝ｋ・ｍなのでｍ＝３。
７・９≡−１ ｍｏｄ １６及びＨ≡２２・１２ ｍｏｄ ａ５９≡４４ｂなのでＪ０＝７。
【０１７５】
期待される結果は、Ｆ≡Ａ・Ｂ ｍｏｄ Ｎ≡９９ｂ・５ｃ３ ｍｏｄ ａ５９≡３７５８１１ ｍｏｄ ａ５９≡２２０１６である。
【０１７６】
最初にＳ（０）＝０で、
段階１
Ｘ＝Ｓ（０）＋Ａ０・Ｂ＝０＋ｂ・５ｃ３＝３ｆ６１
Ｙ０＝Ｘ０・Ｊ０ ｍｏｄ ｒｋ＝７（Ｙ０は、ＳｕｐｅｒＭＡＰにおいて予測される配線）
Ｚ＝Ｘ＋Ｙ０・Ｎ＝３ｆ６１＋７・ａ５９＝８７ｄ０
Ｓ（１）＝Ｚ／ｒｋ＝８７ｄ
段階２
Ｘ＝Ｓ（１）＋Ａ１・Ｂ＝８７ｄ＋９・５ｃ３＝３ｃ５８
Ｙ０＝Ｘ０・Ｊ０ ｍｏｄ ｒｋ＝８・７ ｍｏｄ ２４＝８（予測される配線）
Ｚ＝Ｘ＋Ｙ０・Ｎ＝３ｃ５８＋５２ｃ８＝８ｆ２０
Ｓ（２）＝Ｚ／ｒｋ＝８ｆ２
段階３
Ｘ＝Ｓ（２）＋Ａ２・Ｂ＝８ｆ２＋９・５ｃ３＝３ｃｃｄ
Ｙ０＝ｄ・７ ｍｏｄ ２４＝ｂ（予測される配線）
Ｚ＝Ｘ＋Ｙ０・Ｎ＝３ｃｃｄ＋ｂ・ａ５９＝ａｅａ０
Ｓ（３）＝Ｚ／ｒｋ＝ａｅａ
Ｓ（３）＞Ｎなので、
Ｓ（ｍ）＝Ｓ（３）−Ｎ＝ａｅａ−ａ５９＝９１
従って、Ｃ＝▲Ｐ▼（Ａ・Ｂ）Ｎ＝９１１６
Ｐ体からの戻しは、▲Ｐ▼（Ｃ・Ｈ）Ｎを計算することによって実行される。
再び最初にＳ（０）＝０で、
段階１
Ｘ＝Ｓ（０）＋Ｃ０・Ｈ＝０＋１・４４ｂ＝４４ｂ
Ｙ０＝ｄ（スーパーマップにおいて予測される配線）
Ｚ＝Ｘ＋Ｙ０・Ｎ＝４４ｂ＋８６８５＝８ａｄ０
Ｓ（１）＝Ｚ／ｒｋ＝８ａｄ
段階２
Ｘ＝Ｓ（１）＋Ｃ１・Ｈ＝８ａｄ＋９・４４ｂ＝２ｆ５０
Ｙ０＝０（スーパーマップにおいて予測される配線）
Ｚ＝Ｘ＋Ｙ０・Ｎ＝２ｆ５０＋０＝２ｆ５０
Ｓ（２）＝Ｚ／ｒｋ＝２ｆ５０
段階３
Ｘ＝Ｓ（２）＋Ｃ２・Ｈ＝２ｆ５＋０・４４ｂ＝２ｆ５
Ｙ０＝３（スーパーマップにおいて予測される配線）
Ｚ＝Ｘ＋Ｙ０・Ｎ＝２ｆ５＋３・ａ５９＝２２００
Ｓ（３）＝Ｚ／ｒｋ＝２２０１６
それは、９９ｂ・５ｃ３ ｍｏｄ ａ５９の期待値である。
【０１７７】
各々の段階で我々がｋのＬＳを無視したとすれば、本質的にｎのＭＳ文字をｒｋによって乗算することとなる。
同様に、各々の段階で、乗数のｉ番目のセグメントはｒｉｋによって乗算される数であり、それにＳ（ｉ）と同位（ｓａｍｅ ｒａｎｋ）を与える。
【０１７８】
Ｊ０定数を知るための潜在的な値がある別の好ましい実施例において、Ａｉ・Ｂ＋Ｓ＝１である場合、Ｙ０＝−Ｎ０−１＝Ｊ０である。
【０１７９】
べき算（Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）
『ディー・クヌース（Ｄ．Ｋｎｕｔｈ）著、「コンピュータプログラミングの技法（Ｔｈｅ ａｒｔ ｏｆ ｃｏｍｐｕｔｅｒ ｐｒｏｇｒａｍｍｉｎｇ）」、第２巻、準数値算法（Ｓｅｍｉｎｕｍｅｒｉｃａｌ ａｌｇｏｒｉｔｈｍｓ）、アディソン・ウェズリー（Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ）、リーディング、マサチューセッツ州、１９８１年、ｐ．４０７』（以下クヌースと称す）で、シーケンスの以下の導出は、平方及び乗算のシーケンスを説明しており、べき剰余（ｍｏｄｕｌａｒ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）を実行する。
【０１８０】
この装置はＰ体において平方及び乗算することができるので、モンゴメリ定数を予め計算した後（Ｈ＝２２ｎ）、我々はＣ＝ＡＥ ｍｏｄ Ｎを計算する。
Ｅ（ｊ）はべき指数Ｅの二進法におけるｊビットを意味し、指数１のＭＳビットから始まり、指数ｑのＬＳビットで終わるとすると、奇数のべき指数で以下のように累算できる。
Ａ＊ ￥ ▲Ｐ▼（Ａ・Ｈ）Ｎ
Ａ＊は、Ａ・２ｎに等しい。
Ｂ＝Ａ＊
ｊ＝２〜ｑ−１で（ＦＯＲ ｊ＝２ ＴＯ ｑ−１）
Ｂ ￥ ▲Ｐ▼（Ｂ・Ｂ）Ｎ
Ｅ（ｊ）＝１ならば、Ｂ ￥ ▲Ｐ▼（Ｂ・Ａ＊）Ｎである
（もし Ｅ（ｊ）＝１ならば Ｂ ￥ ▲Ｐ▼（Ｂ・Ａ＊）Ｎ
ＦＯＲループの終わり（ＥＮＤＦＯＲ）
Ｂ ￥ ▲Ｐ▼（Ｂ・Ａ）Ｎ　　Ｅ（０）＝１
Ｂは、２ｎを掛けられる最後の一時的な値であり、Ａは元々のＡである。
Ｃ＝Ｂ
もしＣ≧Ｎならば、Ｃ＝Ｃ−Ｎ
最後の反復の後、値ＢはＡＥ ｍｏｄ Ｎに対する￥であり、Ｃは最終の値である。
【０１８１】
明らかにするために、以下の例を利用することとする。
Ｅ＝１０１１ → Ｅ（１）＝１、Ｅ（２）＝０、Ｅ（３）＝１、Ｅ（４）＝１
ｑ＝４でＡ１０１１ ｍｏｄ Ｎを見つけるために、
Ａ＊＝▲Ｐ▼（Ａ・Ｈ）Ｎ＝Ａ・Ｉ−２Ｉ＝Ａ・Ｉ−１ ｍｏｄ Ｎ
Ｂ＝Ａ＊
ｊ＝２〜ｑで（ＦＯＲ ｊ＝２ ｔｏ ｑ）
Ｂ＝▲Ｐ▼（Ｂ・Ｂ）Ｎより、Ａ２（Ｉ−１）２・Ｉ＝Ａ２・Ｉ−１
Ｅ（２）＝０　　Ｂ＝Ａ２・Ｉ−１
ｊ＝３　　　 Ｂ＝▲Ｐ▼（Ｂ・Ｂ）Ｎ＝Ａ２（Ｉ−１）２・Ｉ＝Ａ４・Ｉ−１
Ｅ（３）＝１　　Ｂ＝▲Ｐ▼（Ｂ・Ａ＊）Ｎ＝（Ａ４・Ｉ−１）（Ａ・Ｉ−１）・Ｉ＝Ａ５・Ｉ−１
ｊ＝４　　　 Ｂ＝▲Ｐ▼（Ｂ・Ｂ）Ｎ＝Ａ１０・Ｉ−２・Ｉ＝Ａ１０・Ｉ−１
Ｅ（４）が奇数だったので、寄生要素Ｉ−１を取り除くために、最後の乗算はＡによるものである。
Ｂ＝▲Ｐ▼（Ｂ・Ａ）Ｎ＝Ａ１０・Ｉ−１・Ａ・Ｉ＝Ａ１１
Ｃ＝Ｂ
【０１８２】
逆数プロセスによってＨパラメータを計算する方法は、米国特許第５５１３１３３号明細書に記載されている。
【０１８３】
次に図３を参照するが、これは本発明がスマートカード及び他のセキュリティ装置に実装される方法を示すブロック略図である。
内部バス５００は、ＣＰＵ５０２、ＲＡＭ５０４、不揮発性メモリ５０６、制御アクセスＥＥＰＲＯＭ（ｃｏｎｔｒｏｌｌｅｄ ａｃｃｅｓｓ ＥＥＰＲＯＭ）５０８、モジュラー演算コプロセッサ５１０を含む部品と連結する。
ここに示すように、コプロセッサ５１０は、データレジスタ５１２及び制御レジスタ５１４を経由して、内部バス５００に接続される。
制御アクセスＥＥＰＲＯＭ５０８は、アドレス及びデータラッチ手段５１６、並びに、制御及びテストレジスタ５１８を経由して接続される。
例えば物理シーケンスランダム生成器（ｐｈｙｓｉｃａｌ ｓｅｑｕｅｎｃｅ ｒａｎｄｏｍ ｇｅｎｅｒａｔｏｒ）５２０、セキュリティ論理（ｓｅｃｕｒｉｔｙ ｌｏｇｉｃ）５２２、スマートカードインターフェース回路５２４、外部ポートインターフェース回路５２６のような多様な他の装置が夫々、バスに接続されてもよい。
【０１８４】
ＲＳＡデジタル署名を確認するような暗号プログラムが実行される場合に、べき剰余のようなモジュラー演算機能を必要とする。
暗号関数を呼び出す暗号プログラムは、好ましくはＣＰＵ５０２上で実行される。
【０１８５】
次に図４を参照するが、これはスマートカードにおいて利用するための本発明の実装の別のブロック略図である。
図３において示されるものと同じ部品は、同じ符号を与えられているが、本実施例の理解に必要なもの以外は、ここでは説明しない。
図４において、ＣＰＵ５０２は外部アキュムレーター７３５０を備えて示される。
演算コプロセッサからのデータをアンロードすることによりＳＭＡＰから記憶装置への直接データ転送を可能にする一方で、データ使用禁止スイッチ７３４０が、データバス５００からＣＰＵアキュムレーターを分離する。
【０１８６】
図５は、Ｊ０生成器と共に、図２，６，７のコプロセッサにて図示されるようなコプロセッサ６０７５内でのデータレジスタバンク（ｄａｔａ ｒｅｇｉｓｔｅｒ ｂａｎｋ）６２０５の好ましい実施例のブロック略図であり、Ｊ０生成器は概して▲ｌ▼ビットの一次ゼロ（ｐｒｉｍａｒｙ ｚｅｒｏ）強制関数をコンパイルする（ｃｏｍｐｉｌｅ）。
【０１８７】
コプロセッサ６０７５は、前出の図にあるように、ＣＰＵと共にデータバスに接続される。
レジスタバンク６２０５は、Ｂレジスタ６０７０、Ａレジスタ６１３０、Ｓレジスタ６１８０、Ｎレジスタ６２００からなる。
各々のレジスタの出力は、直列データスイッチ及び直列プロセス調節器（ｓｅｒｉａｌ ｄａｔａ ｓｗｉｔｃｈ ａｎｄ ｓｅｒｉａｌ ｐｒｏｃｅｓｓ ｃｏｎｄｉｔｉｏｎｅｒ）６０２０に接続し、次いで演算ユニット６２０６に接続され、そこでモジュラー演算を行う。
Ｎレジスタ６２００と演算ユニット６２０６との間には、Ｊ０生成器５５２が接続される。
【０１８８】
本実施例において、Ｊ０生成器は、上記したモジュラー演算機能において利用するために、▲ｌ▼ビットの一次ゼロ強制関数をコンパイルする。
【０１８９】
図６は、図５の演算ユニットの内部ブロック略図である。
このユニットは、更なるＹ０Ｂ０シリアルバッファ（ｓｅｒｉａｌ ｂｕｆｆｅｒ）が第一段階でＹ０を受け入れ、第二段階で次の平方演算のためにモジュラー縮小されたＢ０を受け入れ、そこでＢがＮより長いことが明らかになるという点において、好ましくは高速化平方演算（ａｃｃｅｌｅｒａｔｅｄ ｓｑｕａｒｉｎｇ ｏｐｅｒａｔｉｏｎ）を支援する。
【０１９０】
次に図７Ａを参照するが、これは図６の演算ユニットの主計算部のブロック図である。
丸数字で表した数字は図７Ｂ，Ｄのシーケンス図に関するものである。
【０１９１】
次に図７Ｂを参照するが、これは平方演算の第一の反復（ｆｉｒｓｔ ｉｔｅｒａｔｉｏｎ）へ向かい、第一の反復をも含むプロセスを経時的に示した事象タイミングをポインタで示す図である。
【０１９２】
次に図７Ｃを参照するが、これは平方シーケンス（ｓｑｕａｒｉｎｇ ｓｅｑｕｅｎｃｅ）の第一の反復における次のモンゴメリ平方（Ｎｅｘｔ Ｍｏｎｔｇｏｍｅｒｙ Ｓｑｕａｒｉｎｇ）を排除する事象シーケンスを示す図である。
丸数字は図７Ａ，Ｂ，Ｄを参照する。
【０１９３】
次に図７Ｄを参照するが、これは、平方演算の第一の反復の計算の出力のタイミングを示す事象タイミングをポインタで示す図である。
【０１９４】
次に図８Ａを参照するが、これは概してＪ０の選択を示す一組のルックアップテーブルであり、Ｎ０の右側の文字のモジュラス２▲ｌ▼での負の逆数（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｉｎｖｅｒｓｅ；乗法逆元）である。
Ｎ０は常に、ＧＦ（２ｑ）についてモニックである（ｍｏｎｉｃ）か、又はＧＦ（ｐ）について奇数であるので、Ｊ０は常に存在する。
【０１９５】
図８Ａ及び８Ｂにおいて、我々はこのモジュラスの右側の文字をＮ０と呼ぶ。
我々は、Ｎ０ｊを、局所定義された（ｌｏｃａｌｌｙ ｄｅｆｉｎｅｄ）Ｎ０文字のｊ番目のビットとする。
【０１９６】
図８Ｂは、４ビット若しくは２ビットのＹ０ゼロ強制関数文字のいずれかの設計回路図である。
強制関数への変数入力は、Ｎ０ビット（乗算の間一定である）、▲ｌ▼、Ｓ０ビット、▲ｌ▼乗数及び被乗数ビットの積の▲ｌ▼の右側のビットＡｉ０及びＢ０ｊ、ＧＦ（２ｑ）又はＧＦ（ｐ）においてどの関数が機能するかを決定する桁上げスイッチ▲Ｓ▼である。
Ａ及びＢビットは、▲○×▼乗算器及びＳ０に加算された▲○＋▼に入力される。　▲Ｓ▼＝０の場合、全ての桁上げができなくなる。
【０１９７】
本発明の内容を明らかにするために別の実施例の文脈において記載される本発明の多様な特徴が、単一の実施例との組合せにより提供され得ることは理解される。
逆に、説明の容易化のために単一の実施例の文脈において記載される本発明の多様な特徴が、別々に、若しくは適切なサブコンビネーションにおいても提供され得る。
【０１９８】
本発明が、本明細書に特に示され記載されたものに限定されないことは当業者ならば理解できるだろう。
むしろ、本発明の範囲は、本明細書に記載された多様な特徴の変更及び修正と同様に、その多様な特徴の組合せ及びサブコンビネーションをも含み、従来技術にない前述の記載を読めば、当業者ならば思いつくものである。
【０１９９】
特許請求の範囲において、符号や記号は上記で与えられた意味を有する。
【図面の簡単な説明】
【図１】
本発明の一実施例に係る装置のブロック図であり、四つの主要なレジスタが記載され、演算ユニットへのシリアルデータのフロー経路、及び図３のホストＣＰＵへの入出力データの経路が示される。
【図２】
図１からのデータを演算するように機能する演算ユニットの実施例のブロック図である。
【図３】
典型的にはスマートカード内にある完全なシングルチップのモノリシック暗号コンピュータ（ｍｏｎｏｌｉｔｈｉｃ ｃｒｙｐｔｏｃｏｍｐｕｔｅｒ））の好ましい実施例のブロック略図である。
【図４】
データ使用禁止スイッチ（ｄａｔａ ｄｉｓａｂｌｅ ｓｗｉｔｃｈ）が演算ユニットからのデータのアンロードを速めるように作動する完全なシングルチップのモノリシック暗号コンピュータの好ましい実施例のブロック略図である。
【図５】
Ｊ０を生成するように作動するデータレジスタバンク（ｄａｔａ ｒｅｇｉｓｔｅｒ ｂａｎｋ）のブロック略図である。
【図６】
Ｙ０検知（Ｙ０ ｓｅｎｓｅ；Ｙ０センス）が第一段階の出力を０にする演算装置である演算ユニットのブロック略図である。
【図７Ａ】
図７Ｂ〜Ｄのタイミング図及びフロー図に係る丸数字を付したシーケンスアイコンを有する図６の主計算部のブロック図である。
【図７Ｂ】
平方演算の第一の反復（ｆｉｒｓｔ ｉｔｅｒａｔｉｏｎ）へ向かい、第一の反復をも含むプロセスを経時的に示した事象タイミングをポインタで示す図である。
【図７Ｃ】
図７Ａ，Ｂ，Ｄに係る平方シーケンス（ｓｑｕａｒｉｎｇ ｓｅｑｕｅｎｃｅ）のアイコン化されたポインタの第一の反復における「次のモンゴメリ平方（Ｎｅｘｔ Ｍｏｎｔｇｏｍｅｒｙ Ｓｑｕａｒｉｎｇ）」を排除する詳細な事象シーケンスを示す図である。
【図７Ｄ】
図７Ａ〜Ｃに係る計算の出力のタイミングを示す図である。
【図８Ａ】
ＧＦ（２ｑ）及びＧＦ（ｐ）におけるＹ０ベクトルの生成について記載した図であって、▲ｌ▼＝２及び▲ｌ▼＝４の場合で、右側のＮ０の負の逆数を決定する一組のルックアップテーブル（ｌｏｏｋ ｕｐ ｔａｂｌｅ；参照表）である。
【図８Ｂ】
ＧＦ（２ｑ）及びＧＦ（ｐ）におけるＹ０ベクトルの生成について記載した図であって、▲ｌ▼＝２及び▲ｌ▼＝４の場合の両数値フィールドにおけるＹ０関数を生成する信号を記載するブロック略図である。
【図１】
2004501396.tif 000008
【図２】
2004501396.tif 000009
【図３】
2004501396.tif 000010
【図４】
2004501396.tif 000011
【図５】
2004501396.tif 000012
【図６】
2004501396.tif 000013
【図７Ａ】
2004501396.tif 000014
【図７Ｂ】
2004501396.tif 000015
【図７Ｃ】
2004501396.tif 000016
【図７Ｄ】
2004501396.tif 000017
【図８Ａ】
2004501396.tif 000018
【図８Ｂ】
2004501396.tif 000019
【国際公開パンフレット】
2004501396.tif 000020
2004501396.tif 000021
2004501396.tif 000022
2004501396.tif 000023
2004501396.tif 000024
2004501396.tif 000025
2004501396.tif 000026
2004501396.tif 000027
2004501396.tif 000028
2004501396.tif 000029
2004501396.tif 000030
2004501396.tif 000031
2004501396.tif 000032
2004501396.tif 000033
2004501396.tif 000034
2004501396.tif 000035
2004501396.tif 000036
2004501396.tif 000037
2004501396.tif 000038
2004501396.tif 000039
2004501396.tif 000040
2004501396.tif 000041
2004501396.tif 000042
2004501396.tif 000043
2004501396.tif 000044
2004501396.tif 000045
2004501396.tif 000046
2004501396.tif 000047
2004501396.tif 000048
2004501396.tif 000049
2004501396.tif 000050
2004501396.tif 000051
2004501396.tif 000052
2004501396.tif 000053
2004501396.tif 000054
2004501396.tif 000055
2004501396.tif 000056
2004501396.tif 000057
2004501396.tif 000058
2004501396.tif 000059
2004501396.tif 000060
2004501396.tif 000061
2004501396.tif 000062
2004501396.tif 000063
2004501396.tif 000064
2004501396.tif 000065
2004501396.tif 000066
2004501396.tif 000067
2004501396.tif 000068
2004501396.tif 000069
2004501396.tif 000070
2004501396.tif 000071
2004501396.tif 000072
2004501396.tif 000073
2004501396.tif 000074
2004501396.tif 000075
2004501396.tif 000076
2004501396.tif 000077
2004501396.tif 000078
2004501396.tif 000079
2004501396.tif 000080
2004501396.tif 000081
2004501396.tif 000082
2004501396.tif 000083
2004501396.tif 000084
2004501396.tif 000085
2004501396.tif 000086
2004501396.tif 000087
【国際公開パンフレット（コレクトバージョン）】
2004501396.tif 000088
2004501396.tif 000089
【国際調査報告】
2004501396.tif 000090