JP5896756B2 - 演算装置及びプログラム - Google Patents

Description

本発明は、演算装置、演算方法及びプログラムに関する。
特に、ＲＳＡ（登録商標）暗号や楕円曲線暗号などに用いられる多倍長整数の加算、減算、乗算、モンゴメリ・リダクション、モンゴメリ乗算を行う演算装置及びプログラムに関する。

ＲＳＡ（登録商標）暗号をはじめとする、多くの公開鍵暗号では、ある奇整数を法とする有限体上の演算を行う。
このとき、一般的なＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）で演算可能なデータ長（例えば３２ビット）を超えた数に対して、演算を行う必要がある。
中でも、多倍長乗算は、ＣＰＵの内部演算幅をｂ（ｂｉｔ）、入力長をｌ（ｂｉｔ）とした場合、ｎ＝ｌ／ｂに対して、Ｏ（ｎ^２）の計算量がかかり、多倍長演算の中でも、重い処理の１つとなっている。

一方、入力に対してモンゴメリ変換を行い、モンゴメリ変換後のデータに対して、多倍長乗算とモンゴメリ・リダクションとよばれる処理を行うことで、演算コストの高い除算や剰余算を回避する方法が示されている。
また、多倍長乗算とモンゴメリ・リダクションはペアで行うことが多く、これらをあわせてモンゴメリ乗算と呼ぶ。
通常、モンゴメリ・リダクションもＯ（ｎ^２）の計算量がかかる。
公開鍵暗号を高速化するにあたり、これらの処理の高速化が求められる。

乗算、モンゴメリ・リダクションを高速化する方法としては、専用ハードウェアを用いたり、入力を変換したりして高速化を行う装置が提案されている（例えば、特許文献１、特許文献２、特許文献３、特許文献４）。

特開昭６３−２８６９３号公報 特開２０００−１０４７９号公報 特開２０００−３５３０７７号公報 特開２００１−１９４９９３号公報

特許文献１、特許文献３によれば、専用のプロセッサアーキテクチャやメモリアーキテクチャを持つ計算機を用いて多倍長演算を高速化している。
しかしながら、特許文献１及び特許文献３の方式を実現するためには、専用装置が必要となる。

特許文献２によれば、正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２^ｎとして定義されたＲを用いて、Ｄ＝Ｃ・Ｒ^−１ ｍｏｄ ｐを計算するにあたって、Ｃ＝αＲ＋βを満たす整数ペア（α，β）を算出する（α，β）と、Ｒ^−１＝ε（ｍｏｄ ｐ）を満たすεを求め、α＋εβを計算し、その結果に対してｐを法として合同なｐ以下の剰余値を求めている。
しかしながら、当該方式の場合、法ｐによる多倍長剰余算を行う必要があり、剰余演算に計算コストがかかる。

特許文献４によれば、入力を剰余数系に変換し、変換した系上でモンゴメリ上場算を実現することで、処理の並列化を図り、高速化を実現している。
しかしながら、当該方式では、基底拡張に計算コストがかかる上に、整数による剰余算を行う必要がある。
他の演算に対して、剰余算が遅いプロセッサでは、かえって計算コストがかかる。

この発明は上記のような課題を解決することを主な目的としており、専用装置を用いることなく、多倍長演算を少ない計算コストで高速に実現することを主な目的とする。

本発明に係る演算装置は、
制御部と演算部と記憶部とを有し、入力値の加算を行う演算装置であって、
前記制御部は、
それぞれのビット幅が共通しており、それぞれのビット幅が前記演算部の演算ビット幅よりも大きい入力値Ｘ及び入力値Ｙを、それぞれ、前記演算部の演算ビット幅ごとに分割し、
前記記憶部内の所定の記憶領域を割当てて、入力値Ｘから分割されたｎ（ｎ≧２）個の分割値を格納するためのｎ個の変数Ｘ［０］〜Ｘ［ｎ−１］と、入力値Ｙから分割されたｎ個の分割値を格納するためのｎ個の変数Ｙ［０］〜Ｙ［ｎ−１］とを設け、
入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｘ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、入力値Ｙ内の最下位ビットが含まれる分割値が０番目の変数Ｙ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｙ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｙ［０］〜Ｙ［ｎ−１］に格納し、
前記記憶部内の所定の記憶領域を割当てて、前記演算部による加算結果を格納するためのｕ（ｕ＞ｎ）個の変数Ｚ［０］〜Ｚ［ｕ−１］を設け、
前記演算部は、
スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行し、
スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、第１フェーズの処理として、
入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［ｔ］の値）＋（Ｙ［ｔ］の値）を計算し、加算結果とキャリー値ｃを求め、加算結果をｔ番目の変数Ｚ［ｔ］に格納する処理を行い、
前記制御部は、
カウンタ値ｉを１に設定し、前記演算部に第２フェーズの処理を開始させ、
カウンタ値ｉがｎに達するか、全てのスレッドｔが第２フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
前記演算部は、
前記制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第２フェーズの１ラウンド分の処理として、
〈ａ〉（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値とスレッドｔで得られたキャリー値ｃとを用いて、（Ｚ［ｔ＋ｉ］の値）＋ｃを計算し、新たな加算結果と新たなキャリー値ｃを求め、
〈ｂ〉変数Ｚ［ｔ＋ｉ］の値と新たな加算結果とを比較し、両者が一致している場合に、スレッドｔの第２フェーズの処理を停止し、両者が一致しない場合に、新たな加算結果を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］に格納する
処理を、行うことを特徴とする。

本発明では、各分割値の加算は第１フェーズの処理として１回で終了し、その後、第２フェーズとしてキャリー値の処理が行われる。
通常、数回のラウンド処理でキャリー値の処理は終了するため、全てのスレッドｔにおいて早期に第２フェーズの処理が終了し、加算処理を高速に行うことができる。
このように、本発明によれば、専用装置を用いることなく、多倍長演算を少ない計算コストで高速に実現することができる。

実施の形態１〜５に係る多倍長演算装置の構成例を示す図。 実施の形態１に係る多倍長加算の手順を示すフローチャート図。 実施の形態１に係る多倍長加算の具体例を示す図。 実施の形態１に係る多倍長加算の計算過程を示す図。 実施の形態２に係る多倍長減算の手順を示すフローチャート図。 実施の形態２に係る多倍長減算の具体例を示す図。 実施の形態２に係る多倍長減算の計算過程を示す図。 実施の形態３に係る多倍長乗算の手順を示すフローチャート図。 実施の形態３に係る多倍長乗算の具体例を示す図。 実施の形態３に係る多倍長乗算の具体例を示す図。 実施の形態３に係る多倍長乗算の計算過程を示す図。 実施の形態３に係る多倍長乗算の計算過程を示す図。 実施の形態４に係るモンゴメリ・リダクションの手順を示すフローチャート図。 実施の形態４に係るモンゴメリ・リダクションの具体例を示す図。 実施の形態４に係るモンゴメリ・リダクションの具体例を示す図。 実施の形態４に係るモンゴメリ・リダクションの計算過程を示す図。 実施の形態４に係るモンゴメリ・リダクションの計算過程を示す図。 実施の形態５に係るモンゴメリ乗算の手順を示すフローチャート図。 実施の形態５に係るモンゴメリ乗算の具体例を示す図。 実施の形態５に係るモンゴメリ乗算の具体例を示す図。 実施の形態５に係るモンゴメリ乗算の計算過程を示す図。 実施の形態５に係るモンゴメリ乗算の計算過程を示す図。

実施の形態１〜５では、多倍長演算を高速に実現する多倍長演算装置を説明する。
実施の形態１〜５では、一例として、ＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ Ｍｕｌｔｉｐｌｅ Ｄａｔａ）計算機を用いた多倍長演算装置を説明する。
また、実施の形態１〜５に係る多倍長演算装置は、一般的に入手可能なＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）を用いて実現することも可能である。

実施の形態１．
図１は、実施の形態１〜５に係る多倍長演算装置１００の構成例を示すブロック図である。
実施の形態１〜５に係る多倍長演算装置１００は、計算部１０１、メモリ１０２、通信ポート１０３がバス１０４で接続されている構成となっている。
なお、実施の形態１〜５に係る多倍長演算装置１００は、演算装置の例に相当する。

計算部１０１は、複数のプロセッサ１０５〜１０６、命令デコーダ１０７、レジスタ１０８、１０９で構成されている。

プロセッサ１０５〜１０６は、命令デコーダ１０７がデコードした命令を異なるデータに対して実行する。
プロセッサ１０５〜１０６のいずれかのプロセッサは、多倍長演算を行う際に必要な制御を行う制御部としての役割を有する。
また、プロセッサ１０５〜１０６のいずれかのプロセッサ、又は、プロセッサ１０５〜１０６の全てのプロセッサは、多倍長演算の計算処理を行う演算部としての役割を有する。
制御部として機能するプロセッサが、併せて演算部として機能するようにしてもよい。
プロセッサ１０５〜１０６が、制御部として行う処理の詳細、演算部として行う処理の詳細は、後述する。
演算部として機能するプロセッサは、所定の演算幅ｂビット（例えば３２ビット）の演算を行う。
以下、演算幅のｂビットを１ワードと記す。
また、以下では、制御部として機能するプロセッサを単に「制御部」とも記し、演算部として機能するプロセッサを単に「演算部」とも記す。

データは汎用レジスタ１０８に格納される。
また、メモリ１０２を介してプロセッサ間でデータのやり取りを行う。
特殊レジスタ１０９は、プロセッサ１０５〜１０６の計算値以外の特殊情報を格納するレジスタである。
汎用レジスタ１０８及びメモリ１０２は、記憶部の例に相当する。

各プロセッサが実行するプログラムの単位をスレッドと称す。
実施の形態１〜５に係る多倍長演算装置１００の特徴の１つは、１つの多倍長演算を複数のスレッドを用いて演算することにある。
スレッドの本数ｎ（ｎ≧２）は、入力値をｌ（ｌ＞ｂ）ビットとした場合、ｎ≧ｃｅｉｌ（ｌ／ｂ）とする。
ここで、ｃｅｉｌ（ａ）はａ以上の整数のうちの最小の整数とする。
各プロセッサが実行するスレッドには０以上（ｎ−１）以下のスレッド番号が付与される。
プロセッサ１０５〜１０６はスレッドの本数や、各プロセッサが処理するスレッドの番号を、特殊レジスタ１０９から取得することができる。

実施の形態１〜５に係る多倍長演算装置１００は、図１に示すように、プロセッサ１０５、１０６、レジスタ１０８、１０９、メモリ１０２（例えば、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ））、通信ポート１０３、バス１０４を備える一般的なコンピュータとすることができる。
また、図１では図示を省略しているが、多倍長演算装置１００は、磁気ディスク装置に代表される不揮発性の記憶装置を備えている。
そして、制御部及び演算部の後述する動作を実現するためのコンピュータプログラムやオペレーティングシステムが不揮発性の記憶装置に記憶されている。
制御部及び演算部の動作を実現するためのコンピュータプログラムの少なくとも一部は、オペレーティングシステムに含まれていてもよい。
そして、プロセッサ１０５、１０６は、オペレーティングシステムを動作させながら、制御部及び演算部の動作を実現するためのコンピュータプログラムをメモリ１０２にロードし、また、これらコンピュータプログラムをメモリ１０２から読み出し、実行することで、制御部及び演算部として機能する。
また、多倍長演算装置１０の動作手順を、演算方法として捉えることもできる。

次に、本実施の形態に係る計算部１０１の動作の概略を説明する。

本実施の形態では、入力値Ｘと入力値Ｙの加算結果（Ｘ＋Ｙ）を変数Ｚに出力する。
入力値Ｘと入力値Ｙは、ともにｌ（ｌ＞ｂ）ビットである。
つまり、入力値Ｘと入力値Ｙのビット幅（ｌビット）は、各プロセッサの１ワードであるｂビットよりも大きい。

本実施の形態では、制御部が入力値Ｘと入力値Ｙをそれぞれｎ桁に分割する。
また、制御部は、入力値Ｘから分割されたｎ個の分割値を格納するためのｎ個の変数Ｘ［０］〜Ｘ［ｎ−１］と、入力値Ｙから分割されたｎ個の分割値を格納するためのｎ個の変数Ｙ［０］〜Ｙ［ｎ−１］とを、いずれかの記憶領域（例えば、メモリ１０２）に設ける。
また、制御部は、入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｘ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｘ［０］〜Ｘ［ｎ−１］に格納する。
同様に、制御部は、入力値Ｙ内の最下位ビットが含まれる分割値が０番目の変数Ｙ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｙ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｙ［０］〜Ｙ［ｎ−１］に格納する。
また、いずれかの記憶領域（例えば、メモリ１０２）に、演算部による加算結果を格納するためのｕ（ｕ＞ｎ）個の変数Ｚ［０］〜Ｚ［ｕ−１］を設ける。
なお、変数Ｚの個数は、ｎ以上であれば任意の数とすることができるが、以下では、２ｎ個の変数Ｚ、つまり、変数Ｚ［０］〜Ｚ［２ｎ−１］を設ける（変数Ｚが２ｎワードのサイズを持つ）例にて説明を進める。

演算部は、スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行する。
演算部の処理は、第１フェーズの処理と、第２フェーズの処理に大別される。

演算部は、第１フェーズの処理として、スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［ｔ］の値）＋（Ｙ［ｔ］の値）を計算し、加算結果とキャリー値ｃを求め、加算結果をｔ番目の変数Ｚ［ｔ］に格納する。

次に、制御部がカウンタ値ｉを１に設定し、演算部に第２フェーズの処理を開始させる。
そして、カウンタ値ｉがｎに達するか、全てのスレッドｔが第２フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、制御部は、カウンタ値ｉをインクリメントする。

