(57)【特許請求の範囲】
【請求項１】
モンゴメリ乗算を実施するための処理システムであって、
前記処理システムは、
１組のレジスタを有し、暗号化機能を実行するプロセッサであって、前記モンゴメリ乗算は、前記暗号化機能におけるべき乗を計算するために使用されるものであり、当該プロセッサがＳＩＭＤ命令をサポートするように構成されたプロセッサと、
モンゴメリ乗算を実行するための、前記プロセッサによって実行可能な１組のＳＩＭＤ命令と
を含み、
前記モンゴメリ乗算は、
ｍｏｎｔｍｕｌ（Ａ，Ｂ）＝ｒｅｍ（（ＡＢ−ｑＮ）／Ｒ，Ｎ）、ここでｑ＝ｒｅｍ（ＡＢ  Ｎ’，Ｒ）であり、
ＡおよびＢは整数であり、ｑは商であり、Ｎは法であり、Ｒは法Ｎと互いに素である整数であり、Ｎ’はＮＮ’≡１（ｍｏｄ  Ｒ）となるような整数であり、ｒｅｍは剰余演算であって、かつ、
前記整数Ｂおよび前記法Ｎは配列として実施され、少なくとも１つのＳＩＭＤ命令を使用して、ＡＢを計算するためのＢの倍数で第１の配列Ｔ１を更新し、ｑＮを計算するためのＮの倍数で第２の配列Ｔ２を更新するものとして定義されるものであり、
第１のレジスタは、前記ＢおよびＮの配列の要素を保持し、
第２のレジスタは、前記第１の配列Ｔ１の要素と前記第２の配列Ｔ２の要素とを保持し、
第３のレジスタは、Ｂの倍数で更新された前記第１の配列Ｔ１およびＮの倍数で更新された前記第２の配列Ｔ２の結果を保持するために使用されるものであり、
前記ＳＩＭＤ命令は、乗算ＡＢおよびｑＮの部分を同時に実行する単一のＳＩＭＤ命令を含む
ことを特徴とする処理システム。
【請求項２】
単一のＳＩＭＤ命令を使用して前記第１の配列Ｔ１と前記第２の配列Ｔ２とを同時に更新することを特徴とする請求項１に記載の処理システム。
【請求項３】
前記プロセッサは前記モンゴメリ乗算からの中間計算値を保持するための２つの配列を維持し、前記ＳＩＭＤ命令を使用して前記２つの配列を同時に更新することを特徴とする請求項１または請求項２に記載の処理システム。
【請求項４】
前記モンゴメリ乗算は入力配列の第１の乗算と法配列の第２の乗算とを含み、前記ＳＩＭＤ命令を使用して前記第１および第２の乗算を同時に実行することを特徴とする請求項１または請求項２に記載の処理システム。
【請求項５】
前記モンゴメリ乗算は命令のループを有し、前記ループの各反復は、コピー演算を除き８つ以下のＳＩＭＤ命令を使用するステップを含むことを特徴とする請求項１または請求項２に記載の処理システム。
【請求項６】
前記ＳＩＭＤ命令は、２つのロード命令と、１つの乗算命令と、２つの加算命令と、１つのコピー命令と、１つのビットごとのＡＮＤ命令と、１つのストア命令と、１つのシフト命令とを含むことを特徴とする請求項５に記載の処理システム。
【請求項７】
モンゴメリ乗算を実施するためのコンピュータ読み取り可能記録媒体であって、
前記コンピュータ読み取り可能記録媒体は、プロセッサ上で実行されるとき、前記プロセッサにモンゴメリ乗算を実行するよう命令するコンピュータ実行可能なＳＩＭＤ命令を含み、
前記プロセッサは、暗号化機能を実行するためのものであり、前記モンゴメリ乗算は、前記暗号化機能におけるべき乗を計算するために使用されるものであり、
前記モンゴメリ乗算は、
ｍｏｎｔｍｕｌ（Ａ，Ｂ）＝ｒｅｍ（（ＡＢ−ｑＮ）／Ｒ，Ｎ）、ここでｑ＝ｒｅｍ（ＡＢ  Ｎ’，Ｒ）であり、
ＡおよびＢは整数であり、ｑは商であり、Ｎは法であり、Ｒは法Ｎと互いに素である整数であり、Ｎ’はＮＮ’≡１（ｍｏｄ  Ｒ）となるような整数であり、ｒｅｍは剰余演算であって、かつ、
前記整数Ｂおよび前記法Ｎは配列として実施され、少なくとも１つのＳＩＭＤ命令を使用して、ＡＢを計算するためのＢの倍数で第１の配列Ｔ１を更新し、ｑＮを計算するためのＮの倍数で第２の配列Ｔ２を更新するものとして定義されるものであり、
第１のレジスタは、前記ＢおよびＮの配列の要素を保持し、
第２のレジスタは、前記第１の配列Ｔ１の要素と前記第２の配列Ｔ２の要素とを保持し、
第３のレジスタは、Ｂの倍数で更新された前記第１の配列Ｔ１およびＮの倍数で更新された前記第２の配列Ｔ２の結果を保持するために使用されるものであり、
前記ＳＩＭＤ命令は、乗算ＡＢおよびｑＮの部分を同時に実行する単一のＳＩＭＤ命令を含む
ことを特徴とするコンピュータ読み取り可能記録媒体。
【請求項８】
配列ＢおよびＮの要素を前記第１のレジスタにロードするための第１のＳＩＭＤ命令と、
配列Ｔ１およびＴ２の要素を前記第２のレジスタにロードするための第２のＳＩＭＤ命令と、
第１の乗算による前記配列Ｂの要素と、第２の乗算による前記配列Ｎの要素とを乗算するための、第３のＳＩＭＤ命令と、
前記第２のＳＩＭＤ命令によってロードされた前記配列要素、および前回の反復から保存された任意の桁上げ数に、前記第３のＳＩＭＤ命令の結果を加算するための、第４および第５のＳＩＭＤ命令と、
前記第５のＳＩＭＤ命令のそれぞれの出力を、１つは配列Ｔ１およびＴ２に収まりもう１つは次の反復のための桁上げ数を表す２つの縮小された結果に分けるための第６および第７のＳＩＭＤ命令と、
メモリ内の、配列Ｔ１の要素および配列Ｔ２の要素を更新するための第８のＳＩＭＤ命令と
を含むことを特徴とする請求項７に記載のコンピュータ読取り可能記録媒体。
【請求項９】
前記ＳＩＭＤ命令はＳＳＥ２命令を含むものであることを特徴とする請求項７に記載のコンピュータ読取り可能記録媒体。
【請求項１０】
モンゴメリ乗算を実施する方法であって、
前記方法は、
モンゴメリ乗算を実行する際に使用される値で１組のレジスタを初期設定するステップであって、前記プロセッサは、暗号化機能を実行するためのものであり、前記モンゴメリ乗算は、前記暗号化機能におけるべき乗を計算するために使用されるものである、ステップと、
前記レジスタに格納された前記値について、ＳＩＭＤ命令を使用して前記モンゴメリ乗算を計算するステップと、
を含み、
前記モンゴメリ乗算は、
ｍｏｎｔｍｕｌ（Ａ，Ｂ）＝ｒｅｍ（（ＡＢ−ｑＮ）／Ｒ，Ｎ）、ここでｑ＝ｒｅｍ（ＡＢ  Ｎ’，Ｒ）であり、
ＡおよびＢは整数であり、ｑは商であり、Ｎは法であり、Ｒは法Ｎと互いに素である整数であり、Ｎ’はＮＮ’≡１（ｍｏｄ  Ｒ）となるような整数であり、ｒｅｍは剰余演算であって、かつ、
前記整数Ｂおよび前記法Ｎは配列として実施され、少なくとも１つのＳＩＭＤ命令を使用して、ＡＢを計算するためのＢの倍数で第１の配列Ｔ１を更新し、ｑＮを計算するためのＮの倍数で第２の配列Ｔ２を更新するものとして定義されるものであり、
第１のレジスタは、前記ＢおよびＮの配列の要素を保持し、
第２のレジスタは、前記第１の配列Ｔ１の要素と前記第２の配列Ｔ２の要素とを保持し、
第３のレジスタは、Ｂの倍数で更新された前記第１の配列Ｔ１およびＮの倍数で更新された前記第２の配列Ｔ２の結果を保持するために使用されるものであり、
前記ＳＩＭＤ命令は、乗算ＡＢおよびｑＮの部分を同時に実行する単一のＳＩＭＤ命令を含む
ことを特徴とする方法。
【請求項１１】
前記計算するステップは、前記暗号化機能におけるべき乗を計算するために前記モンゴメリ乗算を使用するステップを含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記計算するステップは、ＳＳＥ２命令を使用するステップを含むことを特徴とする請求項１０に記載の方法。
【請求項１３】
前記モンゴメリ乗算は命令のループを有し、前記ループの各反復は９以下のＳＩＭＤ命令を使用して実行されることを特徴とする請求項１０に記載の方法。
【請求項１４】
前記９つのＳＩＭＤ命令は、２つのロード命令と、１つの乗算命令と、２つの加算命令と、１つのコピー命令と、１つのビットごとのＡＮＤ命令と、１つのストア命令と、１つのシフト命令とを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
入力Ｂ×整数Ａの数字の積で配列Ｔ１を更新し、更新された配列Ｔ１、Ｔ２を同じ前記数字で終わらせることのできる法Ｎの倍数を決定するステップ、
前記入力Ｂと前記整数Ａの数字を乗算し、前記法Ｎと前記決定された倍数とを乗算するステップ、および
前記配列Ｔ１、Ｔ２を更新するステップを、
前記整数Ａの各数字について、右から左へと反復して実行するステップをさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１６】
前記乗算するステップは、単一のＳＩＭＤ命令によって実行されることを特徴とする請求項１５に記載の方法。
【請求項１７】
前記実行するステップの前に、前記配列Ｔ１、Ｔ２および前記法Ｎを初期設定するステップをさらに含むことを特徴とする請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＳＩＭＤ（単一命令複数データ／Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ，Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令をサポートするコンピュータアーキテクチャに関する。
【背景技術】
【０００２】
コンピュータアーキテクチャの中には、ＳＩＭＤ（単一命令複数データ）命令の実行をサポートしているものがある。こうした命令は、それぞれが複数のデータセットに対して１つの演算を実行する。実行時には、１つの演算の複数の同時インスタンス（ｓｉｍｕｌｔａｎｅｏｕｓ ｉｎｓｔａｎｃｅｓ）を使用して異なるデータを処理する。一例として、１つの命令がいくつかの独立した減算または他の数学的演算（ただし、すべて同じ演算）を実行する可能性がある。
【０００３】
インテル（登録商標）コーポレーションのペンティアム（登録商標）４マイクロプロセッサは、ＳＩＭＤ命令を実行できるコンピュータアーキテクチャの一例である。このマイクロプロセッサは、ＳＳＥ２（ストリーミングＳＩＭＤ拡張２）命令として知られる１４４の命令を使用して、レジスタに格納されたデータの演算を実行する。マイクロプロセッサには８つの１２８ビット整数レジスタがあり、２つの６４ビット整数、４つの３２ビット整数、８つの１６ビット整数、または１６の８ビット整数などの、複数のデータセットをそれぞれが保持することができる。個々のＳＳＥ２命令が、おそらくその他のレジスタからの入力と一緒に、レジスタに収容された複数のデータセットに対してそれぞれ１つの演算を実行する。ＳＳＥ２命令は、特定のプログラムタスクを実行するために使用される命令の全体数を減少させることによって、全体の性能を向上させる。
【０００４】
今日では、マイクプロセッサは多くの乗算および除算をほとんど瞬時に実行するように求められている。セキュリティは、コンピュータが多くの正確な演算を実行するように求められる１つの例である。セキュリティ機能は、多くの剰余乗算および演算を含む、べき乗（ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）演算（たとえばＲＳＡアルゴリズム）を使用することの多い、複雑な暗号アルゴリズムを採用している。  
【非特許文献１】Peter L. Montgomery, "Modular Multiplication without Trial Division", Mathematics of Computation, Volume 44, Number 170, April 1985, pp. 519-521
【非特許文献２】Donald E. Knuth, "The Art of Computer Programming", Volume 2, "Seminumerical Algorithms", Third Edition, Springer-Verlag, 1998, exercise 4.3.1-41
【発明の開示】
【発明が解決しようとする課題】
【０００５】
複雑なアルゴリズムにおける計算を少なくし、それによって性能を上げる方法を見つけることが、引き続き目標とされている。
【０００６】
モンゴメリ乗算は、除算を避ける剰余乗算に使われるよく知られたアルゴリズムである。このアルゴリズムは、倍長積を左からではなく右から減らすことによってこれを達成するものである。
【課題を解決するための手段】
【０００７】
ＳＩＭＤ命令をサポートするコンピュータシステム上で、モンゴメリ乗算を実施するためのアーキテクチャおよび方法について説明する。記載の実施では、モンゴメリ乗算によって使用されるマシンレベルの演算が、ＳＳＥ２（ストリーミングＳＩＭＤ拡張２）命令を使用して実行される。
【０００８】
なお、同じ要素および機能を参照するために、開示全体を通じて同じ参照番号を使用する。
【発明を実施するための最良の形態】
【０００９】
モンゴメリ乗算は広範囲にわたって使用される、減算のない、剰余乗算用のアルゴリズムである。以下の開示では、モンゴメリ乗算での２種類のＳＩＭＤ（単一命令複数データ）命令の使用について説明する。モンゴメリ乗算は、ＳＩＭＤ命令をサポートする様々なコンピュータアーキテクチャで実施することが可能であり、その１つの特定の実施について、２つの独立したオペランドに対して演算を行うＳＩＭＤ命令をサポートするコンピュータアーキテクチャに関連して説明する。
【００１０】
（コンピュータアーキテクチャ）
図１は、モンゴメリ乗算に対して２種類のＳＩＭＤ命令の使用を実施するように構成可能な、コンピュータアーキテクチャ１００を示す図である。コンピュータアーキテクチャ１００は、マイクロプロセッサ１０２およびメモリ１０４を含む。マイクロプロセッサ１０２は、加算および乗算などの数学的演算、ＯＲ、ＡＮＤ、ＸＯＲなどの論理演算、ならびに右および左シフトを処理するための、１つまたは複数のＡＬＵ（論理演算ユニット）１０６（１）、．．．、１０６（Ｎ）を持つ。さらにマイクロプロセッサ１０２は、ＡＬＵ１０６によって生成される中間値および最終結果を保持するための１つまたは複数のレジスタ１０８（１）、．．．、１０８（Ｍ）も含む。
【００１１】
マイクロプロセッサ１０２の一例が、インテル（登録商標）ＩＡ−３２マイクロプロセッサであり、このマイクロプロセッサ１０２は、２つのＡＬＵ１０６および８つの１２８ビット整数レジスタを持つ。レジスタ１０８は、ＸＭＭレジスタとしても知られる。インテル（登録商標）コーポレーションおよびマイクロソフト（登録商標）コーポレーションのコンパイラは、ユーザにアセンブリコードを書かせることなくこれらのＸＭＭレジスタへのユーザアクセスをサポートする。
【００１２】
コンピュータアーキテクチャ１００は、ＳＩＭＤ命令をサポートする。この例では、インテル（登録商標）ＩＡ−３２マイクロプロセッサは、ＳＳＥ２（ストリーミングＳＩＭＤ拡張２）命令をサポートする。ＳＳＥ２命令セットは、主にオーディオおよびビデオ圧縮処理を強化するものであり、ＭＰＥＧ  ２符号化およびファイル暗号化の処理を高めるための専用の、いくつかの強化機能をもたらす。ＳＳＥ２命令セットには、とりわけ１２８ビットＳＩＭＤ整数の算術演算をサポートする、１４４の命令が含まれている。ＳＳＥ２命令には、プログラムのベクトル化を支援する意図もある。たとえば、３２ビットデータの演算を行っている場合、それぞれの１２８ビットＸＭＭレジスタは４つの３２ビット値を保持することができる。ＳＳＥ２命令を使用すると、これら４つの３２ビットオペランドを単一命令で処理し、４つの３２ビット結果を得ることができる。
【００１３】
ＳＩＭＤ命令１１０のシーケンスを使用して、剰余乗算用のアルゴリズムであるモンゴメリ乗算が実施される。この命令は、通常、マイクロプロセッサ１０２内にあるように示されているが、ＡＬＵ１０６（１）〜１０６（Ｎ）のうちのいずれでも実行することができる。これらの命令は、おそらくは暗号化機能における剰余べき乗中に、モンゴメリ乗算に関係する計算を実行するように、プロセッサに命じるものである。
【００１４】
（剰余乗算およびモンゴメリ乗算）
剰余乗算およびモンゴメリ乗算入門として、一般的な除算の問題について考えてみる。ｎ１およびｎ２を整数、ｎ２＞０とする。ｎ１をｎ２で割ると、ユークリッドの除算アルゴリズムにより、以下のように一意の整数の商ｑおよび余りｒが得られる。
ｎ１＝ｑｎ２＋ｒ    （０≦ｒ＜ｎ２）
考察の目的で、数式「ｑｕｏ」および「ｒｅｍ」は以下のように定義される。
ｑｕｏ（ｎ１，ｎ２）＝ｑ（商）、および
ｒｅｍ（ｎ１，ｎ２）＝ｒ（余り）
【００１５】
剰余乗算の数学的定義は、正の整数である法（ｍｏｄｕｌｕｓ）Ｎから始まり、本明細書ではこれは一定であるものと仮定する。２つの整数ａおよびｂが与えられた場合、それらの剰余積ｍｏｄｍｕｌ（ａ，ｂ）は、ｒｅｍ（ａｂ，Ｎ）であると定義される。剰余乗算の可能な実施の１つが、下式のように最初に積ａｂを計算し、次にこの積をＮで割って、商ｑおよび余りｒを出すことである。
（１ａ）    ａｂ＝ｑＮ＋ｒ    （０≦ｒ＜Ｎ）
こうしたアルゴリズムは、余りｒ＝ｒｅｍ（ａｂ，Ｎ）＝ｍｏｄｍｕｌ（ａ，ｂ）を出力する。
【００１６】
多くのコンピュータアーキテクチャで整数除算の速度が遅いことに気付いた、本明細書で発明者とされているピーターモンゴメリは、除算を避け、単一の法で大量の計算を実行するときにより高速である、剰余乗算用の他のアルゴリズム（すなわちモンゴメリ乗算）を発見した。剰余乗算用のモンゴメリアルゴリズムに関する背景情報については、出版物（たとえば、非特許文献１および２）が対象とされる。
【００１７】
モンゴメリ乗算は、法Ｎと互いに素である固定の整数Ｒを必要とし、これは固定整数Ｒおよび法Ｎの最大公約数が１（すなわち、ｇｃｄ（Ｎ，Ｒ）＝１）であることを意味するものである。続く考察を容易にするため、法Ｎは奇数であり、整数Ｒは２の累乗であると仮定する（Ｒ＝１０を使用した例は除く）。この仮定によれば、ＮＮ’≡１（ｍｏｄ  Ｒ）の整数Ｎ’が存在する。Ｎ’の値は、Ｎ（およびＲ）にのみ依存し、法Ｎについて１回だけ計算すればよい。
【００１８】
整数ａおよびｂ（ならびに文脈上既知のＮ、Ｒ）が与えられると、モンゴメリ積ｍｏｎｔｍｕｌ（ａ，ｂ）は、０≦ｒ’＜Ｎおよび下式のように、整数ｒ’として定義される。
（１ｂ）    ａｂ≡ｒ’Ｒ    （ｍｏｄ  Ｎ）
【００１９】
この整数ｒ’は、ＲがＮを法として可逆であるので存在する（および、一意である）。モンゴメリ乗算に関する式は、以下の通りであり、
（Ｍ１）    ｍｏｎｔｍｕｌ（ａ，ｂ）＝ｒｅｍ（（ａｂ−ｑＮ）／Ｒ，Ｎ）
上式で、ｑ＝ｒｅｍ（ａｂ  Ｎ’，Ｒ）である。
【００２０】
式（Ｍ１）を検証するために、ｒ１＝（ａｂ−ｑＮ）／Ｒと定義し、この式でｒ１は整数であると見なす。この断定は、下式に従うものである。
ｑＮ≡（ａｂ  Ｎ’）Ｎ≡ａｂ（Ｎ’Ｎ）≡ａｂ    （ｍｏｄ  Ｒ）
【００２１】
次に、以下により、ｒ’≡ｒｅｍ（ｒ１，Ｎ）が数式（１ｂ）を満たすことが確認される。
ｒ’Ｒ＝ｒｅｍ（ｒ１，Ｎ）Ｒ≡ｒ１Ｒ≡ａｂ−ｑＮ≡ａｂ    （ｍｏｄ  Ｎ）
整数ｒ’はまた、「ｒｅｍ」の定義により、０≦ｒ’＜Ｎも満たすものである。
【００２２】
モンゴメリ方程式（Ｍ１）の右辺は、Ｒが２の累乗であり、かつＲが｜ａｂ−ｑＮ｜＜ＮＲを満たすように十分大きい場合では、バイナリコンピュータ上でその値を求めるのは容易である。後者は、０≦ａ，ｂ＜Ｎ＜Ｒの場合に保証される。
【００２３】
モンゴメリ積「ｍｏｎｔｍｕｌ」の有用性を確かめるために、ｔｏｍｏｎｔ（ｘ）＝ｒｅｍ（ｘＲ，Ｎ）となるように、整数ｘに対して関数「ｔｏｍｏｎｔ」を定義する。このとき、以下のようになる。
montmul(tomont(a),tomont(b))R≡tomont(a)tomont(b)    //ｍｏｎｔｍｕｌの定義
≡(aR)(bR)=(abR)R≡tomont(ab)R  (mod N)              //ｔｏｍｏｎｔの定義
【００２４】
ｇｃｄ（Ｎ，Ｒ）＝１の仮定により、この合同式をＲで割ることが可能となり、その結果以下のようになる。
montmul(tomont(a),tomont(b))≡tomont(ab)  (mod N)
【００２５】
右辺および左辺はどちらも区間［０，Ｎ−１］にあり、Ｎを法として合同であることから、等しくなければならない。ａｂ≡ｍｏｄｍｕｌ（ａ，ｂ）（ｍｏｄ  Ｎ）であり、かつ、ｘ≡ｙ（ｍｏｄ  Ｎ）のときにｔｏｍｏｎｔ（ｘ）＝ｔｏｍｏｎｔ（ｙ）であることがわかれば、以下のように結論付けられる。
montmul(tomont(a), tomont(b))= tomont(ab)= tomont(modmul(a, b))
【００２６】
したがって、ｍｏｄｍｕｌを使用して領域上の乗算を定義し、ｍｏｎｔｍｕｌを使用して像に対する乗算を定義する場合、関数「ｔｏｍｏｎｔ」は、Ｚ／ＮＺからＺ／ＮＺへの乗法準同型（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｈｏｍｏｍｏｒｐｈｉｓｍ）である（積の像が像の積であるという意味）。ここでＺ／ＮＺは、Ｎを法とする整数を表す。さらに検討すると、以下のことがわかる。
tomont(a)+ tomont(b)≡tomont(a + b)  (mod N)
tomont(a)- tomont(b)≡tomont(a - b)  (mod N)
【００２７】
したがって、関数「ｔｏｍｏｎｔ」は環準同型（１の像はｒｅｍ（Ｒ，Ｎ））である。
ａ≡ｂ（ｍｏｄ  Ｎ）のときに限り、ｔｏｍｏｎｔ（ａ）＝ｔｏｍｏｎｔ（ｂ）
であることから、関数「ｔｏｍｏｎｔ」は準同型であるだけでなく、Ｚ／ＮＺからＺ／ＮＺへの環同型である。
【００２８】
（多倍長（ｍｕｌｔｉｐｌｅ−ｐｒｅｃｉｓｉｏｎ）モンゴメリ乗算）
これまでモンゴメリ乗算について紹介してきたが、この項では、モンゴメリ乗算での多倍長数の使用について例示する。考察を目的として、暗号化機能での剰余乗算の使用を考えてみる。たとえばＲＳＡ暗号システムでは、法が５１２ビット、１０２４ビット、またはそれ以上の可能性がある、剰余べき乗を必要とする。ほとんどのコンピュータアーキテクチャは、３２×３２→６４ビット、または６４×６４→１２８ビットの積しかサポートしていない。より長い数を乗算するとき、それぞれのオペランドはいくつかのより小さい（通常は３２ビットまたは６４ビット）部分に分割される。
【００２９】
コンピュータのワードサイズに応じて、ｒ＝２３２または２６４としてみよう。ｒｋ＞Ｎとなるような正の整数ｋを探しなさい（通常は、この制約に従ってできる限り小さなｋを選択する）。そして、Ｒ＝ｒｋに設定する。
【００３０】
この考察では、以下に、Ａなどの大文字を使用して負でない多倍長数を表している。Ｎまでの値は、ｋ個の基数ｒの数字で表すことができる。これらの数字は同じ文字で書き表され、その後に大括弧で囲まれたインデックスが続く。０≦ｊ≦ｋ−１のとき、Ａ［ｊ］は基数ｒにおけるＡのｊ番目の数字を示す（０番目の数字が最下位である）。すなわち、
【００３１】
【数１】
0004662744.tif 000002
【００３２】
となる。これを書き表す他の方法は、Ａ＝（Ａ［ｋ−１］Ａ［ｋ−２］．．．Ａ［０］）ｒであり、この式で最後の下付き文字は基数ｒを示す。
【００３３】
これらの表記法が与えられた場合、０≦Ａ，Ｂ＜Ｎ＜Ｒでのｍｏｎｔｍｕｌ（Ａ，Ｂ）用のアルゴリズムの１つは、以下のとおりである。
T1:= 0;
T2:= 0;
DISCARD:= 0;
for j from 0 to k-1 do
mul1:= A[j];
T1:= T1 + mul1 * B;                   //Temporarily need k+1 digits
tlow:= T1[0];                        //tlow:=rem(T1,r)
T1:= (T1 - tlow)/r;                  //T1:=quo(T1,r)
DISCARD:= DISCARD + tlow * rj;       //For presentation purposes
mul2:= rem((tlow - T2[0])* N'[0],r);  //So new T2 will be an integer
T2:= (T2 + mul2 * N - tlow)/r;
end for;
return rem(T1-T2,N);
【００３４】
帰納法によって確かめると、各反復の終わりに以下のことがわかる。
０≦Ｔ１＜Ｂ
０≦Ｔ２＜Ｎ
０≦ＤＩＳＣＡＲＤ＜ｒｊ＋１
Ｔ１ｒｊ＋１＋ＤＩＳＣＡＲＤ＝（Ａ［ｊ］Ａ［ｊ−１］．．．Ａ［０］）ｒ＊Ｂ
Ｔ２ｒｊ＋１＋ＤＩＳＣＡＲＤ≡０  （ｍｏｄ  Ｎ）
【００３５】
そして、次の２つの結果が得られる。  
-N < T1 - T2 < B
(T1 - T2)rj+1+≡(A[j]A[j-1]...A[0])r * B  (mod N)
【００３６】
最後の反復（ｊ＝ｋ−１）が完了すると、次のような結果になる。  
−Ｎ＜Ｔ１−Ｔ２＜Ｂ＜Ｎ
（Ｔ１−Ｔ２）Ｒ≡ＡＢ  （ｍｏｄ  Ｎ）
【００３７】
したがって、関数ｍｏｎｔｍｕｌ（Ａ，Ｂ）は、Ｔ１−Ｔ２（Ｔ１≧Ｔ２のとき）またはＴ１−Ｔ２＋Ｎ（Ｔ１＜Ｔ２のとき）となる。
【００３８】
わずかに修正することで、変数Ｔ１およびＴ２をほとんど同様に更新することができる。ｔｌｏｗおよびｍｕｌ２の初期設定を少し変更すると、メインループは以下のようになる。  
ｆｏｒ  ｊ  ｆｒｏｍ  ０  ｔｏ  ｋ−１  ｄｏ
ｍｕｌ１：＝Ａ［ｊ］；
ｔｌｏｗ：＝ｒｅｍ（Ｔ１［０］＋ｍｕｌ１＊Ｂ［０］，ｒ）；
ｍｕｌ２：＝ｒｅｍ（（ｔｌｏｗ−Ｔ２［０］）＊Ｎ’［０］，ｒ）；
Ｔ１：＝（Ｔ１＋ｍｕｌ１＊Ｂ−ｔｌｏｗ）／ｒ；
Ｔ２：＝（Ｔ２＋ｍｕｌ２＊Ｎ−ｔｌｏｗ）／ｒ；
ｅｎｄ  ｆｏｒ；
【００３９】
このように書き換えると、Ｔ１の更新はＢの倍数を加え、Ｔ２の更新はＮの倍数を加える。Ｔ１、Ｔ２、Ｂ、およびＮの配列は、多倍長数≦Ｎ＜Ｒ＝ｒｋを表し、ここではすべてが、数が基数ｒで書き表されるとき長さｋをもつ。乗数ｍｕｌ１およびｍｕｌ２は単精度である（すなわち０≦ｍｕｌ１、ｍｕｌ２＜ｒ）。Ｔ１を更新するのに必要な命令は、Ｔ２を更新するのに必要な命令に非常によく似ている。したがって、Ｔ１およびＴ２の両方を（ＢおよびＮが多倍長であることを考慮して）更新するための命令シーケンスは以下のようになる。  
[Update Code 1]
sum1:= T1[0]+ mul1 * B[0];           //0≦sum1≦r2-r
//Use rem(sum1, r) = tlow to compute
mul2(formula suppressed here)
sum2: =T2[0]+ mul2 * N[0];
sum1: =quo(sum1, r);                //0≦sum1≦r-1
sum2: =quo(sum2, r);
for i from 1 to k-1 do
sum1:= sum1 + T1[i]+ mul1 * B[i];  //0≦sum1≦r2-1
sum2:= sum2 + T2[i]+ mul2 * N[i];
T1[i-1]:= rem(sum1, r);
T2[i-1]:= rem(sum2, r);
sum1:= quo(sum1, r);              //0≦sum1≦r-1
sum2:= quo(sum2, r);
end for;
T1[k-1]:= sum1;
T2[k-1]:= sum2;
現代のコンピュータアーキテクチャはパイプライン方式および命令レベル並列処理をサポートしており、ここでは配列Ｔ１の更新に関する演算に続いて、配列Ｔ２の更新に関する演算が行われる。性能をさらに向上させるためには、更新ペアにつき１つの命令を使用して、ｉにわたるループ内で配列Ｔ１およびＴ２を一緒に更新することが望ましい。
【００４０】
（モンゴメリ乗算用のＳＩＭＤ命令）
図１に示されたコンピュータアーキテクチャ１００は、ＳＩＭＤ命令１１０を使用して（ここでの特定の例ではＳＳＥ２命令を使用して）、モンゴメリ乗算、ｍｏｎｔｍｕｌ（Ａ，Ｂ）で使用される配列Ｔ１およびＴ２を同時に更新する。この処理には、部分的に、右から左へＡの数字（ｄｉｇｉｔｓ）を処理すること、ならびに、配列Ｔ１およびＴ２の更新に使用されるＢ（すなわちｍｕｌ１＊Ｂ［ｉ］）および法Ｎ（すなわちｍｕｌ２＊Ｎ［ｉ］）を含む乗算の結果をインタリーブすることが含まれる。これについては、以下でより詳細に説明する。
【００４１】
前述のように、ＳＳＥ２命令はプログラムのベクトル化を支援するものであり、複数のデータセットを単一のレジスタ内に保持することができる。この点を例示するために、３２ビットデータを含む演算に対して、１２８ビットレジスタ１０８はそれぞれ４つの３２ビット値を保持することができる。そこで、以下のようにループを書き表すことができる。
int32 x[100], y[100], z[100];  //Assume int32 data type occupies 32bits
for i from 0 to 99 do
z[i]:= x[i]+ y[i];
end for;
このループは（プログラマまたはコンパイラによって）部分的に展開することができ、生成されるコードは以下のようになる。
ｉｎｔ３２  ｘ［１００］，ｙ［１００］，ｚ［１００］；
ｆｏｒ  ｉ４  ｆｒｏｍ  ０  ｔｏ  ９６  ｂｙ  ４  ｄｏ
ｚ［ｉ４］：＝ｘ［ｉ４］＋ｙ［ｉ４］；
ｚ［ｉ４＋１］：＝ｘ［ｉ４＋１］＋ｙ［ｉ４＋１］；
ｚ［ｉ４＋２］：＝ｘ［ｉ４＋２］＋ｙ［ｉ４＋２］；
ｚ［ｉ４＋３］：＝ｘ［ｉ４＋３］＋ｙ［ｉ４＋３］；
ｅｎｄ  ｆｏｒ；
【００４２】
１つのＳＳＥ２命令は、４つの３２ビットデータ値（ｘ［ｉ４＋３］、ｘ［ｉ４＋２］、ｘ［ｉ４＋１］、ｘ［ｉ４］）を、隣接するメモリ位置からＸＭＭレジスタにロードする。他のＳＳＥ２命令は、（ｙ［ｉ４＋３］、ｙ［ｉ４＋２］、ｙ［ｉ４＋１］、ｙ［ｉ４］）を、異なるＸＭＭレジスタにロードする。単一のＰＡＤＤＤ命令は、４つの３２ビット合計のすべてを以下のように形成する。
(x[i4+3]+ y[i4+3], x[i4+2]+ y[i4+2], x[i4+1]+ y[i4+1], x[i4]+ y[i4])
次に４つの合計は、配列ｚの連続する位置に入れられる。４つの配列要素を一度に処理することによって、ループ反復回数が４分の１に（１００から２５に）減らされる。その他の効果は、コンパイラがループインデックスｉ４および配列アドレスｘ、ｙ、ｚを保持するために、それらのレジスタにｘ［ｉ４］などのデータ値を散乱させず４つの３２ビットレジスタを予約できることである。
【００４３】
モンゴメリ乗算の場合、ＳＳＥ２命令を使用して配列Ｔ１およびＴ２を一緒に更新する。最後の例では、４つの３２ビット整数値が一度に処理されたのに対して、ここでは、ＳＳＥ２命令を使用して２つの６４ビット値が処理される。続く例では、基数ｒ＝２３２と仮定する。この実施については、レジスタおよびＳＳＥ２コマンドの例を示す図２を参照しながら説明する。
【００４４】
上述の擬似コード［Ｕｐｄａｔｅ  Ｃｏｄｅ  １］を見ると、ｓｕｍ１およびｓｕｍ２の値は常に区間［０，ｒ２−１］＝［０，２ｒ６４−１］の中にある。１つのＸＭＭレジスタ１０８（１）を使用して両方の６４ビット値（ｓｕｍ１、ｓｕｍ２）を保持する。他のＸＭＭレジスタ１０８（２）、１０８（４）、および１０８（５）（またはメモリ位置）は、以下の６４ビット値のペア（ｐａｉｒｓ）を保持することになる。
（ｍｕｌ１，ｍｕｌ２）
（Ｂ［ｉ］，Ｎ［ｉ］）    （０≦ｉ≦ｋ−１）
（Ｔ１［ｉ］，Ｔ２［ｉ］）  （０≦ｉ≦ｋ−１）
【００４５】
ｍｕｌ１、ｍｕｌ２、Ｂ［ｉ］、Ｎ［ｉ］、Ｔ１［ｉ］、Ｔ２［ｉ］の数値はすべて３２ビットに収まるが、それぞれに６４ビットが割り当てられる。定数（ｒ−１，ｒ−１）も使用され、これは１６進法で００００００００ＦＦＦＦＦＦＦＦ００００００００ＦＦＦＦＦＦＦＦである。この定数はレジスタ１０８（３）に保持される。
【００４６】
これらのデータレイアウトがいったん選択されると、擬似コード［Ｕｐｄａｔｅ  Ｃｏｄｅ  １］の内部ループは容易に変換される。前述のように、８つのＸＭＭレジスタの内の３つの１０８（１）、１０８（２）、および１０８（３）は、ペア（ｓｕｍ１，ｓｕｍ２）、（ｍｕｌ１，ｍｕｌ２）、および（ｒ−１，ｒ−１）を保持する。これら３つのレジスタはすべて内部ループを開始する前に初期設定される。内部ループ本体は、図２の２つのロード命令ＩＮＳＴ１：ＬＯＡＤおよびＩＮＳＴ２：ＬＯＡＤで表されるように、ペア（Ｂ［ｉ］，Ｎ［ｉ］）および（Ｔ１［ｉ］，Ｔ２［ｉ］）をＸＭＭレジスタ１０８（４）および１０８（５）にロードする。
【００４７】
２つの３２ビット値を掛け合わせて６４ビットの符号無し積（すなわち、３２×３２→６４ビットの符号無し積）を生成する、１つのＳＳＥ２命令「ＰＭＵＬＵＤＱ」は、ｍｕｌ１＊Ｂ［ｉ］およびｍｕｌ２＊Ｎ［ｉ］の両方の演算を実行する（すなわち、図２のＩＮＳＴ３：ＰＭＵＬＵＤＱ）。次に、２つの６４ビット値を加える２つのＳＳＥ２命令「ＰＡＤＤＱ」を使用して、
ｓｕｍ１：＝ｓｕｍ１＋Ｔ１［ｉ］＋ｍｕｌ１＊Ｂ［ｉ］；
ｓｕｍ２：＝ｓｕｍ２＋Ｔ２［ｉ］＋ｍｕｌ２＊Ｎ［ｉ］；
が得られ、更新された（ｓｕｍ１，ｓｕｍ２）は他のＸＭＭレジスタ１０８（６）に配置される（すなわち、図２のＩＮＳＴ４：ＰＡＤＤＱおよびＩＮＳＴ５：ＰＡＤＤＱ）。コピー動作（すなわち、ＩＮＳＴ６：ＭＯＶＤＱＡ）によって（ｓｕｍ１，ｓｕｍ２）の複製が作られる。次に、（ｒ−１，ｒ−１）を使用する１つのＳＳＥ２命令「ＰＡＮＤ」（すなわち、１２８ビットのＡＮＤであり、これは２つの６４ビットのＡＮＤと同じである）（すなわち、ＩＮＳＴ７：ＰＡＮＤ）およびストア動作（すなわち、ＩＮＳＴ８：ＳＴＯＲＥ）は、以下の関数を実行する。
Ｔ１［ｉ−１］：＝ｒｅｍ（ｓｕｍ１，ｒ）
Ｔ２［ｉ−１］：＝ｒｅｍ（ｓｕｍ２，ｒ）
ＰＡＮＤは、（ｓｕｍ１，ｓｕｍ２）の一方のコピーを破棄するが、他方は保持される。次に、３２ビットごとのＳＳＥ２演算「ＰＳＲＬＱ」（すなわちゼロ充てん（ｚｅｒｏ  ｆｉｌｌ）された右シフト６４ビットデータ）により、以下の結果が与えられる（すなわち、ＩＮＳＴ９：ＰＳＲＬＱ）
ｓｕｍ１：＝ｑｕｏ（ｓｕｍ１，ｒ）
ｓｕｍ２：＝ｑｕｏ（ｓｕｍ２，ｒ）
【００４８】
アドレス計算およびループ制御に関する命令（ＸＭＭレジスタではなく３２ビットレジスタを使用する）を除き、内部ループ本体は、配列Ｔ１の１つの要素およびアレイＴ２の対応する要素を更新するために、２つのロード、１つの乗算、２つの加算、１つのコピー、１つのビットごとのＡＮＤ、１つのストア、１つのシフトという、９つのＳＳＥ２命令のみが必要である。マイクロソフト（登録商標）  Ｖｉｓｕａｌ  Ｓｔｕｄｉｏ  ．ＮＥＴ（登録商標）およびインテル（登録商標）のＩＡ−３２コンパイラは、ユーザがアセンブリ言語を使用せずにこの種のコードを生成できるようにする固有性（ｉｎｔｒｉｎｓｉｃｓ）を有する。
【００４９】
Ｂ［ｉ］は、配列Ｂの乗数であるＡの数字（ｄｉｇｉｔｓ）を右から左へ処理することが可能なように、ｉ＝０からｉ＝ｋ−１の順に処理されることに留意されたい。Ａにわたるループの反復ごとに、Ｂがすべて再処理される。また、乗算ｍｕｌ１＊Ｂ［ｉ］には、ｉの進行に従って乗算ｍｕｌ２＊Ｎ［ｉ］をインタリーブすることが可能であり、その結果、計算が再編成されることにも留意されたい。それでもなおこの処理は、以下でより詳細に示すように、所望の最終結果を効率的に生成する。
【００５０】
（メモリレイアウト）
ＳＳＥ２ロード命令（ＭＯＶＤＱＡ）は、データがメモリの中で連続してロードされることを要求するため、前述の擬似コード［Ｕｐｄａｔｅ  Ｃｏｄｅ  １］は、Ｂ［ｉ］およびＮ［ｉ］が隣接する６４ビットワードにあることを仮定している。さらにこのメモリは、１６バイト境界上で整列しなければならない。しかし、ｍｏｎｔｍｕｌ（Ａ，Ｂ）が呼び出されると、入力Ｂ［０］からＢ［ｋ−１］は通常、連続する３２ビットワードからなる１つの配列に入り（４バイト境界上で整列され）、Ｎ［０］からＮ［ｋ−１］は、他のこうした配列に入ることになる。これは所望のメモリパターンではない。したがって、追加のループ初期設定を実行して所望の配列レイアウトを生成するように、コンピュータを実装することができる。
【００５１】
問題は、ＢおよびＮの配列を、１２８ビット要素を備えた（および適切に整列された）１つの一時配列にインタリーブすることによって回避される。そのコピーは、初期にｍｏｎｔｍｕｌの中に作成することができる。ｋが大きい場合、コピーされた要素の各ペアに後でｋ回アクセスすることになるため、これらのコピーのコストは無視できるほどのものである。
【００５２】
同様に、配列Ｔ１およびＴ２の要素を、１２８ビット要素を備えた配列内にインタリーブすることができる。最終的なｒｅｍ（Ｔ１−Ｔ２，Ｎ）の計算は、その出力を標準形式（すなわち、隣接する３２ビットワード）で格納することになる。
【００５３】
（演算）
図３は、モンゴメリ乗算でＳＩＭＤ命令を使用するための処理３００を示す図である。処理３００は、たとえばコンピュータアーキテクチャ１００によって実行することが可能であり、以下では、図１および２の両方を参照しながら説明する。処理３００は一連のブロックとして示されており、それぞれのブロックはコンピュータアーキテクチャによって実行される演算または機能を表す。これらの演算または機能は、ソフトウェア、ファームウェア、および／またはハードウェアで実行可能である。また、そのようなものとして、このブロックを使用し、実行時に、記載の機能を実行する、媒体上に格納された命令を表すことができる。
【００５４】
ブロック３０２では、関数ｍｏｎｔｍｕｌ（Ａ，Ｂ）の計算に使用される値が初期設定される。これらの値には、整数入力Ａ、Ｂ、一時配列Ｔ１、Ｔ２、および法Ｎが含まれる。ブロック３０４では、一時アレイＴ１、Ｔ２がゼロに設定される。入力Ｂおよび法Ｎの値は１つのベクトルにインタリーブされ、これらの配列からの要素のペアはレジスタの１つ（たとえば、図２のレジスタ１０８（４））に収められる。
【００５５】
ブロック３０６では反復ループが始まり、入力Ａの数字を右から左へと処理する。ブロック３０８では、配列Ｔ１が入力Ｂの倍数で更新される（乗数ｍｕｌ１は配列Ａからの１つの数字である）と仮定し、プロセッサは、法Ｎのどの倍数ｍｕｌ２が、更新配列Ｔ１、Ｔ２を同じ数字で終わらせることができるかを決定する。ブロック３１０では、（Ａの数字）×Ｂ（すなわち、擬似コードＵｐｄａｔｅ  Ｃｏｄｅ  １中のｍｕｌ１＊Ｂ［ｉ］）の乗算と、先に決定された倍数×法Ｎ（すなわち、擬似コード  Ｕｐｄａｔｅ  Ｃｏｄｅ  １中のｍｕｌ２＊Ｎ［ｉ］）の乗算が実行される。ブロック３１２では、配列Ｔ１、Ｔ２が更新される。２つの配列Ｔ１およびＴ２を使用することによって、モンゴメリ乗算で乗算ＡＢに乗算ｑＮがインタリーブされる。ループは決定ブロック３１４で表されるように、入力Ａのすべての数字が処理されるまで続行する。ブロック３１６では、結果Ｔ１−Ｔ２（ｍｏｄ  Ｎ）が戻される。
【００５６】
（ｍｏｎｔｍｕｌ計算でのループ再構築の例示）
次に、モンゴメリ関数ｍｏｎｔｍｕｌの一例について、実際的であるが仮想のデータを使用して説明する。まず、ｍｏｎｔｍｕｌ計算に対する所望の回答を導出し、続いて、この結果が上記の技法を使用してどのように得られるかについて論じる。
【００５７】
Ａ＝１２３およびＢ＝４５６とすると、問題は、Ｒ＝１０００（１０進数）およびＮ＝７８９でｍｏｎｔｍｕｌ（１２３，４５６）を計算することである。定義により、出力は整数ｒ’となり、０≦ｒ’＜７８９および下式を満たす。
１２３＊４５６≡１０００ｒ’  （ｍｏｄ  ７８９）
ＮＮ’≡１（ｍｏｄ  Ｒ）を解くと、整数Ｎ’は１０９であることがわかる（すなわち、７８９Ｎ’≡１（ｍｏｄ  １０００）であり、Ｎ’＝１０９が導かれる）。前に法Ｎ＝７８９が使用された場合、関係７８９Ｎ’≡１（ｍｏｄ  １０００）を１回解いて、Ｎ’＝１０９を得ることができる。この結果をチェックするには、この関係にＮ’＝１０９を代入。すると、関係７８９＊１０９＝８６００１となり、ｍｏｄ  Ｒ＝１０００の結果が００１になる。法７８９を初めて使用するのであれば、拡張ユークリッドアルゴリズムを使用することができることに留意されたい。
【００５８】
次に、上記で導出されたモンゴメリ乗算関数［Ｍ１］（すなわち、ｍｏｎｔｍｕｌ（Ａ，Ｂ）＝ｒｅｍ（（ＡＢ−ｑＮ）／Ｒ，Ｎ）、ただしｑ＝ｒｅｍ（ＡＢ  Ｎ’，Ｒ））を使用して、積ＡＢが算出され、５６，０８８が生成される（すなわち、１２３＊４５６＝５６，０８８）。先行ゼロが挿入され（すなわち０５６０８８）、２つの３桁数の積を保持するために６つの数字が形成される。Ｒ＝１０００を法とすると、この結果の最後の３桁は０８８である。商ｑをみつけるために、結果の０８８に整数Ｎ’＝１０９を掛けて、９５９２を生成する（すなわち、０８８＊１０９＝９５９２）。もう一度Ｒ＝１０００を法とすると、この結果の末尾３桁は５９２である（すなわち、ｑ＝５９２）。商ｑ＝５９２に法Ｎ＝７８９を掛け合わせ、積１２３＊４５６から引く（すなわち、ＡＢ−ｑＮ）と、以下のようになる。
０５６０８８−５９２＊７８９＝０５６０８８−４６７０８８＝−４１１０００
説明により、この結果は０００となる。値−４１１０００をＲで割る（すなわち、「ｒｅｍ」関数における第１の要素である（ＡＢ−ｑＮ）／Ｒを形成する）と、最終結果は−４１１である。これらの結果をモンゴメリ関数ｍｏｎｔｍｕｌに戻すと、以下のような最終の所望の答えが得られる。  
ｍｏｎｔｍｕｌ（１２３，４５６）＝ｒｅｍ（−４１１，７８９）＝３７８
【００５９】
この所望の答えを基準にして、本項の残りの部分では、ＳＩＭＤ命令を使用する上述の多倍長の実施における値の例を使用する。ここで説明する多倍長バージョン（ｒ＝１０およびｋ＝３を使用する）は、３つのゼロすべてを一度に挿入するのではなく、余りの末尾に１つのゼロ数字を３回挿入することを目的とする。これは、１の位の数字で始まり、１００の位の数字で終わるように、部分的に、入力Ａの数字を右から左へ処理していくことで実行される。
【００６０】
Ｎ’＝１０９のとき、下位の数字はＮ’［０］＝９である。積ＡＢ、すなわち０５６０８８の下位の数字は８である。したがって、積０５６０８８＊Ｎ’は、結果として８＊９＝７２と同じ数字で終わる。最後の数字は２であるので、積ＡＢ（すなわち０５６０８８）から法Ｎ（すなわち７８９）を２回を引くと、以下のようになる。
０５６０８８−２＊７８９＝０５６０８８−１５７８＝０５４５１０
【００６１】
次のステップでは、結果として得られた値０５４５１０の１０の位の数字１に注目する。（末尾のゼロを削除した後の）積０５４５１＊Ｎは、１＊９＝９と同じ数字で終わる。したがって、１０の位の数字の処理を確実にするために１つの末尾のゼロをプレースホルダとして（すなわち７８９０）、結果の０５４５１０から法Ｎ（すなわち７８９）を９回引くことを決定すると、以下のようになる。
０５４５１０−９＊７８９０＝０５４５１０−７１０１０＝−０１６５００
【００６２】
この結果の１００の位の数字５に対してこのステップをもう一度繰り返すと、積−０１６５＊Ｎ（２つの末尾のゼロを削除）は、５＊９＝４５と同じ数字で終わり、最後の数字は５である。２つの末尾のゼロをプレースホルダとして（すなわち７８９００）、結果の−０１６５００から法Ｎ（すなわち７８９）を５回引くと、以下のようになる。
−０１６５００−５＊７８９００＝−０１６５００−３９４５００＝−４１１０００
【００６３】
前述のように、出力は、ｍｏｎｔｍｕｌ（１２３，４５６）＝ｒｅｍ（−４１１，７８９）＝３７８である。ここで、０５６０８８から、２＊７８９、９＊７８９０、および５＊７８９００を引いて、以前に０５６０８８から５９２＊７８９を引いたときと同じ結果が得られた。
【００６４】
２つの一時配列Ｔ１およびＴ２を使用することで、乗算ＡＢ（すなわち１２３＊４５６＝０５６０８８）を減算ＡＢ−ｑＮ（すなわち０５６０８８−５９２＊７８９）でインタリーブして、結果の−４１１０００を得ることができる。乗算ＡＢを計算するために４５６の倍数を配列Ｔ１に加算し、減算ｑＮを計算するために７８９の倍数を配列Ｔ２に加算することになる。Ｔ１およびＴ２はどちらも非負のままとなる。Ｔ１＝Ｔ２＝０に初期設定し、以下のように、乗算ＡＢすなわち１２３＊４５６が、１２３の下位の数字すなわち３を基点として始まる。
Ｔ１＝Ｔ１＋３＊４５６＝０＋１３６８＝１３６８
【００６５】
現在のＴ２＝０は、ゼロで終わる。配列Ｔ１＝１３６８の現在の最後の数字と同じく配列Ｔ２が８で終わるようにするために、以下のように法Ｎ（すなわち７８９）を２倍にすることが決定される（すなわち２＊９＝１８で結果は８で終わり、０に加えると８に等しくなる）。
Ｔ２＝Ｔ２＋２＊７８９＝０＋１５７８＝１５７８
【００６６】
配列Ｔ１およびＴ２の両方で末尾の８の数字を捨てる（すなわち、ループ不変式についてＤＩＳＣＡＲＤ＝８）と、次のようになる。
Ｔ１＝１３６    Ｔ２＝１５７
【００６７】
Ａ＝１２３における次の数字（右から処理）は２である。
Ｔ１＝Ｔ１＋２＊４５６＝１３６＋９１２＝１０４８
現在のＴ２＝１５７は７になる。配列Ｔ１＝１０４８の現在の最後の数字と同じく配列Ｔ２が８になるようにするために、以下のように法Ｎ（すなわち７８９）を９倍にすることが決定される（すなわち９＊９＝８１で１で終わり、７に加えると８に等しくなる）。
Ｔ２＝Ｔ２＋９＊７８９＝１５７＋７１０１＝７２５８
【００６８】
配列Ｔ１およびＴ２の両方で末尾の８の数字を捨てる（すなわち、ループ不変式についてＤＩＳＣＡＲＤ＝８８）と、次のようになる。
Ｔ１＝１０４    Ｔ２＝７２５
【００６９】
Ａ＝１２３における最後の数字（右から処理）は１である。
Ｔ１＝Ｔ１＋１＊４５６＝１０４＋４５６＝５６０
現在の配列Ｔ２＝７２５の最後の数字は５である。配列Ｔ１＝５６０の現在の最後の数字と同じく配列Ｔ２が０になるようにするために、以下のように法Ｎ（すなわち７８９）を５倍にすることが決定される（すなわち５＊９＝４５で結果は５になり、５に加えると１０に等しくなって結果は０となる）。
Ｔ２＝Ｔ２＋５＊７８９＝７２５＋３９４５＝４６７０
【００７０】
配列Ｔ１およびＴ２の両方で末尾の０の数字を捨てる（すなわち、ループ不変式についてＤＩＳＣＡＲＤ＝０８８）と、次のようになる。
Ｔ１＝５６    Ｔ２＝４６７
Ｔ１＝５６が、１２３＊４５６＝５６０８８の先行数字をもち、Ｔ２＝４６７が５９２＊７８９＝４６７０８８の先行数字をもつことに注目されたい。共有される末尾数字はＤＩＳＣＡＲＤ＝０８８にある。出力は以下のようになる。
montmul(123,456)=rem(56-467,789)=rem(-411,789)=378
【００７１】
計算は再編成されたが、処理は同じ最終結果を生成したことに留意されたい。６つの加数（ｓｕｍｍａｎｄ）が以下のように異なる順序で加えられた。
００３＊４５６＝  ００１３６８
０２０＊４５６＝  ００９１２０
１００＊４５６＝  ０４５６００
−００２＊７８９＝−００１５７８
−０９０＊７８９＝−０７１０１０
−５００＊７８９＝−３９４５００
−−−−−−−−
−４１１０００
【００７２】
前述のコンピュータアーキテクチャ１００でＳＩＭＤ命令を使用すると、配列Ｔ１およびＴ２が一緒に更新される。たとえば、以下の両方を同時に実行することができる。
Ｔ１＝１３６＋２＊４５６＝１０４８
Ｔ２＝１５７＋９＊７８９＝７２５８
まず、Ｔ１の更新：６＋２＊６＝１８の末尾（すなわち１の位）の数字に注目する。これは８で終わるが、１５７は結果として７になるため、Ｔ２の更新における７８９の乗数は（８−７）Ｎ’［０］≡９（ｍｏｄ  １０）となる。この乗数がいったん決定されると、Ｔ２の更新の末尾の数字は７＋９＊９＝８８となることがわかる。１８と８８において（共有された）末尾の８を捨てて、桁上げ（ｃａｒｒｉｅｓ）ベクトルを高位の数字（１，８）に初期設定する。
【００７３】
Ｔ１の更新およびＴ２の更新を進めるが、ＳＩＭＤ命令を使用してそれらを一緒に行い、次のステップで、以下のように入力の１０の位（下付き文字１）を処理する。
temp=carries +(T1[1],T2[1])+(2,9)*(B[1],N[1])
=(1,8)+(3,5)+(2,9)*(5,8)
=(14,85)
ｔｅｍｐの２つの要素は０から９９までの整数である。末尾の数字（４，５）は（Ｔ１［０］，Ｔ２［０］）の新しい値として保存され、上位の数字は桁上げベクトルに置かれる（すなわち、ｃａｒｒｉｅｓ＝（１，８））が、これは偶然に桁上げベクトルの古い値と同じである。
【００７４】
１００の位でも同様に実行する。
temp=carries +(T1[2],T2[2])+(2,9)*(B[2],N[2])
=(1,8)+(1,1)+(2,9)*(4,7)
=(10,72)
【００７５】
末尾の数字（０，２）は（Ｔ１［１］，Ｔ２［１］）の新しい値として保存され、上位の数字は桁上げベクトルに置かれる（すなわち、ｃａｒｒｉｅｓ＝（１，７））。
【００７６】
これで入力Ａ＝１２３のすべての数字を使い尽くした。桁上げベクトルの内容（すなわちｃａｒｒｉｅｓ＝（１，７））は（Ｔ１［２］，Ｔ２［２］）の新しい値として保存される。新しい値（最後の８はすでに捨てられている）はＴ１＝１０４およびＴ２＝７２５である。
【００７７】
ｔｅｍｐ計算への入力は０から９までの整数であり、出力は０から９９までの範囲にある。ハードウェアレジスタ１０８に対して、これは０から２３２−１の入力および０から２６４−１の出力に対応する。（Ｔ１［２］，Ｔ２［２］）をメモリから参照すると、オペランドは隣接する位置にあるが、これは前回の反復でオペランドがどのように格納されたかによるものである。より詳しく言えば、たとえオペランドの値が３２ビットに収まるものであっても、隣接する６４ビット位置に格納される。初期に、（Ｂ［２］，Ｎ［２］）のようなペアが隣接する位置にコピーされ、Ａ＝１２３の各数字が処理されるときに再使用される。
【００７８】
（ソースコード例）
擬似コード［Ｕｐｄａｔｅ  Ｃｏｄｅ  １］を実施するためのソースコードの例を以下に示す。
【００７９】
マクロの中にはこのコード内で参照されるものもあるが、ここでは定義しない。ｐｔｒ＿ｒｏｕｎｄｕｐ＿ｍ１２８ｉ（ｔｅｍｐｓ）は、４バイト境界上で整列された一時配列アドレスを取り、ｔｅｍｐｓ、ｔｅｍｐｓ＋４、ｔｅｍｐｓ＋８、ｔｅｍｐｓ＋１２のうち、１６バイト境界上で整列されたものすべてを戻す。１２８ビット値ｘが与えられると、ＳＳＥ２＿ｄｉｇｉｔ２（ｘ）マクロはｘの６３〜３２ビットの値を戻し、ＳＳＥ２＿ｄｉｇｉｔ０（ｘ）マクロはｘの３１〜０ビットの値を戻す。
【００８０】
ｄｉｇｉｔ＿ｔ、ｄｉｔｉｇ＿ｔｃ、ＤＷＯＲＤＲＥＧ、ＤＷＯＲＤＲＥＧＣはすべて３２ビット型である。末尾の「ｃ」または「Ｃ」は定数オペランドを識別するものである。
【００８１】
ここで、変数の対応関係の一部を示す。
Ｔｅｘｔ                      ｍｏｄｍｕｌ＿ｆｒｏｍ＿ｒｉｇｈｔ＿ＳＳＥ２
Ａ，Ｂ                        ｂ，ａ
Ｎ                            ｍｏｄｕｌｕｓ
Ｎ’［０］                    ｍｉｎｖ
ｋ                            ｌｎｇ
（Ｂ［ｉ］，Ｎ［ｉ］）        ａ＿ｍｏｄｕｌｕｓ［ｉ］
（Ｔ１［ｉ］，Ｔ２［ｉ］）      ｔｅｍｐ１２［ｉ］
（２３２−１，２３２−１）        ｍａｓｋ０２
（ｍｕｌ１，ｍｕｌ２）          ｍｕｌ１２
（ｓｕｍ１，ｓｕｍ２）          ｐｒｏｄ１２またはｃａｒｒｙ１２
【００８２】
ｍｕｌ２の計算、Ｔ２に加算されるＮの倍数は、通常以下のようになる。
ｍｕｌ２＝（Ｔ１［０］＋ｍｕｌ１＊Ｂ［０］−Ｔ２［０］）＊Ｎ’（ｍｏｄ  ｒ）
この式では、Ｎ’による乗算を開始する前に、乗算ｍｕｌ１＊Ｂ［０］を完了している必要がある。代わりにソースコードは、Ｂ［０］＊Ｎ’（ｍｏｄ  ｒ）を予め計算して以下を使用する。
mul2 =(T1[0]- T2[0])* N'+ mul1 *(B[0]* N')(mod r)
修正されたｍｕｌ２式により、ハードウェアがこうした計算をパイプライン化する場合、２つの整数乗算をオーバラップさせることができる。
【００８３】
【表１−１】
0004662744.tif 000003
【００８４】
【表１−２】
0004662744.tif 000004
【００８５】
【表１−３】
0004662744.tif 000005
【００８６】
【表１−４】
0004662744.tif 000006
【００８７】
（結論）
以上、本発明について、構造的特徴および／または方法論的作用に特有の言葉で説明してきたが、添付の特許請求の範囲に定義された本発明は、説明された特有の特徴および作用に必ずしも限定されるものでないことを理解されよう。むしろ、この特有の特徴および作用は、記載された本発明を実施する例示的な形式として開示されるものである。
【図面の簡単な説明】
【００８８】
【図１】ＳＩＭＤ命令をサポートするコンピュータアーキテクチャを示す図である。
【図２】モンゴメリ乗算（剰余乗算を実行する）でのＳＩＭＤ命令の使用、およびレジスタにおけるデータ値の配置を示す図である。
【図３】図１のコンピュータアーキテクチャにおいてモンゴメリ乗算を実行するための処理を示す流れ図である。
【符号の説明】
【００８９】
１００  コンピュータアーキテクチャ
１０２  マイクロプロセッサ
１０４  メモリ
１０６（１）〜（Ｎ）  ＡＬＵ
１０８（１）〜（Ｍ）  レジスタ
１１０  ｍｏｎｔｍｕｌ関数用のＳＩＭＤ命令
【図１】
0004662744.tif 000007
【図２】
0004662744.tif 000008
【図３】
0004662744.tif 000009