演算部は、制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第２フェーズの１ラウンド分の処理を繰り返す。
第２フェーズの１ラウンド分の処理は、以下の〈ａ〉と〈ｂ〉の処理である。
〈ａ〉（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値とスレッドｔで得られたキャリー値ｃとを用いて、（Ｚ［ｔ＋ｉ］の値）＋ｃを計算し、新たな加算結果と新たなキャリー値ｃを求める。
〈ｂ〉変数Ｚ［ｔ＋ｉ］の値と新たな加算結果とを比較し、両者が一致している場合に、スレッドｔの第２フェーズの処理を停止し、両者が一致しない場合に、新たな加算結果を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］に格納する。

次に、図２のフローチャートを参照して、本実施の形態に係る多倍長演算装置１００で多倍長加算を行う場合の手順を説明する。
なお、図２において、大文字で示す変数はメモリ１０２上のデータとし、小文字で示す変数は汎用レジスタ１０８上のデータとする。
また、各変数のデータ長は１ワードとする。
また、入力値ｃｅｉｌ（ｌ／ｂ）ワードがｎに満たない場合は、満たない部分のワードを予め０でクリアする。

まず、演算部が、汎用レジスタ１０８から、スレッドごとに自身のスレッド番号と演算するスレッド本数を取得する（Ｓ２０１）。

次に、演算部が出力Ｚの上位ｎ桁をゼロクリアし、スレッドごとにＸとＹの加算を求め、加算値をＺの下位ｎ桁に格納し、制御部が変数（カウンタ値）ｉに１をセットする（Ｓ２０２）。
ここで、Ａｄｄ＿ｃｃ（ａ，ｂ）は、１ワードの入力ａ，ｂに対し、ａ＋ｂの結果を汎用レジスタ１０８に出力し、キャリー値を特殊レジスタ１０９に出力することを意味する。
図２に示すＳ２０２の処理２及び処理３が、第１フェーズの処理に該当する。

ｉがｎ未満である場合、演算部はＺ［ｔ＋ｉ］の値を読み込み、０との加算を行う（Ｓ２０３）。
ここで、Ａｄｄｃ＿ｃｃ（ａ，ｂ）は、１ワードの入力ａ，ｂに対し、ａとｂと特殊レジスタ１０９のキャリーの値を加算し、加算結果を汎用レジスタ１０８に出力し、加算後のキャリー値を特殊レジスタ１０９に出力することを意味する。

加算の前後で値に変化が無ければ（ｓ＝＝ａ？でＹＥＳ）、演算部は、キャリー値が０であるとみなし、スレッドｔの処理を終了する。
また、演算部は、変化があれば（ｓ＝＝ａ？でＮＯ）、加算結果を、Ｚ［ｔ＋ｉ］に出力し、制御部がｉに１を加算する（Ｓ２０４）。
キャリー値が０になる（すなわち、ｓ＝＝ａ？でＹＥＳとなる）か、ｉがｎとなるまでＳ２０３、Ｓ２０４を繰り返す。
ｎ本のスレッド全てがループを抜けたら処理を終了する。
図２に示すＳ２０３の処理１及び処理２、ｓ＝＝ａ？の判断、Ｓ２０４の処理１が、第２フェーズの１ラウンド分の処理に該当する。

図３は、本実施の形態に係る多倍長加算における値の変化を示す。
図３では、内容を理解しやすくするため、内部演算幅を十進数とし、４桁の演算を４つのスレッド（スレッド番号０〜３）で実行した場合を示している。図３では、１２３４（Ｘ）＋５６７８（Ｙ）＝６９１２（Ｚ）を計算する例を示す。
また、図４は、図３に示した計算の内訳を、スレッド番号０について示している。

次に、本実施の形態に係る多倍長演算装置１００の効果を説明する。
本実施の形態では、各桁の加算は１回で終了し、その後、キャリーの処理を行う。
キャリーの処理のワーストケースはＯ（ｎ）となるが、入力がランダムである場合、キャリーが最後まで残る確率は非常に低いため、数回のキャリーの計算で図２のループを抜けることができるため、加算処理を高速に行うことができる。
また、キャリー加算前後の値を比較することで、キャリー情報を直接参照できなくても、キャリーの有無を判定することができる。
また、本実施の形態に係る多倍長演算装置１００は、前述したように、ＳＩＭＤ計算機等の通常の計算機で実現可能であり、専用装置を用いることなく、多倍長加算を高速に行うことができる。

以上、本実施の形態では、
複数のプロセッサを内蔵し、単一の命令を複数のデータに対して同時に実行できる計算機と、データを格納し、前記プロセッサが同時にアクセスできるメモリを有する多倍長整数演算装置であって、入力Ｘ，Ｙに対して、Ｚ＝Ｘ＋Ｙを計算する多倍長加算を以下のステップで実行する多倍長整数演算装置を説明した。
１．入力データを計算機の内部演算幅毎に複数の桁（以降、それぞれＸ［ｎ］，Ｙ［ｎ］と記す）に分割するステップ
２．スレッドごとに自身のスレッド番号ｔと演算するスレッド本数ｎを取得するステップ
３．Ｚを０にセットするステップ
４．Ｘ［ｔ］＋Ｙ［ｔ］を計算し、加算結果とキャリーｃを求め、前記加算結果をＺ［ｔ］に格納するステップ
５．桁ｉを１に設定するステップ
６．Ｚ［ｔ＋ｉ］＋ｃを計算し、新たな加算結果と新たなキャリーｃを求め、前記加算結果をＺ［ｔ＋ｉ］に格納するステップ
７．桁ｉに１を加算するステップ
８．ｉ＜ｎかつ、ｃ≠０の間、ステップ６〜７を実行するステップ
９．前記スレッドの全てがステップ６〜８を完了するのを待つステップ。

実施の形態２．
本実施の形態では、多倍長減算処理を行う。
本実施の形態に係る多倍長演算装置１００の構成は図１に示したものと同じである。

次に、本実施の形態に係る計算部１０１の動作の概略を説明する。

本実施の形態では、入力値Ｙから入力値Ｘを減算した減算結果（Ｙ−Ｘ）を変数Ｚに出力する。
なお、実施の形態１と同様に、本実施の形態でも、入力値Ｘ、入力値Ｙのビット幅がｌ（ｌ＞ｂ）ビットであり、制御部が入力値Ｘと入力値Ｙをそれぞれｎ桁に分割し、変数Ｘ［０］〜Ｘ［ｎ−１］と変数Ｙ［０］〜Ｙ［ｎ−１］とを設け、更に、変数Ｚ［０］〜Ｚ［２ｎ−１］を設ける。
変数Ｚの個数は、本実施の形態でも、ｎ以上であれば任意の数とすることができるが、実施の形態１と同様に、２ｎ個の変数Ｚを設ける（変数Ｚが２ｎワードのサイズを持つ）例にて説明を進める。
また、制御部が分割値をＸ［０］〜Ｘ［ｎ−１］を格納する手順、Ｙ［０］〜Ｙ［ｎ−１］に格納する手順も実施の形態１と同じである。
更に、演算部も、実施の形態１と同様に、ｎ個のスレッドを並列に実行し、第１フェーズの処理と、第２フェーズの処理とを行う。

本実施の形態では、演算部は、第１フェーズの処理として、スレッドｔにおいて、入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｙ［ｔ］の値）−（Ｘ［ｔ］の値）を計算し、減算結果とボロー値ｄを求め、減算結果をｔ番目の変数Ｚ［ｔ］に格納する。

次に、制御部がカウンタ値ｉを１に設定し、演算部に第２フェーズの処理を開始させる。
そして、カウンタ値ｉがｎに達するか、全てのスレッドｔが第２フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、制御部は、カウンタ値ｉをインクリメントする。

演算部は、制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第２フェーズの１ラウンド分の処理を繰り返す。
第２フェーズの１ラウンド分の処理は、以下の〈ａ〉と〈ｂ〉の処理である。
〈ａ〉（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値とスレッドｔで得られたボロー値ｄとを用いて、（Ｚ［ｔ＋ｉ］の値）−ｄを計算し、新たな減算結果と新たなボロー値ｄを求める。
〈ｂ〉変数Ｚ［ｔ＋ｉ］の値と新たな減算結果とを比較し、両者が一致している場合に、スレッドｔの第２フェーズの処理を停止し、両者が一致しない場合に、新たな減算結果を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］に格納する。

次に、図５のフローチャートを参照して、本実施の形態に係る多倍長演算装置１００で多倍長減算を行う場合の手順を説明する。
なお、図５において、大文字で示す変数はメモリ１０２上のデータとし、小文字で示す変数は汎用レジスタ１０８上のデータとする。
また、各変数のデータ長は１ワードとする。
入力値ｃｅｉｌ（ｌ／ｂ）ワードがｎに満たない場合は、満たない部分のワードを予め０でクリアする。

まず、演算部が、汎用レジスタ１０８から、スレッドごとに自身のスレッド番号と演算するスレッド本数を取得する（Ｓ４０１）。

次に、演算部が出力Ｚの上位ｎ桁をゼロクリアし、スレッドごとにＹとＸの減算を求め、減算値をＺの下位ｎ桁に格納し、制御部が変数（カウンタ値）ｉに１をセットする（Ｓ４０２）。
ここで、Ｓｕｂ＿ｃｃ（ａ，ｂ）は１ワードの入力ａ，ｂに対し、ｂ−ａの結果を汎用レジスタ１０８に出力し、ボロー値を特殊レジスタに出力することを意味する。
図５に示すＳ４０２の処理２及び処理３が、第１フェーズの処理に該当する。

ｉがｎ未満である場合、演算部はＺ［ｔ＋ｉ］の値を読み込み、０との減算を行う（Ｓ４０３）。
ここで、Ｓｕｂｃ＿ｃｃ（ａ，ｂ）は１ワードの入力ａ，ｂに対し、ｂからａと特殊レジスタ１０９のボローの値を減算し、減算結果を汎用レジスタ１０８に出力し、ボロー値を特殊レジスタ１０９に出力することを意味する。

減算の前後で値に変化が無ければ（ｓ＝＝ａ？でＹＥＳ）、演算部は、ボロー値が０であるとみなし、スレッドｔの処理を終了する。
また、演算部は、変化があれば（ｓ＝＝ａ？でＮＯ）、減算結果を、Ｚ［ｔ＋ｉ］に出力し、制御部がｉに１を加算する（Ｓ４０４）。
ボロー値が０になる（すなわち、ｓ＝＝ａ？でＹＥＳとなる）か、ｉがｎとなるまでＳ４０３、Ｓ４０４を繰り返す。
ｎ本のスレッド全てがループを抜けたら処理を終了する。
図５に示すＳ４０３の処理１及び処理２、ｓ＝＝ａ？の判断、Ｓ４０４の処理１が、第２フェーズの１ラウンド分の処理に該当する。

図６は、本実施の形態に係る多倍長減算における値の変化を示す。
図６では、内容を理解しやすくするため、内部演算幅を十進数とし、４桁の演算を４つのスレッド（スレッド番号０〜３）で実行した場合について示している。図６では、７６３４（Ｙ）−５６７８（Ｘ）＝１９５６（Ｚ）を計算する例を示す。
また、図７は、図６に示した計算の内訳を、スレッド番号０について示している。

次に、本実施の形態に係る多倍長演算装置１００の効果を説明する。
本実施の形態では、各桁の減算は１回で終了し、その後、ボローの処理を行う。
ボローの処理のワーストケースはＯ（ｎ）となるが、入力がランダムである場合、ボローが最後まで残る確率は非常に低いため、数回のボローの計算で図５のループを抜けることができる。
よって、減算処理を高速に行うことができる。
また、ボロー減算前後の値を比較することで、ボロー情報を直接参照できなくても、ボローの有無を判定することができる。
また、本実施の形態に係る多倍長演算装置１００は、前述したように、ＳＩＭＤ計算機等の通常の計算機で実現可能であり、専用装置を用いることなく、多倍長減算を高速に行うことができる。

以上、本実施の形態では、
複数のプロセッサを内蔵し、単一の命令を複数のデータに対して同時に実行できる計算機と、データを格納し、前記プロセッサが同時にアクセスできるメモリを有する多倍長整数演算装置であって、入力Ｘ，Ｙに対して、Ｚ＝Ｙ−Ｘを計算する多倍長減算を以下のステップで実行する多倍長整数演算装置を説明した。
１．入力データを計算機の内部演算幅毎に複数の桁（以降、それぞれＸ［ｎ］，Ｙ［ｎ］と記す）に分割するステップ
２．スレッドごとに自身のスレッド番号ｔと演算するスレッド本数ｎを取得するステップ
３．Ｚを０にセットするステップ
４．Ｙ［ｔ］−Ｘ［ｔ］を計算し、減算結果とボローｄを求め、前記減算結果をＺ［ｔ］に格納するステップ
５．桁ｉを１に設定するステップ
６．Ｚ［ｔ＋ｉ］−ｃを計算し、新たな減算結果と新たなボローｄを求め、前記減算結果をＺ［ｔ＋ｉ］に格納するステップ
７．桁ｉに１を加算するステップ
８．ｉ＜ｎかつ、ｃ≠０の間、ステップ６〜７を実行するステップ
９．前記スレッドの全てがステップ６〜８を完了するのを待つステップ。

実施の形態３．
本実施の形態では、多倍長乗算処理を行う。
本実施の形態に係る多倍長演算装置１００の構成は図１に示したものと同じである。

次に、本実施の形態に係る計算部１０１の動作の概略を説明する。

本実施の形態では、入力値Ｘと入力値Ｙを乗算した乗算結果（Ｘ×Ｙ）を変数Ｚに出力する。
なお、実施の形態１と同様に、本実施の形態でも、入力値Ｘ、入力値Ｙのビット幅がｌ（ｌ＞ｂ）ビットであり、制御部が入力値Ｘと入力値Ｙをそれぞれｎ桁に分割し、変数Ｘ［０］〜Ｘ［ｎ−１］と変数Ｙ［０］〜Ｙ［ｎ−１］とを設け、更に、変数Ｚ［０］〜Ｚ［２ｎ−１］を設ける。
また、制御部が分割値をＸ［０］〜Ｘ［ｎ−１］を格納する手順、Ｙ［０］〜Ｙ［ｎ−１］に格納する手順も実施の形態１と同じである。
更に、演算部も、実施の形態１と同様に、ｎ個のスレッドを並列に実行し、第１フェーズの処理と、第２フェーズの処理とを行う。

本実施の形態では、まず、制御部が、カウンタ値ｉを０に設定し、演算部に第１フェーズの処理を開始させる。
また、制御部は、カウンタ値ｉがｎに達するまでの間、演算部が第１フェーズの１ラウンド分の処理を終了する度に、カウンタ値ｉをインクリメントする。

演算部は、カウンタ値ｉがｎに達するまでの間、制御部によりカウンタ値ｉがインクリメントされる度に、スレッドｔにおいて、第１フェーズの１ラウンド分の処理を繰り返す。
第１フェーズの１ラウンド分の処理は、以下の〈１−ａ〉と〈１−ｂ〉の処理である。
〈１−ａ〉入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、入力値Ｙのｉ番目の変数Ｙ［ｉ］の値と、（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値と、スレッドｔで得られたキャリー成分値ｃとを用いて、（Ｘ［ｔ］の値）×（Ｙ［ｉ］の値）＋（Ｚ［ｔ＋ｉ］の値）＋ｃを計算する。
〈１−ｂ〉計算結果の下位１ワードの値を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］に格納し、計算結果の上位１ワードの値を新たなキャリー成分値ｃとする。

次に、制御部は、カウンタ値ｉがｎに達すると、演算部に第２フェーズの処理を開始させる。
そして、制御部は、カウンタ値ｉが２ｎに達するまでの間、演算部が第２フェーズの１ラウンド分の処理を終了する度に、カウンタ値ｉをインクリメントする。

演算部は、カウンタ値ｉが２ｎに達するまでの間、制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第２フェーズの１ラウンド分の処理を繰り返す。
第２フェーズの１ラウンド分の処理は、以下の〈２−ａ〉と〈２−ｂ〉の処理である。
〈２−ａ〉スレッドｔで得られたキャリー成分値ｃが０であるか否かを判断し、キャリー成分値ｃが０である場合にスレッドｔの第２フェーズの処理を停止する。
〈２−ｂ〉０でない場合に（Ｚ［ｔ＋ｉ］の値）＋ｃを計算し、計算結果の下位１ワードの値を変数Ｚ［ｔ＋ｉ］の新たな値とし、計算結果の上位１ワードの値を新たなキャリー成分値ｃとする。

次に、図８のフローチャートを参照して、本実施の形態に係る多倍長演算装置１００で多倍長乗算を行う場合の手順を説明する。
なお、図８において、大文字で示す変数はメモリ１０２上のデータとし、小文字で示す変数は汎用レジスタ１０８上のデータとする。
また、各変数のデータ長は１ワードとする。
ただし、図８において太字で表記している変数は２ワードとする。
なお、明細書では、２ワードの変数は、ダブルクオーテーションで表現する（例えば、“ｍ”）。
また、入力値ｃｅｉｌ（ｌ／ｂ）ワードがｎに満たない場合は、満たない部分のワードを予め０でクリアする。

まず、演算部が、汎用レジスタ１０８から、スレッドごとに自身のスレッド番号と演算するスレッド本数を取得し、また、Ｚと“ｃ”を０にセットし、制御部がｉに０をセットする（Ｓ６０１）。

そして、ｉがｎ未満の場合、演算部は、乗算処理を行う。
つまり、演算部は、“ｍ”＝Ｘ［ｔ］×Ｙ［ｉ］＋Ｚ［ｔ＋ｉ］＋“ｃ”を計算する。
更に、演算部は、“ｍ”の下位１ワードをＺ［ｔ＋ｉ］に、上位１ワードを“ｃ”に出力する。
次に、制御部が、ｉに１を加算する（Ｓ６０２）。
ここで、Ｍｕｌ＿ｗ（ａ，ｂ）は１ワードのａとｂの積を求め、２ワードの乗算結果を出力することを意味する。
なお、図８のＳ６０２の処理１〜４が、第１フェーズの１ラウンド分の処理に相当する。

ｉがｎ以上となったら、演算部は、乗算処理を抜け、キャリー処理を行う。
つまり、演算部は、キャリー成分値“ｃ”が０であるか否かを判断し、“ｃ”が０でない場合に（“ｃ”＝＝０？でＮＯ）、“ｃ”＝Ｚ［ｔ＋ｉ］＋“ｃ”を計算し、“ｃ”の下位１ワードをＺ［ｔ＋ｉ］に、上位１ワードを“ｃ”に出力する。
そして、制御部が、変数ｉに１を加算する（Ｓ６０３）。
ｉ≧２ｎまたは“ｃ”＝０となるまでループを繰り返す。
つまり、演算部は、変数ｉが２ｎに達するまでの間、制御部により変数ｉがインクリメントされる度に、停止していないスレッドｔにおいて、スレッドｔで得られたキャリー成分値“ｃ”が０であるか否かを判断し、キャリー成分値“ｃ”が０である場合（“ｃ”＝＝０？でＹＥＳ）にスレッドｔの処理を停止し、キャリー成分値“ｃ”が０でない場合（“ｃ”＝＝０？でＮＯ）は、Ｓ６０３の処理を行う。
ｎ本のスレッド全てがループを抜けたら処理を終了する。
なお、図８に示すＳ６０３の処理１〜３、“ｃ”＝＝０？の判断が、第２フェーズの１ラウンド分の処理に該当する。

図９及び図１０は、本実施の形態に係る多倍長乗算における値の変化を示す。
図９及び図１０では、内容を理解しやすくするため、内部演算幅を十進数とし、４桁の演算を４つのスレッド（スレッド番号０〜３）で実行した場合について示している。図９及び図１０では、１２３４（Ｘ）＊５６７８（Ｙ）＝７００６６５２（Ｚ）を計算する例を示す。
なお、図１０には、図９との連続性を明示するために、図９の最下段に示しているｉ＝３の際の計算過程を再度提示している。
また、図１１及び図１２は、図９及び図１０に示した計算の内訳を、スレッド番号０について示している。

次に、本実施の形態に係る多倍長演算装置１００の効果を説明する。
本実施の形態では、乗算処理はｎ回のループで終了する。
また、乗算処理中にキャリーの加算処理も行う点は、本実施の形態の多倍長乗算の特徴の１つである。

キャリー処理について、乗算処理終了後にキャリー成分が残っていれば、前記キャリー成分が０になるまで、加算を行う。
キャリー処理のワーストケースはＯ（ｎ）となるが、入力がランダムである場合、キャリーが最後まで残る確率は非常に低いため、数回のキャリーの計算でループを抜けることができる。
よって、多倍長乗算処理はｎ＋α（α＜ｎ）で行うことができる。
また、本実施の形態に係る多倍長演算装置１００は、前述したように、ＳＩＭＤ計算機等の通常の計算機で実現可能であり、専用装置を用いることなく、多倍長乗算を高速に行うことができる。

以上、本実施の形態では、
複数のプロセッサを内蔵し、単一の命令を複数のデータに対して同時に実行できる計算機と、データを格納し、前記プロセッサが同時にアクセスできるメモリを有する多倍長整数演算装置であって、入力Ｘ，Ｙに対して、Ｚ＝ＸＹを計算する多倍長乗算を以下のステップで実行する多倍長整数演算装置を説明した。
１．入力データを計算機の内部演算幅毎に複数の桁（以降、それぞれＸ［ｎ］，Ｙ［ｎ］と記す）に分割するステップ
２．出力Ｚ，キャリーｃ，桁ｉに０をセットするステップ
３．“ｍ”＝Ｘ［ｔ］×Ｙ［ｉ］＋Ｚ［ｔ＋ｉ］＋ｃを計算し、“ｍ”の下位１ワードをＺ［ｔ＋ｉ］に、上位１ワードをｃに出力するステップ
４．桁ｉに１を加算するステップ
５．ｉ＜ｎの間、ステップ３〜４を実行するステップ
６．ｃ＝Ｚ［ｔ＋ｉ］＋ｃを計算し、ｃの下位１ワードをＺ［ｔ＋ｉ］に、上位１ワードをｃに出力するステップ
７．ｉに１を加算するステップ
８．ｉ＜２ｎかつ、ｃ≠０の間、ステップ６〜７を実行するステップ
９．前記スレッドの全てがステップ６〜８を完了するのを待つステップ。

実施の形態４．
本実施の形態では、多倍長モンゴメリ・リダクション処理を行う。
本実施の形態に係る多倍長演算装置１００の構成は図１に示したものと同じである。

次に、本実施の形態に係る計算部１０１の動作の概略を説明する。

本実施の形態では、演算部の演算ビット幅である１ワード（ｂビット）よりも大きなビット幅の入力値Ｘと法Ｍとに対して、ｒ＝２^ｂ、Ｒ＝ｒ^ｎとして定義されたＲと、（−Ｍ^−１ ｍｏｄ ｒ）として定義されたＭＩｎｖとを用いて、（ＸＲ^−１ ｍｏｄ Ｍ）を計算するモンゴメリ・リダクションを行う。ただし、０≦Ｘ＜ＭＲとする。
なお、上記のｎは、法Ｍを１ワードごとに分割した際の法Ｍの分割数であり、ｎ≧２である。
また、本実施の形態では、入力値Ｘを１ワードごとに分割した際の入力値Ｘの分割数は、２ｎであるとする。

まず、制御部が、入力値Ｘ及び法Ｍを、それぞれ１ワードごとに分割する。
また、制御部は、入力値Ｘから分割された２ｎ個の分割値を格納するための２ｎ個の変数Ｘ［０］〜Ｘ［２ｎ−１］を、いずれかの記憶領域（例えば、メモリ１０２）に設ける。
また、制御部は、入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（２ｎ−１）番目の変数Ｘ［２ｎ−１］に格納されるようにして、２ｎ個の分割値を変数Ｘ［０］〜Ｘ［２ｎ−１］に格納する。
また、制御部は、いずれかの記憶領域（例えば、メモリ１０２）に、法Ｍから分割されたｎ個の分割値を格納するためのｎ個の変数Ｍ［０］〜Ｍ［ｎ−１］を設ける。
また、制御部は、法Ｍ内の最下位ビットが含まれる分割値が０番目の変数Ｍ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｍ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｍ［０］〜Ｍ［ｎ−１］に格納する。
更に、制御部は、いずれかの記憶領域（例えば、メモリ１０２）に、演算部による計算結果を格納するｎ個の変数Ｚ［０］〜Ｚ［ｎ−１］を設ける。

演算部は、実施の形態１〜３と同様に、スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行する。
演算部の処理は、第１フェーズ〜第４フェーズの処理に大別される。

演算部は、第１フェーズの処理として、以下の〈１−ａ〉と〈１−ｂ〉の処理を行う。
〈１−ａ〉スレッドｔにおいて、入力値Ｘの０番目の変数Ｘ［０］の値とＭＩｎｖとを用いて、（Ｘ［０］の値）×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとする。
〈１−ｂ〉スレッドｔにおいて、法Ｍのｔ番目の変数Ｍ［ｔ］の値と、入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕ＋（Ｘ［ｔ］の値）を計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［ｔ］の新たな値とし、計算結果ｍの上位１ワードの値をキャリー成分値ｃとする。
〈１−ｃ〉０番目のスレッドであるスレッド０において、スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｘ［０］の新たな値とする。

次に、制御部は、カウンタ値ｉを１に設定し、演算部に第２フェーズの処理を開始させる。
そして、カウンタ値ｉがｎに達するまで、全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントする。

演算部は、制御部によりカウンタ値ｉがインクリメントされる度に、第２フェーズの１ラウンド分の処理を繰り返す。
第２フェーズの１ラウンド分の処理は、以下の〈２−ａ〉と〈２−ｂ〉の処理である。
〈２−ａ〉スレッドｔにおいて、入力値Ｘの０番目の変数Ｘ［０］の値とｉ番目の変数Ｘ［ｉ］の値と、ＭＩｎｖとを用いて、｛（Ｘ［０］の値）＋（Ｘ［ｉ］の値）｝×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとする。
〈２−ｂ〉スレッドｔにおいて、法Ｍのｔ番目の変数Ｍ［ｔ］の値と、前記ｕと、入力値Ｘの（ｔ＋ｉ）番目の変数Ｘ［ｔ＋ｉ］の値と、スレッドｔで得られたキャリー成分値ｃとを用いて、（Ｍ［ｔ］の値）×ｕ＋（Ｘ［ｔ＋ｉ］の値）＋ｃを計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［ｔ＋ｉ］の新たな値とし、計算結果ｍの上位１ワードの値を新たなキャリー成分値ｃとする。
〈２−ｃ〉０番目のスレッドであるスレッド０において、スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｘ［０］の新たな値とする。
また、演算部は、カウンタ値ｉがｎに達すると、スレッド０において、値０を変数Ｘ［０］の新たな値とする。

次に、制御部は、カウンタ値ｉがｎに達すると、スレッド０において値０が変数Ｘ［０］の新たな値とされた後に、演算部に第３フェーズの処理を開始させる。
そして、カウンタ値ｉが２ｎに達するか、全てのスレッドｔが第３フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第３フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントする。

演算部は、カウンタ値ｉが２ｎに達するまでの間、制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第３フェーズの１ラウンド分の処理を繰り返す。
第３フェーズの１ラウンド分の処理は、以下の〈３−ａ〉と〈３−ｂ〉の処理である。
〈３−ａ〉スレッドｔで得られたキャリー成分値ｃが０であるか否かを判断し、キャリー成分値ｃが０である場合にスレッドｔの第３フェーズの処理を停止する。
〈３−ｂ〉０でない場合に、（Ｘ［（ｔ＋ｉ） ｍｏｄ ２ｎ］の値）＋ｃを計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［（ｔ＋ｉ） ｍｏｄ ２ｎ］の新たな値とし、計算結果ｍの上位１ワードの値を新たなキャリー成分値ｃとする。

制御部は、カウンタ値ｉが２ｎに達した場合、又は全てのスレッドｔが第３フェーズの処理を停止した場合に、演算部に第４フェーズの処理を開始させる。

演算部は、第４フェーズの処理として、以下の処理を行う。
変数Ｘ［０］の値を変数ａに格納し、変数Ｘ［ｎ］〜Ｘ［２ｎ−１］の値を、それぞれ、変数Ｘ［０］〜Ｘ［ｎ−１］に格納する。
変数ａの値が０でない場合、又は変数Ｘ［ｎ−１］〜Ｘ［０］の値を連接して得られる値が法Ｍ以上の場合に、Ｘ−Ｍを計算し、計算結果を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、変数Ｘ［０］〜Ｘ［ｎ−１］の値を変数Ｚ［０］〜Ｚ［ｎ−１］に格納する。

次に、図１３のフローチャートを参照して、本実施の形態に係る多倍長演算装置１００でモンゴメリ・リダクションを行う場合の手順を説明する。
図１３では、入力値Ｘのモンゴメリ・リダクションの結果ＸＲ^−１ ｍｏｄ Ｍを変数Ｚに出力する。
入力値Ｘは２ｎ桁に分割され、ｎ個のスレッドを用いて計算を行う。
また、入力値ＸはＸ＜Ｍ・Ｒの関係を満たすものとする。
ここで、Ｒ＝ｒ^ｎとし、ｒ＝２^ｂとする。
Ｚはｎワードのサイズを持つ。
ＭＩｎｖは−Ｍ^−１ ｍｏｄ ｒを満たす１ワード整数である。

図１３において、大文字で示す変数はメモリ１０２上のデータとし、小文字で示す変数は汎用レジスタ１０８上のデータとする。
また、各変数のデータ長は１ワードとする。
ただし、図１３において太字で表記した変数は２ワードとする。
なお、明細書では、２ワードの変数は、ダブルクオーテーションで表現する（例えば、“ｍ”）。
また、入力値ｃｅｉｌ（ｌ／ｂ）ワードがｎに満たない場合は、満たない部分のワードを予め０でクリアする。

まず、演算部が、汎用レジスタ１０８から、スレッドごとに自身のスレッド番号と演算するスレッド本数を取得し、制御部が、変数ｉに１をセットする（Ｓ８０１）。

次に、モンゴメリ・リダクション処理を行う。
具体的には、演算部が、Ｘ［０］×ＭＩｎｖの下位１ワードｕを求め、“ｍ”＝Ｍ［ｔ］×ｕ＋Ｘ［ｔ］を計算する。
ここで、Ｍｕｌ＿ｌｏ（ａ，ｂ）は１ワード入力ａ，ｂに対し、ａ×ｂを計算し、下位１ワードを出力することを意味する。
そして、演算部は、“ｍ”の下位１ワードをＸ［ｔ］に出力し、上位１ワードを“ｃ”に出力する（Ｓ８０２）。
また、演算部は、スレッド番号が０である場合（ｔ＝＝０？でＹＥＳ）、“ｃ”の下位１ワードをＸ［０］に出力する（Ｓ８０３）。
なお、図１３のＳ８０２とＳ８０３が第１フェーズの処理に相当する。

ｉがｎ未満の場合、演算部は、（Ｘ［０］＋Ｘ［ｉ］）×ＭＩｎｖの下位１ワードｕを求め、“ｍ”＝Ｍ［ｔ］×ｕ＋Ｘ［ｔ＋ｉ］＋“ｃ”を計算する。
また、演算部は、“ｍ”の下位１ワードをＸ［ｔ＋ｉ］に出力し、上位１ワードを“ｃ”に出力する。
そして、制御部が、変数ｉに１を加算する（Ｓ８０４）。
また、演算部は、スレッド番号が０である場合（ｔ＝＝０？でＹＥＳ）、“ｃ”の下位１ワードをＸ［０］に出力する（Ｓ８０５）。
なお、図１３のＳ８０４の処理１〜６、Ｓ８０５が、第２フェーズの１ラウンド分の処理に該当する。

ｉがｎ以上となったらモンゴメリ・リダクション処理を抜け、キャリー処理を行う。
始めに、演算部は、スレッド番号が０である場合（ｔ＝＝０？でＹＥＳ）、Ｘ［０］に０を出力する（Ｓ８０６）。
また、演算部は、“ｍ”＝Ｘ［（ｔ＋ｉ）％２ｎ］＋“ｃ”を計算し、“ｍ”の下位１ワードをＸ［（ｔ＋ｉ）％２ｎ］に、上位１ワードを“ｃ”に出力する。
制御部が、変数ｉに１を加算する（Ｓ８０７）。
ｉ≧２ｎまたは“ｃ”＝０となるまでループを繰り返す。
つまり、演算部は、変数ｉが２ｎに達するまでの間、制御部により変数ｉがインクリメントされる度に、停止していないスレッドｔにおいて、スレッドｔで得られたキャリー成分値“ｃ”が０であるか否かを判断し、キャリー成分値“ｃ”が０である場合（“ｃ”＝＝０？でＹＥＳ）にスレッドｔの処理を停止し、キャリー成分値“ｃ”が０でない場合（“ｃ”＝＝０？でＮＯ）は、Ｓ８０７の処理を行う。
そして、ｎ本のスレッド全てがループを抜けたらキャリー処理を終了する。
なお、図１３に示す“ｃ”＝＝０？の判断、Ｓ８０７の処理１〜４が、第３フェーズの１ラウンド分の処理に該当する。

なお、メモリが十分にある場合は、２ｎの剰余演算を省略してもよい。
この場合、後述の減算処理で変数ａに格納するデータはＸ［２ｎ］になることに注意する。

キャリー処理を終了したら、減算処理を行う。
演算部は、まず、Ｘ［０］の値を変数ａに出力し、Ｘの値をｎワードシフトする（Ｓ８０８）。
つまり、演算部は、変数Ｘ［ｎ］〜Ｘ［２ｎ−１］の値を、それぞれ、変数Ｘ［０］〜Ｘ［ｎ−１］に格納する。
そして、ａの値が０でないか、Ｘ［ｎ−１，…，０］の値（Ｘ［ｎ−１］〜Ｘ［０］の値を連接して得られる値）が法Ｍ以上の場合は、演算部は、多倍長整数減算Ｘ−Ｍを実行し、結果をＸに格納する（Ｓ８０９）。
最後に、演算部は、Ｘ［０］〜Ｘ［ｎ−１］の値をＺ［０］〜Ｚ［ｎ−１］に格納する（Ｓ８１０）。
なお、図１３に示すＳ８０８〜Ｓ８１０が、第４フェーズの処理に相当する。

図１４及び図１５は、本実施の形態に係るモンゴメリ・リダクションにおける値の変化を示す。
図１４及び図１５では、内容を理解しやすくするため、内部演算幅を十進数とし、４桁の演算を４つのスレッド（スレッド番号０〜３）で実行した場合について示す。図１４及び図１５では、２３４５６７８（Ｘ）＊Ｒ^−１ ｍｏｄ ３５１１（Ｍ）＝１７４５（Ｚ）を計算する例を示す。
この場合、ｎ＝４、Ｒ＝１０^ｎ＝１０^４、ｒ＝１０、ＭＩｎｖ＝−３５１１^−１ ｍｏｄ １０＝９となる。
なお、図１５には、図１４との連続性を明示するために、図１４の最下段に示しているｉ＝３の際の計算過程を再度提示している。
また、図１６及び図１７は、図１４及び図１５に示した計算の内訳を、スレッド番号０について示している。

次に、本実施の形態に係る多倍長演算装置１００の効果を説明する。
本実施の形態では、モンゴメリ・リダクション処理はｎ回のループで終了する。
モンゴメリ・リダクション処理中にキャリーの加算処理も行う点が、本実施の形態の特徴の１つである。
また、各ステップで、最下位の桁を処理するスレッドのキャリーをメモリに出力することで、計算量をＯ（ｎ）にすることができる。

キャリー処理について、モンゴメリ・リダクション処理終了後にキャリー成分が残っていれば、前記キャリー成分が０になるまで、加算を行う。
キャリー処理のワーストケースはＯ（ｎ）となるが、入力がランダムである場合、キャリーが最後まで残る確率は非常に低いため、数回のキャリーの計算でループを抜けることができる。
また、２ｎで剰余をとることで、多倍長整数乗算と同じメモリサイズでモンゴメリ・リダクションを行うことができる。
さらに、ｎが２のべき乗の場合、演算コストの大きい剰余演算を、演算コストの小さいビット演算で実現することができる。
また、本実施の形態に係る多倍長演算装置１００は、前述したように、ＳＩＭＤ計算機等の通常の計算機で実現可能であり、専用装置を用いることなく、モンゴメリ・リダクションを高速に行うことができる。

なお、本実施の形態では、入力値Ｘのビット幅は、１ワード単位で分割した際に２ｎ個に分割され、変数Ｘが２ｎ個設けられるものとした。
このため、図１３のＳ８０７の処理１及び処理３で２ｎの剰余演算を行うことにした。
しかし、メモリが十分にある場合は、入力値Ｘを格納する変数Ｘを、ｖ個（但し、ｖはｎの倍数、つまり、ｖは３ｎ、４ｎ等）で構成してもよい。ただし、入力Ｘに格納される値の範囲は０≦Ｘ＜ＭＲを満たすものとする。
このような変数Ｘの場合は、図１３のＳ８０７の処理１及び処理３における２ｎの剰余演算は省略される。
また、同様に、減算処理（図１３のＳ８０８の処理１）で変数ａに格納するデータはＸ［２ｎ］になる。
更に、減算処理（図１３のＳ８０８の処理２）で、Ｘ［ｎ］〜Ｘ［２ｎ−１］の値を、それぞれ、Ｘ［０］〜Ｘ［ｎ−１］に格納する。

以上、本実施の形態では、
複数のプロセッサを内蔵し、単一の命令を複数のデータに対して同時に実行できる計算機と、データを格納し、前記プロセッサが同時にアクセスできるメモリを有する多倍長整数演算装置であって、入力Ｘ，法Ｍ，内部演算幅ｂ（ｂｉｔ）に対し、“ｒ＝２ｂ”，“Ｒ＝ｒｎ”として定義されたＲと、“−Ｍ^−１ ｍｏｄ ｒ”として定義されたＭＩｎｖを用いて、Ｚ＝ＸＲ^−１ ｍｏｄ Ｍを計算するモンゴメリ・リダクションを以下のステップで実行する多倍長整数演算装置を説明した。
１．入力データと法を計算機の内部演算幅毎に複数の桁（以降、それぞれＸ［ｎ］，Ｍ［ｎ］と記す）に分割するステップ
２．スレッドごとに自身のスレッド番号ｔと演算するスレッド本数ｎを取得するステップ
３．Ｘ［０］×ＭＩｎｖの下位１ワードｕを求め、“ｍ”＝Ｍ［ｔ］×ｕ＋Ｘ［ｔ］を計算するステップ
４．“ｍ”の下位１ワードをＸ［ｔ］に出力し、上位１ワードを“ｃ”に出力するステップ
５．スレッド番号が０である場合、“ｃ”の下位１ワードをＸ［０］に出力するステップ
６．桁ｉに１を設定するステップ
７．（Ｘ［０］＋Ｘ［ｉ］）×ＭＩｎｖの下位１ワードｕを求め、“ｍ”＝Ｍ［ｔ］×ｕ＋Ｘ［ｔ＋ｉ］＋“ｃ”を計算するステップ
８．“ｍ”の下位１ワードをＸ［ｔ＋ｉ］に出力し、上位１ワードを“ｃ”に出力するステップ
９．スレッド番号が０である場合、ｃの下位１ワードをＸ［０］に出力するステップ
１０．桁ｉに１を加算するステップ
１１．ｉ＜ｎの間、ステップ６〜９を実行するステップ
１２．スレッド番号が０である場合、Ｘ［０］に０を出力するステップ
１３．“ｍ”＝Ｘ［（ｔ＋ｉ）％２ｎ］＋“ｃ”を計算し、“ｍ”の下位１ワードをＸ［（ｔ＋ｉ）％２ｎ］に、上位１ワードを“ｃ”に出力するステップ
１４．桁ｉに１を加算するステップ
１５．ｉ＜２ｎかつ、ｃ≠０の間、ステップ１３〜１４を実行するステップ
１６．前記スレッドの全てがステップ１３〜１５を完了するのを待つステップ
１７．Ｘ［０］の値を変数ａに取得するステップ
１８．Ｘの値をｎワードシフトするステップ
１９．ａの値が０でないか、Ｘ［ｎ−１，…，０］の値がＭ以上の場合は、多倍長整数減算Ｘ−Ｍを実行し、結果をＸに格納するステップ
２０．Ｘ［０］〜Ｘ［ｎ−１］の値をＺ［０］〜Ｚ［ｎ−１］に格納するステップ

また、本実施の形態では、
上記のステップ１２にて、“ｍ”＝Ｘ［ｔ＋ｉ］＋“ｃ”を計算し、“ｍ”の下位１ワードをＸ［ｔ＋ｉ］に、上位１ワードを“ｃ”に出力するステップを実行し、上記のステップ１７にて、Ｘ［２ｎ］の値を変数ａに取得するステップを実行する多倍長整数演算装置を説明した。

実施の形態５．
本実施の形態では、多倍長モンゴメリ乗算処理を行う。
本実施の形態に係る多倍長演算装置１００の構成は図１に示したものと同じである。

次に、本実施の形態に係る計算部１０１の動作の概略を説明する。

本実施の形態では、それぞれのビット幅が共通しており、それぞれのビット幅が演算部の演算ビット幅である１ワード（ｂビット）よりも大きい入力値Ｘと入力値Ｙと法Ｍとに対して、ｒ＝２^ｂ、Ｒ＝ｒ^ｎとして定義されたＲと、（−Ｍ^−１ ｍｏｄ ｒ）として定義されたＭＩｎｖとを用いて、（ＸＹＲ^−１ ｍｏｄ Ｍ）を計算するモンゴメリ乗算を行う。ただし、０≦Ｘ，Ｙ＜Ｍとする。
なお、上記のｎは、法Ｍを１ワードごとに分割した際の法Ｍの分割数であり、ｎ≧２である。
また、本実施の形態では、入力値Ｘを１ワードごとに分割した際の入力値Ｘの分割数、入力値Ｙを１ワードごとに分割した際の入力値Ｙの分割数は、それぞれｎであるとする。

まず、制御部が、入力値Ｘ、入力値Ｙ及び法Ｍを、それぞれ１ワードごとに分割する。
また、制御部は、入力値Ｘから分割されたｎ個の分割値を格納するためのｎ個の変数Ｘ［０］〜Ｘ［ｎ−１］と、入力値Ｙから分割されたｎ個の分割値を格納するためのｎ個の変数Ｙ［０］〜Ｙ［ｎ−１］とを、いずれかの記憶領域（例えば、メモリ１０２）に設ける。
また、制御部は、入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｘ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｘ［０］〜Ｘ［ｎ−１］に格納する。
更に、制御部は、入力値Ｙ内の最下位ビットが含まれる分割値が０番目の変数Ｙ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｙ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｙ［０］〜Ｙ［ｎ−１］に格納する。
また、制御部は、法Ｍから分割されたｎ個の分割値を格納するためのｎ個の変数Ｍ［０］〜Ｍ［ｎ−１］を、いずれかの記憶領域（例えば、メモリ１０２）に設ける。
また、制御部は、法Ｍ内の最下位ビットが含まれる分割値が０番目の変数Ｍ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｍ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｍ［０］〜Ｍ［ｎ−１］に格納する。
また、制御部は、演算部による計算結果を格納する２ｎ個の変数Ｚ［０］〜Ｚ［２ｎ−１］を、いずれかの記憶領域（例えば、メモリ１０２）に設ける。

演算部は、実施の形態１〜４と同様に、スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行する。
演算部の処理は、第１フェーズ〜第４フェーズの処理に大別される。

演算部は、第１フェーズの処理として、以下の〈１−ａ〉〜〈１−ｆ〉の処理を行う。
〈１−ａ〉スレッドｔにおいて、入力値Ｘの０番目の変数Ｘ［０］の値と、入力値Ｙの０番目の変数Ｙ［０］の値と、ＭＩｎｖとを用いて、（Ｘ［０］の値）×（Ｙ［０］の値）×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとする。
〈１−ｂ〉スレッドｔにおいて、法Ｍのｔ番目の変数Ｍ［ｔ］の値と前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕを計算し、２ワードの計算結果をｕｍとする。
〈１−ｃ〉スレッドｔにおいて、入力値Ｘの０番目の変数Ｘ［０］の値と入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［０］の値）×（Ｙ［ｔ］の値）を計算し、２ワードの計算結果をｘｙとする。
〈１−ｄ〉スレッドｔにおいて、前記ｕｍの下位１ワードと前記ｘｙの下位１ワードとを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値をｔ番目の変数Ｚ［ｔ］に格納する。
〈１−ｅ〉スレッドｔにおいて、前記ｍの上位１ワードと前記ｕｍの上位１ワードと前記ｘｙの上位１ワードとを加算し、２ワードの計算結果をキャリー成分値ｃとする。
〈１−ｆ〉０番目のスレッドであるスレッド０において、スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｚ［０］の新たな値とする。

次に、制御部は、カウンタ値ｉを１に設定し、演算部に第２フェーズの処理を開始させる。
そして、制御部は、カウンタ値ｉがｎに達するまで、全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントする。

演算部は、制御部によりカウンタ値ｉがインクリメントされる度に、第２フェーズの１ラウンド分の処理を繰り返す。
第２フェーズの１ラウンド分の処理は、以下の〈２−ａ〉〜〈２−ｆ〉の処理である。
〈２−ａ〉スレッドｔにおいて、０番目の変数Ｚ［０］とｉ番目の変数Ｚ［ｉ］と、入力値Ｘのｉ番目の変数Ｘ［ｉ］と、入力値Ｙの０番目の変数Ｙ［０］と、ＭＩｎｖとを用いて、｛（Ｚ［０］の値）＋（Ｚ［ｉ］の値）＋（Ｘ［ｉ］の値）×（Ｙ［０］の値）｝×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとする。
〈２−ｂ〉スレッドｔにおいて、法Ｍのｔ番目の変数Ｍ［ｔ］の値と前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕを計算し、２ワードの計算結果をｕｍとする。
〈２−ｃ〉スレッドｔにおいて、入力値Ｘのｉ番目の変数Ｘ［ｉ］の値と入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［ｉ］の値）×（Ｙ［ｔ］の値）を計算し、２ワードの計算結果をｘｙとする。
〈２−ｄ〉スレッドｔにおいて、前記ｕｍの下位１ワードと、前記ｘｙの下位１ワードと、ステップｔで得られたキャリー成分値ｃの下位１ワードと、（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値とを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の新たな値とする。
〈２−ｅ〉スレッドｔにおいて、前記ｍの上位１ワードと、前記ｕｍの上位１ワードと、前記ｘｙの上位１ワードと、ステップｔで得られたキャリー成分値ｃの上位１ワードとを加算し、２ワードの計算結果を新たなキャリー成分値ｃとする。
〈２−ｆ〉０番目のスレッドであるスレッド０において、スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｚ［０］の新たな値とする。
また、演算部は、カウンタ値ｉがｎに達すると、スレッド０において、値０を変数Ｚ［０］の新たな値とする。

カウンタ値ｉがｎに達すると、スレッド０において値０が変数Ｘ［０］の新たな値とされた後に、制御部は、演算部に第３フェーズの処理を開始させる。
そして、制御部は、カウンタ値ｉが２ｎに達するか、全てのスレッドｔが第３フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第３フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントする。

演算部は、カウンタ値ｉが２ｎに達するまでの間、制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第３フェーズの１ラウンド分の処理を繰り返す。
第３フェーズの１ラウンド分の処理は、以下の〈３−ａ〉及び〈３−ｂ〉の処理である。
〈３−ａ〉スレッドｔで得られたキャリー成分値ｃが０であるか否かを判断し、キャリー成分値ｃが０である場合にスレッドｔの第３フェーズの処理を停止する。
〈３−ｂ〉０でない場合に、スレッドｔで得られたキャリー成分値ｃの下位１ワードと変数Ｚ［（ｔ＋ｉ） ｍｏｄ ２ｎ］の値とを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｚ［（ｔ＋ｉ） ｍｏｄ ２ｎ］の新たな値とし、前記ｍの上位１ワードとスレッドｔで得られたキャリー成分値ｃの上位１ワードとを加算し、２ワードの計算結果を新たなキャリー成分値ｃとする。

制御部は、カウンタ値ｉが２ｎに達した場合、又は全てのスレッドｔが第３フェーズの処理を停止した場合に、演算部に第４フェーズの処理を開始させる。

演算部は、第４フェーズの処理として、以下の処理を行う。
変数Ｚ［０］の値を変数ａに格納し、変数Ｚ［ｎ］〜Ｚ［２ｎ−１］の値を、それぞれ、変数Ｚ［０］〜Ｚ［ｎ−１］に格納する。
変数ａの値が０でない場合、又は変数Ｚ［ｎ−１］〜Ｚ［０］の値を連接して得られる値が法Ｍ以上の場合に、Ｚ−Ｍを計算し、計算結果を変数Ｚ［０］〜Ｚ［ｎ−１］に格納する。

次に、図１８のフローチャートを参照して、本実施の形態に係る多倍長演算装置１００でモンゴメリ乗算を行う場合の手順を説明する。
図１８では、入力値Ｘ，Ｙのモンゴメリ乗算の結果ＸＹＲ^−１ ｍｏｄ ＭをＺに出力する。
Ｚは２ｎワードのサイズをもち、中間変数値の格納も行う。
入力値Ｘ，Ｙはｎ桁に分割され、ｎ個のスレッドを用いて計算を行う。
また、入力値Ｘ，ＹはＸ，Ｙ＜Ｍの関係を満たすものとする。
ここで、Ｒ＝ｒ^ｎとし、ｒ＝２^ｂとする。
ＭＩｎｖは−Ｍ^−１ ｍｏｄ ｒを満たす１ワード整数である。

図１８において、大文字で示す変数はメモリ１０２上のデータとし、小文字で示す変数は汎用レジスタ１０８上のデータとする。
また、各変数のデータ長は１ワードとする。
ただし、図１８において太字で表記した変数は２ワードとする。
なお、明細書では、２ワードの変数は、ダブルクオーテーションで表現する（例えば、“ｃ”）。
また、入力値ｃｅｉｌ（ｌ／ｂ）ワードがｎに満たない場合は、満たない部分のワードを予め０でクリアする。

まず、演算部が、汎用レジスタ１０８から、スレッドごとに自身のスレッド番号と演算するスレッド本数を取得し、また、Ｚを０にセットし、制御部が変数ｉを１にセットする（Ｓ１００１）。

次にモンゴメリ乗算処理を行う。
具体的には、演算部が、Ｘ［０］×Ｙ［０］×ＭＩｎｖの下位１ワードｕを求め、Ｍ［ｔ］×ｕ＋Ｘ［０］×Ｙ［ｔ］を計算する。
計算を２ワード以下の変数で行うため、Ｍ［ｔ］×ｕ，Ｘ［０］×Ｙ［ｔ］を上位ワードと下位ワードに分解し、下位ワードみの加算を行なった後、加算結果の下位１ワードをＺ［ｔ］に出力する。
また、演算部は、前記加算結果の上位ワードと前記Ｍ［ｔ］×ｕ，Ｘ［０］×Ｙ［ｔ］の上位ワードを加算し、２ワードデータ“ｃ”を生成する（Ｓ１００２）。
演算部は、スレッド番号が０である場合（ｔ＝＝０？でＹＥＳ）、“ｃ”の下位１ワードをＺ［０］に出力する（Ｓ１００３）。
なお、図１８のＳ１００２とＳ１００３が第１フェーズの処理に相当する。

ｉがｎ未満の場合、演算部は、（Ｚ［０］＋Ｚ［ｉ］＋Ｘ［ｉ］×Ｙ［０］）×ＭＩｎｖの下位１ワードｕを求め、Ｍ［ｔ］×ｕ＋Ｘ［０］×Ｙ［ｔ］＋Ｚ［ｔ＋ｉ］＋“ｃ”を計算する。
計算を２ワード以下の変数で行うため、Ｍ［ｔ］×ｕ，Ｘ［０］×Ｙ［ｔ］，“ｃ”を上位ワードと下位ワードに分解し、下位ワードみの加算を行なった後、加算結果の下位１ワードをＺ［ｔ＋ｉ］に出力する。
また、演算部は、前記加算結果の上位ワードと前記Ｍ［ｔ］×ｕ，Ｘ［０］×Ｙ［ｔ］，“ｃ”の上位ワードを加算し、２ワードデータ“ｃ”を生成する。
また、制御部が、変数ｉに１を加算する（Ｓ１００４）。
演算部は、スレッド番号が０である場合（ｔ＝＝０？でＹＥＳ）、“ｃ”の下位１ワードをＺ［０］に出力する（Ｓ１００５）。
なお、図１８のＳ１００４の処理１〜１５、Ｓ１００５が、第２フェーズの１ラウンド分の処理に該当する。

ｉがｎ以上となったらモンゴメリ乗算処理を抜け、キャリー処理を行う。
始めに、演算部は、スレッド番号が０である場合（ｔ＝＝０？でＹＥＳ）、Ｚ［０］に０を出力する（Ｓ１００６）。
次に、演算部は、Ｚ［（ｔ＋ｉ）％２ｎ］＋“ｃ”を計算する。
計算を２ワード以下の変数で行うため、“ｃ”を上位ワードと下位ワードに分解し、下位ワードみの加算を行なった後、加算結果の下位１ワードをＺ［（ｔ＋ｉ）％２ｎ］に出力する。
また、演算部は、前記加算結果の上位ワードと前記“ｃ”の上位ワードを加算し、２ワードデータ“ｃ”を生成する。
制御部が、変数ｉに１を加算する（Ｓ１００７）。
ｉ≧２ｎまたは“ｃ”＝０となるまでループを繰り返す。
つまり、演算部は、変数ｉが２ｎに達するまでの間、制御部により変数ｉがインクリメントされる度に、停止していないスレッドｔにおいて、スレッドｔで得られたキャリー成分値“ｃ”が０であるか否かを判断し、キャリー成分値“ｃ”が０である場合（“ｃ”＝＝０？でＹＥＳ）にスレッドｔの処理を停止し、キャリー成分値“ｃ”が０でない場合（“ｃ”＝＝０？でＮＯ）は、Ｓ１００７の処理を行う。
そして、ｎ本のスレッド全てがループを抜けたらキャリー処理を終了する。
なお、図１８に示す“ｃ”＝＝０？の判断、Ｓ１００７の処理１〜４が、第３フェーズの１ラウンド分の処理に該当する。

なお、メモリが十分にある場合は、２ｎの剰余演算を省略してもよい。
この場合、後述の減算処理で変数ａに格納するデータはＺ［２ｎ］になることに注意する。

キャリー処理を終了したら、減算処理を行う。
演算部は、まず、Ｚ［０］の値を変数ａに出力し、Ｚの値をｎワードシフトする（Ｓ１００８）。
つまり、演算部は、変数Ｚ［ｎ］〜Ｚ［２ｎ−１］の値を、それぞれ、変数Ｚ［０］〜Ｚ［ｎ−１］に格納する。
そして、ａの値が０でないか、Ｚ［ｎ−１，…，０］の値（Ｚ［ｎ−１］〜Ｚ［０］の値を連接して得られる値）が法Ｍ以上の場合は、演算部は、多倍長整数減算Ｚ−Ｍを実行し、結果をＺに格納する（Ｓ１００９）。
最後に、演算部は、Ｚ［０］〜Ｚ［ｎ−１］を出力する。
なお、図１３に示すＳ１００８、Ｓ１００９及びＺ［０］〜Ｚ［ｎ−１］の出力が、第４フェーズの処理に相当する。

図１９及び図２０は、本実施の形態に係るモンゴメリ乗算における値の変化を示す。
図１９及び図２０では、内容を理解しやすくするため、内部演算幅を十進数とし、４桁の演算を４つのスレッド（スレッド番号０〜３）で実行した場合について示す。図１４及び図１５では、５６７８（Ｘ）＊４３２１（Ｙ）＊Ｒ^−１ ｍｏｄ ６１３１（Ｍ）＝３７３６（Ｚ）を計算する例を示す。
この場合、ｎ＝４、Ｒ＝１０^ｎ＝１０^４、ｒ＝１０、ＭＩｎｖ＝−６１３１^−１ ｍｏｄ １０＝９となる。
なお、図２０には、図１９との連続性を明示するために、図１９の最下段に示しているｉ＝３の際の計算過程（一部）を再度提示している。
また、図２１及び図２２は、図１９及び図２０に示した計算の内訳を、スレッド番号０について示している。

次に、本実施の形態に係る多倍長演算装置１００の効果を説明する。
本実施の形態では、モンゴメリ乗算処理はｎ回のループで終了する。
モンゴメリ乗算処理中にキャリーの加算処理も行う点が、本実施の形態の特徴の１つである。
また、加算データを上位と下位で分割して加算することで、３ワードの変数が必要な計算を、２ワード以下の変数で行うことができる。
さらに、各ステップで、最下位の桁を処理するスレッドのキャリーをメモリに出力することで、計算量をＯ（ｎ）にすることができる。

キャリー処理について、モンゴメリ乗算処理終了後にキャリー成分が残っていれば、前記キャリー成分が０になるまで、加算を行う。
キャリー処理のワーストケースはＯ（ｎ）となるが、入力がランダムである場合、キャリーが最後まで残る確率は非常に低いため、数回のキャリーの計算でループを抜けることができる。
また、２ｎで剰余をとることで、多倍長整数乗算と同じメモリサイズでモンゴメリ乗算処理を実現することができる。
さらに、ｎが２のべき乗の場合、演算コストの大きい剰余演算を、演算コストの小さいビット演算で実現することができる。
また、本実施の形態に係る多倍長演算装置１００は、前述したように、ＳＩＭＤ計算機等の通常の計算機で実現可能であり、専用装置を用いることなく、モンゴメリ乗算を高速に行うことができる。

なお、本実施の形態では、変数Ｚは２ｎワードで構成されるものとした。
このため、図１８のＳ１００７の処理３及び処理４で２ｎの剰余演算を行うことにした。
しかし、変数Ｚは、ｖワード（但し、ｖはｎの倍数、つまり、ｖは３ｎ、４ｎ等）で構成してもよい。
このような変数Ｚの場合は、図１８のＳ１００７の処理３及び処理４における２ｎの剰余演算は省略される。
また、同様に、減算処理（図１８のＳ１００８の処理１）で変数ａに格納するデータはＺ［２ｎ］になる。
更に、減算処理（図１８のＳ１００８の処理２）で、Ｚ［ｎ］〜Ｚ［２ｎ−１］の値を、それぞれ、Ｚ［０］〜Ｚ［ｎ−１］に格納する。

以上、本実施の形態では、
複数のプロセッサを内蔵し、単一の命令を複数のデータに対して同時に実行できる計算機と、データを格納し、前記プロセッサが同時にアクセスできるメモリを有する多倍長整数演算装置であって、入力Ｘ，Ｙ，法Ｍ，内部演算幅ｂ（ｂｉｔ）に対し、“ｒ＝２ｂ”，“Ｒ＝ｒｎ”として定義されたＲと、“−Ｍ−１ ｍｏｄ ｒ”として定義されたＭＩｎｖを用いて、Ｚ＝ＸＹＲ−１ ｍｏｄ Ｍを計算するモンゴメリ乗算を以下のステップで実行する多倍長整数演算装置を説明した。
１．入力データと法を計算機の内部演算幅毎に複数の桁（以降、それぞれＸ［ｎ］，Ｙ［ｎ］，Ｍ［ｎ］と記す）に分割するステップ
２．スレッドごとに自身のスレッド番号ｔと演算するスレッド本数ｎを取得するステップ
３．Ｚを０にセットするステップ
４．Ｘ［０］×Ｙ［０］×ＭＩｎｖの下位１ワードｕを求め、Ｍ［ｔ］×ｕとＸ［０］×Ｙ［ｔ］を計算するステップ
５．前記Ｍ［ｔ］×ｕとＸ［０］×Ｙ［ｔ］の下位ワードみの加算を行なった後、加算結果の下位１ワードをＺ［ｔ］に出力するステップ
６．前記加算結果の上位ワードと前記Ｍ［ｔ］×ｕ，Ｘ［０］×Ｙ［ｔ］の上位ワードを加算し、２ワードデータ“ｃ”を生成するステップ
７．スレッド番号が０である場合、“ｃ”の下位１ワードをＺ［０］に出力するステップ
８．桁ｉに１を設定するステップ
９．（Ｚ［０］＋Ｚ［ｉ］＋Ｘ［ｉ］×Ｙ［０］）×ＭＩｎｖの下位１ワードｕを求め、Ｍ［ｔ］×ｕとＸ［ｉ］×Ｙ［ｔ］を計算するステップ
１０．前記Ｍ［ｔ］×ｕ，Ｘ［０］×Ｙ［ｔ］，“ｃ”の下位ワードとＺ［ｔ＋ｉ］との加算を行なった後、加算結果の下位１ワードをＺ［ｔ＋ｉ］に出力するステップ
１１．前記加算結果の上位ワードと前記Ｍ［ｔ］×ｕ，Ｘ［０］×Ｙ［ｔ］，“ｃ”の上位ワードを加算し、２ワードデータ“ｃ”を生成するステップ
１２．変数ｉに１を加算するステップ
１３．スレッド番号が０である場合、“ｃ”の下位１ワードをＺ［０］に出力するステップ
１４．ｉ＜ｎの間、ステップ９〜１３を実行するステップ
１５．スレッド番号が０である場合、Ｚ［０］に０を出力するステップ
１６．“ｃ”の下位ワードとＺ［（ｔ＋ｉ）％２ｎ］との加算を行なった後、加算結果の下位１ワードをＺ［（ｔ＋ｉ）％２ｎ］に出力するステップ
１７．前記加算結果の上位ワードと前記“ｃ”の上位ワードを加算し、２ワードデータ“ｃ”を生成するステップ
１８．桁ｉに１を加算するステップ
１９．ｉ＜２ｎかつ、ｃ≠０の間、ステップ１６〜１８を実行するステップ
２０．前記スレッドの全てがステップ１６〜１８を完了するのを待つステップ
２１．Ｚ［０］の値を変数ａに取得するステップ
２２．Ｚの値をｎワードシフトするステップ
２３．ａの値が０でないか、Ｚ［ｎ−１，…，０］の値がＭ以上の場合は、多倍長整数減算Ｚ−Ｍを実行し、結果をＺに格納するステップ

また、本実施の形態では、
上記のステップ１６にて、“ｃ”の下位ワードとＺ［（ｔ＋ｉ）］との加算を行なった後、加算結果の下位１ワードをＺ［（ｔ＋ｉ）］に出力するステップを実行し、上記のステップ２１にて、Ｚ［２ｎ］の値を変数ａに取得するステップを実行する多倍長整数演算装置を説明した。

１００ 多倍長演算装置、１０１ 計算部、１０２ メモリ、１０３ 通信ポート、１０４ バス、１０５ プロセッサ、１０６ プロセッサ、１０７ 命令デコーダ、１０８ 汎用レジスタ、１０９ 特殊レジスタ。

Claims (8)

1. 制御部と演算部と記憶部とを有し、入力値の加算を行う演算装置であって、
   前記制御部は、
   それぞれのビット幅が共通しており、それぞれのビット幅が前記演算部の演算ビット幅よりも大きい入力値Ｘ及び入力値Ｙを、それぞれ、前記演算部の演算ビット幅ごとに分割し、
   前記記憶部内の所定の記憶領域を割当てて、入力値Ｘから分割されたｎ（ｎ≧２）個の分割値を格納するためのｎ個の変数Ｘ［０］〜Ｘ［ｎ−１］と、入力値Ｙから分割されたｎ個の分割値を格納するためのｎ個の変数Ｙ［０］〜Ｙ［ｎ−１］とを設け、
   入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｘ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、入力値Ｙ内の最下位ビットが含まれる分割値が０番目の変数Ｙ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｙ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｙ［０］〜Ｙ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、前記演算部による加算結果を格納するためのｕ（ｕ＞ｎ）個の変数Ｚ［０］〜Ｚ［ｕ−１］を設け、
   前記演算部は、
   スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行し、
   スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、第１フェーズの処理として、
   入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［ｔ］の値）＋（Ｙ［ｔ］の値）を計算し、加算結果とキャリー値ｃを求め、加算結果をｔ番目の変数Ｚ［ｔ］に格納する処理を行い、
   前記制御部は、
   カウンタ値ｉを１に設定し、前記演算部に第２フェーズの処理を開始させ、
   カウンタ値ｉがｎに達するか、全てのスレッドｔが第２フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   前記制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第２フェーズの１ラウンド分の処理として、
   〈ａ〉（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値とスレッドｔで得られたキャリー値ｃとを用いて、（Ｚ［ｔ＋ｉ］の値）＋ｃを計算し、新たな加算結果と新たなキャリー値ｃを求め、
   〈ｂ〉変数Ｚ［ｔ＋ｉ］の値と新たな加算結果とを比較し、両者が一致している場合に、スレッドｔの第２フェーズの処理を停止し、両者が一致しない場合に、新たな加算結果を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］に格納する
   処理を、行うことを特徴とする演算装置。
2. 制御部と演算部と記憶部とを有し、入力値の減算を行う演算装置であって、
   それぞれのビット幅が共通しており、それぞれのビット幅が前記演算部の演算ビット幅よりも大きい入力値Ｘ及び入力値Ｙを、それぞれ、前記演算部の演算ビット幅ごとに分割し、
   前記記憶部内の所定の記憶領域を割当てて、入力値Ｘから分割されたｎ（ｎ≧２）個の分割値を格納するためのｎ個の変数Ｘ［０］〜Ｘ［ｎ−１］と、入力値Ｙから分割されたｎ個の分割値を格納するためのｎ個の変数Ｙ［０］〜Ｙ［ｎ−１］とを設け、
   入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｘ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、入力値Ｙ内の最下位ビットが含まれる分割値が０番目の変数Ｙ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｙ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｙ［０］〜Ｙ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、前記演算部による減算結果を格納するためのｕ（ｕ＞ｎ）個の変数Ｚ［０］〜Ｚ［ｕ−１］を設け、
   前記演算部は、
   スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行し、
   スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、第１フェーズの処理として、
   入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｙ［ｔ］の値）−（Ｘ［ｔ］の値）を計算し、減算結果とボロー値ｄを求め、減算結果をｔ番目の変数Ｚ［ｔ］に格納する処理を行い、
   前記制御部は、
   カウンタ値ｉを１に設定し、前記演算部に第２フェーズの処理を開始させ、
   カウンタ値ｉがｎに達するか、全てのスレッドｔが第２フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   前記制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第２フェーズの１ラウンド分の処理として、
   〈ａ〉（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値とスレッドｔで得られたボロー値ｄとを用いて、（Ｚ［ｔ＋ｉ］の値）−ｄを計算し、新たな減算結果と新たなボロー値ｄを求め、
   〈ｂ〉変数Ｚ［ｔ＋ｉ］の値と新たな減算結果とを比較し、両者が一致している場合に、スレッドｔの第２フェーズの処理を停止し、両者が一致しない場合に、新たな減算結果を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］に格納する
   処理を、行うことを特徴とする演算装置。
3. 制御部と演算部と記憶部とを有し、入力値の乗算を行う演算装置であって、
   前記制御部は、
   それぞれのビット幅が共通しており、それぞれのビット幅が前記演算部の演算ビット幅である１ワードよりも大きい入力値Ｘ及び入力値Ｙを、それぞれ、１ワードごとに分割し、
   前記記憶部内の所定の記憶領域を割当てて、入力値Ｘから分割されたｎ（ｎ≧２）個の分割値を格納するためのｎ個の変数Ｘ［０］〜Ｘ［ｎ−１］と、入力値Ｙから分割されたｎ個の分割値を格納するためのｎ個の変数Ｙ［０］〜Ｙ［ｎ−１］とを設け、
   入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｘ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、入力値Ｙ内の最下位ビットが含まれる分割値が０番目の変数Ｙ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｙ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｙ［０］〜Ｙ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、前記演算部による計算結果を格納するためのｕ（ｕ＞ｎ）個の変数Ｚ［０］〜Ｚ［ｕ−１］を設け、
   カウンタ値ｉを０に設定し、前記演算部に第１フェーズの処理を開始させ、
   カウンタ値ｉがｎに達するまでの間、前記演算部が第１フェーズの１ラウンド分の処理を終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行し、
   カウンタ値ｉがｎに達するまでの間、前記制御部によりカウンタ値ｉがインクリメントされる度に、スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、第１フェーズの１ラウンド分の処理として、
   〈１−ａ〉入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、入力値Ｙのｉ番目の変数Ｙ［ｉ］の値と、（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値と、スレッドｔで得られたキャリー成分値ｃとを用いて、（Ｘ［ｔ］の値）×（Ｙ［ｉ］の値）＋（Ｚ［ｔ＋ｉ］の値）＋ｃを計算し、
   〈１−ｂ〉計算結果の下位１ワードの値を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］に格納し、計算結果の上位１ワードの値を新たなキャリー成分値ｃとする
   処理を、行い、
   前記制御部は、
   カウンタ値ｉがｎに達すると、前記演算部に第２フェーズの処理を開始させ、
   カウンタ値ｉがｕに達するまでの間、前記演算部が第２フェーズの１ラウンド分の処理を終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   カウンタ値ｉがｕに達するまでの間、前記制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第２フェーズの１ラウンド分の処理として、
   〈２−ａ〉スレッドｔで得られたキャリー成分値ｃが０であるか否かを判断し、キャリー成分値ｃが０である場合にスレッドｔの第２フェーズの処理を停止し、
   〈２−ｂ〉０でない場合に（Ｚ［ｔ＋ｉ］の値）＋ｃを計算し、計算結果の下位１ワードの値を変数Ｚ［ｔ＋ｉ］の新たな値とし、計算結果の上位１ワードの値を新たなキャリー成分値ｃとする
   処理を、行うことを特徴とする演算装置。
4. 制御部と演算部と記憶部とを有し、
   前記演算部の演算ビット幅である１ワード（１ワード＝ｂビット）よりも大きなビット幅の入力値Ｘと法Ｍとに対して、ｒ＝２^ｂ、Ｒ＝ｒ^ｎ（ｎは、法Ｍを１ワードごとに分割した際の法Ｍの分割数であり、ｎ≧２）として定義されたＲと、（−Ｍ^−１ ｍｏｄ ｒ）として定義されたＭＩｎｖとを用いて、（ＸＲ^−１ ｍｏｄ Ｍ）を計算するモンゴメリ・リダクションを行う演算装置であって、
   前記制御部は、
   入力値Ｘ及び法Ｍを、それぞれ１ワードごとに分割し、
   前記記憶部内の所定の記憶領域を割当てて、入力値Ｘから分割された２ｎ個の分割値を格納するための２ｎ個の変数Ｘ［０］〜Ｘ［２ｎ−１］を設け、
   入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（２ｎ−１）番目の変数Ｘ［２ｎ−１］に格納されるようにして、２ｎ個の分割値を変数Ｘ［０］〜Ｘ［２ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、法Ｍから分割されたｎ個の分割値を格納するためのｎ個の変数Ｍ［０］〜Ｍ［ｎ−１］を設け、
   法Ｍ内の最下位ビットが含まれる分割値が０番目の変数Ｍ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｍ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｍ［０］〜Ｍ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、前記演算部による計算結果を格納するｎ個の変数Ｚ［０］〜Ｚ［ｎ−１］を設け、
   前記演算部は、
   スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行し、
   第１フェーズの処理として、
   スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、
   〈１−ａ〉入力値Ｘの０番目の変数Ｘ［０］の値とＭＩｎｖとを用いて、（Ｘ［０］の値）×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとし、
   〈１−ｂ〉法Ｍのｔ番目の変数Ｍ［ｔ］の値と、入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕ＋（Ｘ［ｔ］の値）を計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［ｔ］の新たな値とし、計算結果ｍの上位１ワードの値をキャリー成分値ｃとし、
   ０番目のスレッドであるスレッド０において、
   〈１−ｃ〉スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｘ［０］の新たな値とする
   処理を、行い、
   前記制御部は、
   カウンタ値ｉを１に設定し、前記演算部に第２フェーズの処理を開始させ、
   カウンタ値ｉがｎに達するまで、全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   前記制御部によりカウンタ値ｉがインクリメントされる度に、第２フェーズの１ラウンド分の処理として、
   個々のスレッドｔにおいて、
   〈２−ａ〉入力値Ｘの０番目の変数Ｘ［０］の値とｉ番目の変数Ｘ［ｉ］の値と、ＭＩｎｖとを用いて、｛（Ｘ［０］の値）＋（Ｘ［ｉ］の値）｝×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとし、
   〈２−ｂ〉法Ｍのｔ番目の変数Ｍ［ｔ］の値と、前記ｕと、入力値Ｘの（ｔ＋ｉ）番目の変数Ｘ［ｔ＋ｉ］の値と、スレッドｔで得られたキャリー成分値ｃとを用いて、（Ｍ［ｔ］の値）×ｕ＋（Ｘ［ｔ＋ｉ］の値）＋ｃを計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［ｔ＋ｉ］の新たな値とし、計算結果ｍの上位１ワードの値を新たなキャリー成分値ｃとし、
   ０番目のスレッドであるスレッド０において、
   〈２−ｃ〉スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｘ［０］の新たな値とする
   処理を、行い、
   カウンタ値ｉがｎに達すると、スレッド０において、値０を変数Ｘ［０］の新たな値とし、
   前記制御部は、
   カウンタ値ｉがｎに達すると、スレッド０において値０が変数Ｘ［０］の新たな値とされた後に、前記演算部に第３フェーズの処理を開始させ、
   カウンタ値ｉが２ｎに達するか、全てのスレッドｔが第３フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第３フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   カウンタ値ｉが２ｎに達するまでの間、前記制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第３フェーズの１ラウンド分の処理として、
   〈３−ａ〉スレッドｔで得られたキャリー成分値ｃが０であるか否かを判断し、キャリー成分値ｃが０である場合にスレッドｔの第３フェーズの処理を停止し、
   〈３−ｂ〉０でない場合に、（Ｘ［（ｔ＋ｉ） ｍｏｄ ２ｎ］の値）＋ｃを計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［（ｔ＋ｉ） ｍｏｄ ２ｎ］の新たな値とし、計算結果ｍの上位１ワードの値を新たなキャリー成分値ｃとする
   処理を、行い、
   前記制御部は、
   カウンタ値ｉが２ｎに達した場合、又は全てのスレッドｔが第３フェーズの処理を停止した場合に、前記演算部に第４フェーズの処理を開始させ、
   前記演算部は、
   第４フェーズの処理として、
   変数Ｘ［０］の値を変数ａに格納し、
   変数Ｘ［ｎ］〜Ｘ［２ｎ−１］の値を、それぞれ、変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、
   変数ａの値が０でない場合、又は変数Ｘ［ｎ−１］〜Ｘ［０］の値を連接して得られる値が法Ｍ以上の場合に、Ｘ−Ｍを計算し、計算結果を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、
   変数Ｘ［０］〜Ｘ［ｎ−１］の値を変数Ｚ［０］〜Ｚ［ｎ−１］に格納することを特徴とする演算装置。
5. 制御部と演算部と記憶部とを有し、
   前記演算部の演算ビット幅である１ワード（１ワード＝ｂビット）よりも大きなビット幅の入力値Ｘと法Ｍとに対して、ｒ＝２^ｂ、Ｒ＝ｒ^ｎ（ｎは、法Ｍを１ワードごとに分割した際の法Ｍの分割数であり、ｎ≧２）として定義されたＲと、（−Ｍ^−１ ｍｏｄ ｒ）として定義されたＭＩｎｖとを用いて、（ＸＲ^−１ ｍｏｄ Ｍ）を計算するモンゴメリ・リダクションを行う演算装置であって、
   前記制御部は、
   入力値Ｘ及び法Ｍを、それぞれ１ワードごとに分割し、
   前記記憶部内の所定の記憶領域を割当てて、入力値Ｘから分割された２ｎ個の分割値を格納するためのｖ（ｖはｎの倍数であって、ｖ≧３ｎ）個の変数Ｘ［０］〜Ｘ［ｖ−１］を設け、
   入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（２ｎ−１）番目の変数Ｘ［２ｎ−１］に格納されるようにして、２ｎ個の分割値を変数Ｘ［０］〜Ｘ［２ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、法Ｍから分割されたｎ個の分割値を格納するためのｎ個の変数Ｍ［０］〜Ｍ［ｎ−１］を設け、
   法Ｍ内の最下位ビットが含まれる分割値が０番目の変数Ｍ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｍ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｍ［０］〜Ｍ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、前記演算部による計算結果を格納するｎ個の変数Ｚ［０］〜Ｚ［ｎ−１］を設け、
   前記演算部は、
   スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行し、
   第１フェーズの処理として、
   スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、
   〈１−ａ〉入力値Ｘの０番目の変数Ｘ［０］の値とＭＩｎｖとを用いて、（Ｘ［０］の値）×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとし、
   〈１−ｂ〉法Ｍのｔ番目の変数Ｍ［ｔ］の値と、入力値Ｘのｔ番目の変数Ｘ［ｔ］の値と、前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕ＋（Ｘ［ｔ］の値）を計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［ｔ］の新たな値とし、計算結果ｍの上位１ワードの値をキャリー成分値ｃとし、
   ０番目のスレッドであるスレッド０において、
   〈１−ｃ〉スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｘ［０］の新たな値とする
   処理を、行い、
   前記制御部は、
   カウンタ値ｉを１に設定し、前記演算部に第２フェーズの処理を開始させ、
   カウンタ値ｉがｎに達するまで、全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   前記制御部によりカウンタ値ｉがインクリメントされる度に、第２フェーズの１ラウンド分の処理として、
   個々のスレッドｔにおいて、
   〈２−ａ〉入力値Ｘの０番目の変数Ｘ［０］の値とｉ番目の変数Ｘ［ｉ］の値と、ＭＩｎｖとを用いて、｛（Ｘ［０］の値）＋（Ｘ［ｉ］の値）｝×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとし、
   〈２−ｂ〉法Ｍのｔ番目の変数Ｍ［ｔ］の値と、前記ｕと、入力値Ｘの（ｔ＋ｉ）番目の変数Ｘ［ｔ＋ｉ］の値と、スレッドｔで得られたキャリー成分値ｃとを用いて、（Ｍ［ｔ］の値）×ｕ＋（Ｘ［ｔ＋ｉ］の値）＋ｃを計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［ｔ＋ｉ］の新たな値とし、計算結果ｍの上位１ワードの値を新たなキャリー成分値ｃとし、
   ０番目のスレッドであるスレッド０において、
   〈２−ｃ〉スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｘ［０］の新たな値とする
   処理を、行い、
   カウンタ値ｉがｎに達すると、スレッド０において、値０を変数Ｘ［０］の新たな値とし、
   前記制御部は、
   カウンタ値ｉがｎに達すると、スレッド０において値０が変数Ｘ［０］の新たな値とされた後に、前記演算部に第３フェーズの処理を開始させ、
   カウンタ値ｉが２ｎに達するか、全てのスレッドｔが第３フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第３フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   カウンタ値ｉが２ｎに達するまでの間、前記制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第３フェーズの１ラウンド分の処理として、
   〈３−ａ〉スレッドｔで得られたキャリー成分値ｃが０であるか否かを判断し、キャリー成分値ｃが０である場合にスレッドｔの第３フェーズの処理を停止し、
   〈３−ｂ〉０でない場合に、（Ｘ［ｔ＋ｉ］の値）＋ｃを計算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｘ［ｔ＋ｉ］の新たな値とし、計算結果ｍの上位１ワードの値を新たなキャリー成分値ｃとする
   処理を、行い、
   前記制御部は、
   カウンタ値ｉが２ｎに達した場合、又は全てのスレッドｔが第３フェーズの処理を停止した場合に、前記演算部に第４フェーズの処理を開始させ、
   前記演算部は、
   第４フェーズの処理として、
   変数Ｘ［２ｎ］の値を変数ａに格納し、
   変数Ｘ［ｎ］〜Ｘ［２ｎ−１］の値を、それぞれ、変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、
   変数ａの値が０でない場合、又は変数Ｘ［ｎ−１］〜Ｘ［０］の値を連接して得られる値が法Ｍ以上の場合に、Ｘ−Ｍを計算し、計算結果を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、
   変数Ｘ［０］〜Ｘ［ｎ−１］の値を変数Ｚ［０］〜Ｚ［ｎ−１］に格納することを特徴とする演算装置。
6. 制御部と演算部と記憶部とを有し、
   それぞれのビット幅が共通しており、それぞれのビット幅が前記演算部の演算ビット幅である１ワード（１ワード＝ｂビット）よりも大きい入力値Ｘと入力値Ｙと法Ｍとに対して、ｒ＝２^ｂ、Ｒ＝ｒ^ｎ（ｎは、法Ｍを１ワードごとに分割した際の法Ｍの分割数であり、ｎ≧２）として定義されたＲと、（−Ｍ^−１ ｍｏｄ ｒ）として定義されたＭＩｎｖとを用いて、（ＸＹＲ^−１ ｍｏｄ Ｍ）を計算するモンゴメリ乗算を行う演算装置であって、
   前記制御部は、
   入力値Ｘ、入力値Ｙ及び法Ｍを、それぞれ１ワードごとに分割し、
   前記記憶部内の所定の記憶領域を割当てて、入力値Ｘから分割されたｎ個の分割値を格納するためのｎ個の変数Ｘ［０］〜Ｘ［ｎ−１］と、入力値Ｙから分割されたｎ個の分割値を格納するためのｎ個の変数Ｙ［０］〜Ｙ［ｎ−１］とを設け、
   入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｘ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、入力値Ｙ内の最下位ビットが含まれる分割値が０番目の変数Ｙ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｙ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｙ［０］〜Ｙ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、法Ｍから分割されたｎ個の分割値を格納するためのｎ個の変数Ｍ［０］〜Ｍ［ｎ−１］を設け、
   法Ｍ内の最下位ビットが含まれる分割値が０番目の変数Ｍ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｍ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｍ［０］〜Ｍ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、前記演算部による計算結果を格納する２ｎ個の変数Ｚ［０］〜Ｚ［２ｎ−１］を設け、
   前記演算部は、
   スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行し、
   第１フェーズの処理として、
   スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、
   〈１−ａ〉入力値Ｘの０番目の変数Ｘ［０］の値と、入力値Ｙの０番目の変数Ｙ［０］の値と、ＭＩｎｖとを用いて、（Ｘ［０］の値）×（Ｙ［０］の値）×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとし、
   〈１−ｂ〉法Ｍのｔ番目の変数Ｍ［ｔ］の値と前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕを計算し、２ワードの計算結果をｕｍとし、
   〈１−ｃ〉入力値Ｘの０番目の変数Ｘ［０］の値と入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［０］の値）×（Ｙ［ｔ］の値）を計算し、２ワードの計算結果をｘｙとし、
   〈１−ｄ〉前記ｕｍの下位１ワードと前記ｘｙの下位１ワードとを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値をｔ番目の変数Ｚ［ｔ］に格納し、
   〈１−ｅ〉前記ｍの上位１ワードと前記ｕｍの上位１ワードと前記ｘｙの上位１ワードとを加算し、２ワードの計算結果をキャリー成分値ｃとし、
   ０番目のスレッドであるスレッド０において、
   〈１−ｆ〉スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｚ［０］の新たな値とする
   処理を、行い、
   前記制御部は、
   カウンタ値ｉを１に設定し、前記演算部に第２フェーズの処理を開始させ、
   カウンタ値ｉがｎに達するまで、全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   前記制御部によりカウンタ値ｉがインクリメントされる度に、第２フェーズの１ラウンド分の処理として、
   個々のスレッドｔにおいて、
   〈２−ａ〉０番目の変数Ｚ［０］とｉ番目の変数Ｚ［ｉ］と、入力値Ｘのｉ番目の変数Ｘ［ｉ］と、入力値Ｙの０番目の変数Ｙ［０］と、ＭＩｎｖとを用いて、｛（Ｚ［０］の値）＋（Ｚ［ｉ］の値）＋（Ｘ［ｉ］の値）×（Ｙ［０］の値）｝×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとし、
   〈２−ｂ〉法Ｍのｔ番目の変数Ｍ［ｔ］の値と前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕを計算し、２ワードの計算結果をｕｍとし、
   〈２−ｃ〉入力値Ｘのｉ番目の変数Ｘ［ｉ］の値と入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［ｉ］の値）×（Ｙ［ｔ］の値）を計算し、２ワードの計算結果をｘｙとし、
   〈２−ｄ〉前記ｕｍの下位１ワードと、前記ｘｙの下位１ワードと、ステップｔで得られたキャリー成分値ｃの下位１ワードと、（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値とを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の新たな値とし、
   〈２−ｅ〉前記ｍの上位１ワードと、前記ｕｍの上位１ワードと、前記ｘｙの上位１ワードと、ステップｔで得られたキャリー成分値ｃの上位１ワードとを加算し、２ワードの計算結果を新たなキャリー成分値ｃとし、
   ０番目のスレッドであるスレッド０において、
   〈２−ｆ〉スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｚ［０］の新たな値とする
   処理を、行い、
   カウンタ値ｉがｎに達すると、スレッド０において、値０を変数Ｚ［０］の新たな値とし、
   前記制御部は、
   カウンタ値ｉがｎに達すると、スレッド０において値０が変数Ｘ［０］の新たな値とされた後に、前記演算部に第３フェーズの処理を開始させ、
   カウンタ値ｉが２ｎに達するか、全てのスレッドｔが第３フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第３フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   カウンタ値ｉが２ｎに達するまでの間、前記制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第３フェーズの１ラウンド分の処理として、
   〈３−ａ〉スレッドｔで得られたキャリー成分値ｃが０であるか否かを判断し、キャリー成分値ｃが０である場合にスレッドｔの第３フェーズの処理を停止し、
   〈３−ｂ〉０でない場合に、スレッドｔで得られたキャリー成分値ｃの下位１ワードと変数Ｚ［（ｔ＋ｉ） ｍｏｄ ２ｎ］の値とを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｚ［（ｔ＋ｉ） ｍｏｄ ２ｎ］の新たな値とし、前記ｍの上位１ワードとスレッドｔで得られたキャリー成分値ｃの上位１ワードとを加算し、２ワードの計算結果を新たなキャリー成分値ｃとする
   処理を、行い、
   前記制御部は、
   カウンタ値ｉが２ｎに達した場合、又は全てのスレッドｔが第３フェーズの処理を停止した場合に、前記演算部に第４フェーズの処理を開始させ、
   前記演算部は、
   第４フェーズの処理として、
   変数Ｚ［０］の値を変数ａに格納し、
   変数Ｚ［ｎ］〜Ｚ［２ｎ−１］の値を、それぞれ、変数Ｚ［０］〜Ｚ［ｎ−１］に格納し、
   変数ａの値が０でない場合、又は変数Ｚ［ｎ−１］〜Ｚ［０］の値を連接して得られる値が法Ｍ以上の場合に、Ｚ−Ｍを計算し、計算結果を変数Ｚ［０］〜Ｚ［ｎ−１］に格納することを特徴とする演算装置。
7. 制御部と演算部と記憶部とを有し、
   それぞれのビット幅が共通しており、それぞれのビット幅が前記演算部の演算ビット幅である１ワード（１ワード＝ｂビット）よりも大きい入力値Ｘと入力値Ｙと法Ｍとに対して、ｒ＝２^ｂ、Ｒ＝ｒ^ｎ（ｎは、法Ｍを１ワードごとに分割した際の法Ｍの分割数であり、ｎ≧２）として定義されたＲと、（−Ｍ^−１ ｍｏｄ ｒ）として定義されたＭＩｎｖとを用いて、（ＸＹＲ^−１ ｍｏｄ Ｍ）を計算するモンゴメリ乗算を行う演算装置であって、
   前記制御部は、
   入力値Ｘ、入力値Ｙ及び法Ｍを、それぞれ１ワードごとに分割し、
   前記記憶部内の所定の記憶領域を割当てて、入力値Ｘから分割されたｎ個の分割値を格納するためのｎ個の変数Ｘ［０］〜Ｘ［ｎ−１］と、入力値Ｙから分割されたｎ個の分割値を格納するためのｎ個の変数Ｙ［０］〜Ｙ［ｎ−１］とを設け、
   入力値Ｘ内の最下位ビットが含まれる分割値が０番目の変数Ｘ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｘ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｘ［０］〜Ｘ［ｎ−１］に格納し、入力値Ｙ内の最下位ビットが含まれる分割値が０番目の変数Ｙ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｙ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｙ［０］〜Ｙ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、法Ｍから分割されたｎ個の分割値を格納するためのｎ個の変数Ｍ［０］〜Ｍ［ｎ−１］を設け、
   法Ｍ内の最下位ビットが含まれる分割値が０番目の変数Ｍ［０］に格納され、最上位ビットが含まれる分割値が（ｎ−１）番目の変数Ｍ［ｎ−１］に格納されるようにして、ｎ個の分割値を変数Ｍ［０］〜Ｍ［ｎ−１］に格納し、
   前記記憶部内の所定の記憶領域を割当てて、前記演算部による計算結果を格納するｖ個（ｖはｎの倍数であって、ｖ≧３ｎ）の変数Ｚ［０］〜Ｚ［ｖ−１］を設け、
   前記演算部は、
   スレッド番号として「０〜ｎ−１」が設定されているｎ個のスレッドを並列に実行し、
   第１フェーズの処理として、
   スレッド番号＝ｔ（ｔは「０〜ｎ−１」のうちのいずれか）であるスレッドｔにおいて、
   〈１−ａ〉入力値Ｘの０番目の変数Ｘ［０］の値と、入力値Ｙの０番目の変数Ｙ［０］の値と、ＭＩｎｖとを用いて、（Ｘ［０］の値）×（Ｙ［０］の値）×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとし、
   〈１−ｂ〉法Ｍのｔ番目の変数Ｍ［ｔ］の値と前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕを計算し、２ワードの計算結果をｕｍとし、
   〈１−ｃ〉入力値Ｘの０番目の変数Ｘ［０］の値と入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［０］の値）×（Ｙ［ｔ］の値）を計算し、２ワードの計算結果をｘｙとし、
   〈１−ｄ〉前記ｕｍの下位１ワードと前記ｘｙの下位１ワードとを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値をｔ番目の変数Ｚ［ｔ］に格納し、
   〈１−ｅ〉前記ｍの上位１ワードと前記ｕｍの上位１ワードと前記ｘｙの上位１ワードとを加算し、２ワードの計算結果をキャリー成分値ｃとし、
   ０番目のスレッドであるスレッド０において、
   〈１−ｆ〉スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｚ［０］の新たな値とする
   処理を、行い、
   前記制御部は、
   カウンタ値ｉを１に設定し、前記演算部に第２フェーズの処理を開始させ、
   カウンタ値ｉがｎに達するまで、全てのスレッドｔにおいて第２フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   前記制御部によりカウンタ値ｉがインクリメントされる度に、第２フェーズの１ラウンド分の処理として、
   個々のスレッドｔにおいて、
   〈２−ａ〉０番目の変数Ｚ［０］とｉ番目の変数Ｚ［ｉ］と、入力値Ｘのｉ番目の変数Ｘ［ｉ］と、入力値Ｙの０番目の変数Ｙ［０］と、ＭＩｎｖとを用いて、｛（Ｚ［０］の値）＋（Ｚ［ｉ］の値）＋（Ｘ［ｉ］の値）×（Ｙ［０］の値）｝×ＭＩｎｖを計算し、２ワードの計算結果の下位１ワードの値をｕとし、
   〈２−ｂ〉法Ｍのｔ番目の変数Ｍ［ｔ］の値と前記ｕとを用いて、（Ｍ［ｔ］の値）×ｕを計算し、２ワードの計算結果をｕｍとし、
   〈２−ｃ〉入力値Ｘのｉ番目の変数Ｘ［ｉ］の値と入力値Ｙのｔ番目の変数Ｙ［ｔ］の値とを用いて、（Ｘ［ｉ］の値）×（Ｙ［ｔ］の値）を計算し、２ワードの計算結果をｘｙとし、
   〈２−ｄ〉前記ｕｍの下位１ワードと、前記ｘｙの下位１ワードと、ステップｔで得られたキャリー成分値ｃの下位１ワードと、（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の値とを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を（ｔ＋ｉ）番目の変数Ｚ［ｔ＋ｉ］の新たな値とし、
   〈２−ｅ〉前記ｍの上位１ワードと、前記ｕｍの上位１ワードと、前記ｘｙの上位１ワードと、ステップｔで得られたキャリー成分値ｃの上位１ワードとを加算し、２ワードの計算結果を新たなキャリー成分値ｃとし、
   ０番目のスレッドであるスレッド０において、
   〈２−ｆ〉スレッド０で得られたキャリー成分値ｃの下位１ワードの値を変数Ｚ［０］の新たな値とする
   処理を、行い、
   カウンタ値ｉがｎに達すると、スレッド０において、値０を変数Ｚ［０］の新たな値とし、
   前記制御部は、
   カウンタ値ｉがｎに達すると、スレッド０において値０が変数Ｘ［０］の新たな値とされた後に、前記演算部に第３フェーズの処理を開始させ、
   カウンタ値ｉが２ｎに達するか、全てのスレッドｔが第３フェーズの処理を停止するまで、停止していない全てのスレッドｔにおいて第３フェーズの１ラウンド分の処理が終了する度に、カウンタ値ｉをインクリメントし、
   前記演算部は、
   カウンタ値ｉが２ｎに達するまでの間、前記制御部によりカウンタ値ｉがインクリメントされる度に、停止していないスレッドｔにおいて、第３フェーズの１ラウンド分の処理として、
   〈３−ａ〉スレッドｔで得られたキャリー成分値ｃが０であるか否かを判断し、キャリー成分値ｃが０である場合にスレッドｔの第３フェーズの処理を停止し、
   〈３−ｂ〉０でない場合に、スレッドｔで得られたキャリー成分値ｃの下位１ワードと変数Ｚ［ｔ＋ｉ］の値とを加算し、２ワードの計算結果をｍとし、計算結果ｍの下位１ワードの値を変数Ｚ［ｔ＋ｉ］の新たな値とし、前記ｍの上位１ワードとスレッドｔで得られたキャリー成分値ｃの上位１ワードとを加算し、２ワードの計算結果を新たなキャリー成分値ｃとする処理を、行い、
   前記制御部は、
   カウンタ値ｉが２ｎに達した場合、又は全てのスレッドｔが第３フェーズの処理を停止した場合に、前記演算部に第４フェーズの処理を開始させ、
   前記演算部は、
   第４フェーズの処理として、
   変数Ｚ［２ｎ］の値を変数ａに格納し、
   変数Ｚ［ｎ］〜Ｚ［２ｎ−１］の値を、それぞれ、変数Ｚ［０］〜Ｚ［ｎ−１］に格納し、
   変数ａの値が０でない場合、又は変数Ｚ［ｎ−１］〜Ｚ［０］の値を連接して得られる値が法Ｍ以上の場合に、Ｚ−Ｍを計算し、計算結果を変数Ｚ［０］〜Ｚ［ｎ−１］に格納することを特徴とする演算装置。
8. 請求項１〜７のいずれかに記載の制御部及び演算部の処理を可能にする命令群を含んでいることを特徴とするプログラム。

Images