(57)【特許請求の範囲】
【請求項１】
ある値ＡとＢの乗算をし、法Ｎによる剰余算を行って、結果Ｙを計算するモンゴメリ法用乗算剰余計算装置において、
Ａのある１桁の値と、Ｂのある１桁の値と、キャリー値との３値を入力とし、Ａのある１桁の値とＢのある１桁の値の乗算を行い、これにキャリー値を加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力する第１の積和計算手段と、
Ｎのある１桁の値と、ある１桁の値ｍと、キャリー値との３値を入力とし、Ｎのある１桁の値とある値ｍとの乗算を行い、これにキャリー値を加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力する第２の積和計算手段と、
第１の積和計算手段の出力の下位桁と、第２の積和計算手段の出力の下位桁と、変数Ｙのある１桁と、キャリー値とを加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力し、該下位桁を変数Ｙのある１桁に格納する加算手段と、
を備えることを特徴とするモンゴメリ法用乗算剰余計算装置。
【請求項２】
前記第１の積和計算手段の演算と、前記第２の積和計算手段の演算とは、並列に行われることを特徴とする請求項１に記載のモンゴメリ法用乗算剰余計算装置。
【請求項３】
前記モンゴメリ法用乗算剰余計算装置は、公開鍵暗号方式の演算に使用されることを特徴とする請求項１に記載のモンゴメリ法用乗算剰余計算装置。
【請求項４】
前記演算の入力及び出力の１桁の値は、プロセッサが単精度の数値を表す場合に用いられるビット数からなることを特徴とする請求項１に記載のモンゴメリ法用乗算剰余計算装置。
【請求項５】
前記加算手段が演算を行っている間に、前記第１の積和計算手段と、前記第２の積和計算手段が次回の演算を行うことを特徴とする請求項１に記載のモンゴメリ法用乗算剰余計算装置。
【請求項６】
Ａの最下位の１桁の値と、Ｂのある１桁の値と、結果を格納する変数Ｙの１桁とを入力とし、Ａの最下位の１桁の値と、Ｂのある１桁の値とを乗算し、これに変数Ｙの１桁を加算した結果を、前記第１の積和計算手段へのキャリー値の初期値としての上位桁の値と、下位桁の２値として出力する第３の積和計算手段と、
該第３の積和計算手段の出力の内の下位桁と、モンゴメリ法用のパラメータとを入力し、これらを乗算して出力する乗算手段と、
該第３の積和計算手段の出力の内の下位桁と、該乗算手段の出力と、Ｎのある１桁の３値を入力として、Ｎのある１桁の値と該乗算手段の出力とを乗算し、これらに該第３の積和計算手段の出力の内の下位桁を加算し、加算結果の上位桁を前記第２の積和計算手段へのキャリー値の初期値として出力する第４の積和計算手段と、
を更に備えることを特徴とする請求項１に記載のモンゴメリ法用乗算剰余計算装置。
【請求項７】
前記第１の積和計算手段と、前記第２の積和計算手段と、前記加算手段のそれぞれの出力であるキャリー値と、前記加算手段の演算後の変数Ｙの最上位桁値を入力し、これらを加算した結果の上位桁を変数Ｙの最上位桁に、下位桁を変数Ｙの上位から２番目の桁に格納する第２の加算手段を更に備えることを特徴とする請求項１に記載のモンゴメリ法用乗算剰余計算装置。
【請求項８】
ある値ＡとＢの乗算をし、法Ｎによる剰余算を行って、結果Ｙを計算するモンゴメリ法用乗算剰余計算方法において、
（ａ）第１の積和計算手段が、Ａのある１桁の値と、Ｂのある１桁の値と、キャリー値との３値を入力とし、Ａのある１桁の値とＢのある１桁の値の乗算を行い、これにキャリー値を加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力し、
（ｂ）第２の積和計算手段が、Ｎのある１桁の値と、ある１桁の値ｍと、キャリー値との３値を入力とし、Ｎのある１桁の値とある値ｍとの乗算を行い、これにキャリー値を加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力し、
（ｃ）加算手段が、ステップ（ａ）の出力の下位桁と、ステップ（ｂ）の出力の下位桁と、変数Ｙのある１桁と、キャリー値とを加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力し、該下位桁を変数Ｙのある１桁に格納する、
ことを特徴とするモンゴメリ法用乗算剰余計算方法。
【請求項９】
モンゴメリのアルゴリズムを用いて、プロセッサの単精度（ｋビット）演算による乗算剰余計算を行う装置において、
積和演算を行い、その演算結果を上位ｋビットと下位ｋビットとに分けて出力する第１積和回路と、
積和演算を行いその演算結果を上位ｋビットと下位ｋビットとに分けて出力する第２積和回路と、
加算演算を行いその演算結果を上位２ビットと下位ｋビットとに分けて出力する加算回路と、
前記第１積和回路で乗算される２数を保持する第１及び第２レジスタと、
前記加算回路の下位ｋビット出力を保持し、前記加算回路のその次の回のｋビット入力を格納する第３レジスタと、
モンゴメリのアルゴリズムにおけるパラメータの値を保持する第４レジスタと、
剰余の法を保持する第５レジスタと、
前記第１積和回路の上位kビット出力を保持し、同第1積和回路のその次の回の加算される入力となる数を格納する第6レジスタと、
前記第2積和回路の上位ｋビット出力を保持し、同第２積和回路のその次の回の加算される入力となる数を格納する第７レジスタと、
前記加算回路の上位２ビット出力を保持し、同加算回路のその次の回の入力となる数を格納する第８レジスタとを備え、
前記第１積和回路は、前記第１及び第２レジスタに保持された２数の所定ビットの値を乗算し、その乗算結果に前記第６レジスタに保持された値を加算する演算を行い、前記第２積和回路は、前記第４レジスタに保持された値と前記第５レジスタに保持された数の所定ビットの値とを乗算し、その乗算結果に前記第７レジスタに保持された値を加算する演算を行い、前記加算回路は、前記第１積和回路の下位ｋビット出力と前記第２積和回路の下位ｋビット出力と前記第３レジスタに保持された所定ビットの値と前期第８レジスタに保持された値を加算する演算を行うように構成したことを特徴とするモンゴメリ法による乗算剰余計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、公開鍵暗号系のＲＳＡ暗号処理において、モンゴメリのアルゴリズムを用いて乗算剰余計算を高速に行う乗算剰余計算装置に関する。
【背景技術】
【０００２】
近年におけるコンピュータネットワークの発達により、データベースを検索する機会、電子メール，電子ニュース等の電子化された情報をネットワークを経由して送受する機会が急速に増加してきている。更に、これらを利用して、オンラインショッピング等のサービスも提供されつつある。しかし、それに伴って、ネットワーク上の電子化されたデータを盗聴する、改竄する、他人になりすましてサービスを無償で受ける等の問題も指摘されている。特に、無線を利用したネットワークにおいては、傍受が容易なために、これらの問題を防止する対策が望まれている。【０００３】
これらの問題に対して暗号技術を応用した暗号化電子メール，利用者認証システムが提案され、種々のネットワークにも導入されつつある。
この意味で、コンピュータネットワークにおいては暗号化が必須の技術であるといえる。このような暗号技術の中の一つにディジタル署名即ち認証に適した公開鍵暗号方式がある。公開鍵暗号方式は、暗号化／復号に大量の演算処理が必要なために高速化が望まれており、様々な高速化アルゴリズムが発表されている。【０００４】
暗号化方式は、大別すると秘密鍵暗号系と公開鍵暗号系との二つに分類できる。秘密鍵暗号系は、送信者と受信者とが同じ暗号鍵を持つことにより暗号通信を行う方式である。即ち、秘密鍵暗号系では、あるメッセージを秘密の暗号鍵に基づいて暗号化して相手に送り、受け手はこの暗号鍵を用いて暗号文を復号して元のメッセージに戻して情報を入手する。公開鍵暗号系は、送信者が公開されている受信者の公開鍵でメッセージを暗号化して送信し、受信者が自分の秘密鍵でその暗号化メッセージを復号することにより通信を行う方式である。【０００５】
即ち、公開鍵暗号系では、公開鍵は暗号化のための鍵、秘密鍵は公開鍵により暗号化された暗号を復号するための鍵であり、公開鍵で暗号化した暗号は秘密鍵でのみ復号することができる。【０００６】
秘密鍵暗号系では、個人が秘密に保管しなければならない鍵が通信相手の数だけ必要であり、必要な総鍵数はｎ人のネットワークの場合ｎ（ｎ−１）／２個である。また、初めて通信する相手に対しては、何らかの方法で秘密鍵の配送が必要であるという欠点がある。【０００７】
この欠点を解消するために、大規模なネットワークでは、鍵管理センタを設置し、センタとの間の秘密鍵のみを保管し、暗号通信を行う場合は、センタから送信相手との秘密鍵を得る方法が用いられる。【０００８】
一方、公開鍵暗号系では、個人が秘密に保管する鍵は自分の秘密鍵のみであり、必要な総秘密鍵数もｎ人のネットワークの場合ｎ個である。
また、初めて通信する相手に対しては、公開鍵の配送を行えば良く、鍵管理センタを設置して、ユーザの公開鍵をｎ個公開簿に登録し、センタから送信相手の公開鍵を得る方法が用いられる。【０００９】
この場合、センタは公開鍵の改竄を防ぐだけで、秘密に保管する必要がない。但し、公開鍵方式は秘密鍵方式に比べて鍵のビット数が大きいため保管に要するファイルサイズは大きくなる。また、認証の場合、秘密鍵暗号系では、例えば送信するメッセージを秘密鍵で圧縮変換し、送信文に付加して送り、受信側では同様に圧縮変換して比較する方式がとられている。【００１０】
しかし、送受信が同じ鍵であるため、受信者は認証データを偽造することができる。これに対して、公開鍵暗号系では、秘密鍵で暗号化することができるのは本人だけであるので、偽造することはできない。公開鍵暗号系では、送信者はメッセージを圧縮変換して秘密鍵で暗号化し、公開鍵を送信文に付加して送り、受信者は送信者の公開鍵で付加されたデータを復号し、同様に圧縮変換したものと比較する方式がとられている。この場合、受信者は不正ができない。【００１１】
このように認証系では公開鍵暗号系の技術は必要不可欠であるといえる。しかし、公開鍵暗号系には、暗号化／復号に大量の演算処理が必要であるという大きな欠点があるため、一般には、処理が速い秘密鍵暗号系をメッセージの暗号化に、公開鍵暗号系は認証用にというように組み合わせて用いられる場合が多い。【００１２】
公開鍵暗号系の中で、現在最も有力なものが1977年にリヴェスト（Rivest），シャミア（Shamir）及びエイドルマン（Adlman）の三人によって発明されたＲＳＡ暗号である。
このＲＳＡ暗号の基本原理は次のようなものである。
（ＲＳＡの基本アルゴリズム）
暗号鍵（ｅ，Ｎ）と対応する復号鍵（ｄ，Ｎ）とにおいて、ｅとＮとは公開鍵であり、ｄは秘密鍵である。【００１３】
平文をＭ，暗号文をＣとすると、暗号化Ｅと復号Ｄとのアルゴリズムは次のようにあらわされる。
Ｃ＝Ｅ（Ｍ）＝Ｍe mod Ｎ
Ｍ＝Ｄ（Ｃ）＝Ｃd mod Ｎ
但し、ｄ・ｅ＝１mod ＬＣＭ｛（ｐ−１），（ｑ−１）｝
Ｎ＝ｐ・ｑ
ＬＣＭ：最小公倍数（lowest common multiple）
ｐ，ｑは大きな素数
通常、ｅ，ｄ，Ｍ，Ｎなどは1024ビット程度の大きな整数が用いられているので、高速指数計算法を使用しても１回のＲＳＡ演算で平均1500回程度の多重精度乗算と剰余算とを行わなければならない。【００１４】
特に剰余計算については、演算処理を高速化するために、近似法，剰余テーブル方式，モンゴメリのアルゴリズム等、多くの高速化手法が提案されている。
このような、ＲＳＡ暗号に代表される公開鍵暗号系の多くで利用される、べき乗剰余アルゴリズムを高速に処理するためには、１回あたりの剰余アルゴリズムの高速化が要求される。【００１５】
この剰余演算の高速化を実現する一方法であるモンゴメリのアルゴリズムについて説明する。モンゴメリのアルゴリズムについては、Modulo Multiplication Without Trial Division, Peter L. Montgomery, Mathematics of Computation, Volume 44, Number 170, April 1985 pp. 519〜528を参照されたい。
（モンゴメリのアルゴリズム）
モンゴメリのアルゴリズムは、剰余の法Ｎ（Ｎ＞１）と、剰余の法Ｎと互いに素である基数Ｒ（Ｒ＞Ｎ）とを用いると、被剰余数ＴからＴＲ-1mod Ｎの計算が基数Ｒによる除算のみで行えることを利用して、Ｎによる除算を用いることなく剰余計算を行うアルゴリズムである。【００１６】
以下において、Ｎ，Ｎ′，Ｒ，Ｒ-1及びＴは整数であり、被剰余数Ｔは０≦Ｔ＜Ｒ・Ｎ、Ｒ-1は剰余の法Ｎの上での基数Ｒの逆数であり、Ｒ・Ｒ-1−Ｎ・Ｎ′＝１（０≦Ｒ-1＜Ｎ，０≦Ｎ′＜Ｒ）の関係を満たす。【００１７】
更に、この基数Ｒに２のベキ乗数を使用した場合、基数Ｒによる除算をシフト操作に置き換えることができるため、Ｔ→ＴＲ-1mod Ｎの計算の高速処理が可能となる。
次に、アルゴリズム１として、Ｔ→ＴＲ-1mod ＮのアルゴリズムＲＥＤＣ（Ｔ）を示す。【００１８】
但し、アルゴリズム１において（Ｔ＋ｍ・Ｎ）／Ｒは必ず割り切れることが証明されている。
（アルゴリズム１）
Ｔ→ＴＲ-1mod ＮのアルゴリズムＹ＝ＲＥＤＣ（Ｔ）は次のようにあらわされる。
Ｍ＝（Ｔmod Ｒ）・Ｎ′mod Ｒ
Ｙ＝（Ｔ＋Ｍ・Ｎ）／Ｒ
if  Ｙ≧Ｎ  then  Ｙ＝Ｙ−Ｎ
if  Ｙ＜Ｎ  then  return  Ｙ
１回のＲＥＤＣでは、剰余Ｔmod ＮではなくＴＲ-1mod Ｎが求められるだけである。
よって、剰余Ｔmod Ｎを求めるためには、次に示すようにＲＥＤＣ（Ｔ）と、予め求めておいたＲ2mod Ｎとの積で、再びＲＥＤＣを行えば良い。
ＲＥＤＣ（ＲＥＤＣ（Ｔ）・（Ｒ2 mod Ｎ））
＝（ＴＲ-1mod Ｎ）・（Ｒ2 mod Ｎ）・Ｒ-1mod Ｎ
＝ＴＲ-1・Ｒ2 ・Ｒ-1mod Ｎ
＝Ｔmod Ｎ
このようにして、剰余Ｔmod Ｎを求めることができる。
（ＲＥＤＣの多重精度計算への拡張）
次に、剰余の法Ｎまたは基数Ｒが多倍長即ち多重精度である場合について、ＲＥＤＣのアルゴリズムを拡張する。【００１９】
剰余の法Ｎ，基数Ｒが多重精度である場合、ＲＥＤＣの（Ｔmod Ｒ）・Ｎ′及びＭ・Ｎの計算は、多重精度×多重精度の処理となり、汎用の計算機では非常に大きな処理量と処理時間とが必要となる。そこで、この部分を多重精度×単精度の処理で行えるように拡張したアルゴリズム２を示す。
（アルゴリズム２）
ＲＥＤＣを多重精度へ拡張したアルゴリズムは次に示すようになる。被剰余数Ｔ，パラメータＮ′，出力用変数Ｙが何れもｒ進数で、
Ｔ＝（ｔg-1，ｔg-2，…，ｔ0 ）r ，
Ｎ＝（ｎg-1 ，ｎg-2，…，ｎ0 ）r ，
Ｙ＝（ｙg ，ｙg-1 ，…，ｙ0 ）r，
ｎ’0，
ｒ＝２k，
Ｒ＝ｒg 
とあらわされる場合、次に示すｊ＝０〜ｇ−１の繰り返し処理によりＴＲ-1modＮを多重精度×単精度として、以下のアルゴリズムによって求めることができる。なお、ここで、（  ）ｒは、ｒ進数で表された数であることを示す。また、ここで単精度とはｒ進数１桁のこととし、同じ文字を使用した場合、基本的に大文字を多重精度、小文字を単精度、小文字の添字を多重精度での桁の位置とする。
Ｙ＝Ｔ
for   ｊ＝０  to  ｇ−１
ｍ＝ｙ0 ・ｎ’0 mod ｒ
Ｙ＝Ｙ＋ｍ・Ｎ
Ｙ＝Ｙ／ｒ
next
if  Ｙ≧Ｎ  then  Ｙ＝Ｙ−Ｎ
if  Ｙ＜Ｎ  then  return  Ｙ
このようにして得られるＴＲ-1mod Ｎと、上述したように予め求めておいたＲ2 mod Ｎとの積で再びＲＥＤＣを行うことにより、Ｔmod Ｎを求めることができる。
（ＲＥＤＣの多重精度乗算剰余への拡張）
次に、ＲＥＤＣのアルゴリズムを乗算剰余演算に拡張する。【００２０】
上記のアルゴリズムにおいて、入力Ｔは０≦Ｔ＜Ｒ・Ｎを満たす値であるが、実際のＲＳＡ演算では、入力Ｔが整数Ａ，Ｂ（０≦Ａ，Ｂ＜Ｎ）の乗算結果であることが多い。
その場合、整数Ａ，Ｂの乗算も多重精度整数演算であるため、多重精度拡張ＲＥＤＣと同様の繰り返し計算が行われる。【００２１】
この場合、乗算とＲＥＤＣとを別々に繰り返し計算すると、繰り返し計算制御によるロスが２倍になってしまう。
そこで、乗算とＲＥＤＣとを同一の繰り返しループで行えるように拡張したアルゴリズム３を示す。
（アルゴリズム３）
ＲＥＤＣを多重精度乗算剰余へ拡張したアルゴリズムＲＥＤＣ（Ａ×Ｂ）は次に示すようになる。【００２２】
乗算する２数Ａ，Ｂ，パラメータＮ′，モンゴメリ乗算のパラメータｎ’0，出力用変数Ｙが何れもｒ進数で、
Ａ＝（ａg-1 ，ａg-2，…，ａ0 ）r ，
Ｂ＝（ｂg-1 ，ｂg-2，…，ｂ0 ）r ，
Ｎ＝（ｎg-1 ，ｎg-2，…，ｎ0 ）r ，
Ｙ＝（ｙg ，ｙg-1，…，ｙ0 ）r ，
ｎ’0，
ｒ＝２k，
Ｒ＝ｒg 
とあらわされる場合、次に示すｊ＝０〜ｇ−１の繰り返し処理により、ＡＢＲ-1mod Ｎを多重精度×単精度の計算として求めることができる。
Ｙ＝０
for   ｊ＝０  to  ｇ−１
Ｙ＝Ｙ＋Ａ・ｂj
ｍ＝ｙ0 ・ｎ’0 mod ｒ
Ｙ＝Ｙ＋ｍ・Ｎ
Ｙ＝Ｙ／ｒ
next
if  Ｙ≧Ｎ  then  Ｙ＝Ｙ−Ｎ
if  Ｙ＜Ｎ  then  return  Ｙ
上記のアルゴリズム３においては、Ａ、Ｎが多重精度で、ｂｊ、ｎ’０が単精度であり、Ａとｂｊの乗算を行っているので、多重精度×単精度の計算として演算が行われている。【００２３】
このようにして得られるＡＢＲ-1mod Ｎと、上述したように予め求めておいたＲ2 mod Ｎとの積で再びＲＥＤＣを行うことにより、ＡＢmod Ｎを求めることができる。
（ＲＥＤＣの単精度×単精度処理への拡張）
アルゴリズム３では、多重精度のモンゴメリ乗算剰余を多重精度×単精度で実現可能としているが、この多重精度×単精度の計算部分をさらに単精度×単精度の計算を組み合わせて行えるよう拡張する。【００２４】
この場合、Ａ×ｂi の計算部分とｍ×Ｎの計算部分とが繰り返し計算となり、上述の場合と同様に２つの乗算を別々に繰り返し計算すると、繰り返し計算制御によるロスが２倍になってしまう。【００２５】
そこで、２つの乗算を同一の繰り返しループで行えるようにすれば、ロスの低減が可能である。
２つの乗算を同一の繰り返しループで行えるように拡張したアルゴリズム４を示す。
（アルゴリズム４）
ＲＥＤＣを単精度×単精度へ拡張したアルゴリズムＲＥＤＣ（Ａ×Ｂ）は次に示すようになる。【００２６】
乗算する２数Ａ，Ｂ，パラメータＮ′，モンゴメリ乗算のパラメータｎ’0，出力用変数Ｙ，キャリー変数Ｃが何れもｒ進数で、
Ａ＝（ａg-1 ，ａg-2，…，ａ0 ）r ，
Ｂ＝（ｂg-1 ，ｂg-2，…，ｂ0 ）r ，
Ｎ＝（ｎg-1 ，ｎg-2，…，ｎ0 ）r ，
Ｙ＝（ｙg ，ｙg-1，…，ｙ0 ）r ，
Ｃ＝（ｃ1 ，ｃ0）r ，
ｎ’0，
ｒ＝２k，
Ｒ＝ｒg 
とあらわされ、ｒ進１桁の一時変数をtmp1，tmp2，tmp3，tmp4とする場合、次に示すｉ，ｊの繰り返し処理によりＡＢＲ-1mod Ｎを単精度×単精度の計算で求めることができる。【００２７】
Ｙ＝０
for   ｊ＝０  to  ｇ−１                  ……………………………
（tmp2，tmp1）r ＝ｙ0 ＋ａ0・ｂj
ｍ＝tmp1・ｎ’0 mod ｒ
（tmp4，tmp1）r ＝tmp1＋ｍ・ｎ0            コア前処理
（ｃ1 ，ｃ0）r ＝tmp2＋tmp4
for   ｉ＝０  to  ｇ−１                  ……………………………
（tmp3，tmp2，tmp1）r ＝ｙi＋（ｃ1 ，ｃ0 ）r ＋ａi ・ｂj 
（tmp4，ｙi-1 ）r ＝tmp1＋ｍ・ｎi          コア処理
（ｃ1 ，ｃ0 ）r ＝tmp4＋（tmp3，tmp2）r
next  ｉ                                  ……………………………
（ｃ1 ，ｃ0）r ＝（ｃ1 ，ｃ0 ）r ＋ｙg 
ｙg-1 ＝ｃ0                                コア後処理
ｙg ＝ｃ1
next  ｊ                                  ……………………………
if  Ｙ≧Ｎ  then  Ｙ＝Ｙ−Ｎ                  補正処理
if  Ｙ＜Ｎ  then  return  Ｙ
ここで、（  ）r は、括弧内のｒ進数１桁の変数を多重精度として扱うことを示している。tmp1〜tmp４、ｃ０、ｃ１は、ｒ進数で表された多重精度の数を複数のビットに列に分割し、それぞれを単精度の値として表したものである。たとえば、tmp1は、単精度の積和計算ｙ０＋a０・ｂｊの計算結果の下半分のビットで表される単精度の値であり、tmp2は、当該積和計算の計算結果の上半分のビットで表される単精度の値である。また、tmp3，ｃ1 はｒ進数１桁で表現しているが、内容は１ビットの値である。【００２８】
出力用変数Ｙについて、計算に使用する値がｙi のとき、出力がｙi-1 に格納されるのは、アルゴリズム３におけるＹ＝Ｙ／ｒの機能をこれにより実現しているためである。
また、便宜上、外側のループをｊループ、内側のループをｉループと呼び、ｊループの始めからｉループまでをコア前処理、ｉループ内の処理をコア処理、ｉループの終わりからｊループの終わりまでをコア後処理と呼ぶこととする。【００２９】
図１は、上述したアルゴリズム４のコア処理を実行する乗算剰余計算装置の構成図である。
なお、以下のすべての説明において、ｋビットのｋとは、単精度の値が表されるビット数であり、３２ビットプロセッサの場合であれば、ｋは３２となる。【００３０】
図１に示す乗算剰余計算装置は、内部で乗算及び加算を行うα積和回路10及びβ積和回路11と、乗算する一方の数Ａ：（ａg-1，ａg-2 ，…，ａ0）を保持するＡレジスタ１２と、乗算する一方の数Ｂ：（ｂg-1 ，ｂg-2，…，ｂ0 ）を保持するＢレジスタ１３と、剰余の法Ｎ：（ｎg-1 ，ｎg-2 ，…，ｎ0 ）を保持するＮレジスタ１４と、β積和回路１１の出力の下位ｋビットを格納するＹレジスタ１５と、モンゴメリのパラータｍを保持するｍレジスタ１６と、α積和回路１０の出力の上位（ｋ＋１）ビット及びβ積和回路１１の出力の上位ｋビットを加算するキャリー計算部としての加算回路１７と、加算回路１７の加算結果を格納するＣレジスタ１８と、ｊの値と０とを比較して出力を選択する選択回路１９とを有する。【００３１】
また、α積和回路１０，β積和回路１１の内部構成を図２Ａ，Ｂに夫々示す。
α積和回路１０は、Ａレジスタ１２及びＢレジスタ１３からの出力を乗算するｋビット乗算器２０と、ｋビット乗算器２０の出力及び選択回路１９（Ｙレジスタ１５）の出力を加算する2kビット加算器２１ と、2kビット加算器２１の出力及びＣレジスタ１８の出力を加算する2k＋１ビット加算器２２とを有する。【００３２】
β積和回路１１は、Ｎレジスタ１４及びｍレジスタ１６からの出力を乗算するｋビット乗算器２３と、ｋビット乗算器２３の出力及びα積和回路１０からの下位ｋビットの出力を加算する2kビット加算器２４とを有する。【００３３】
図３は、アルゴリズム４のコア処理の内容を示す説明図である。
α積和回路１０内にて、Ａレジスタ１２の出力ａi（ｋビット）とＢレジスタ１３の出力ｂj（ｋビット）とを乗算し、その乗算結果（２ｋビット；３０）に、選択回路１９（Ｙレジスタ１５）の出力（ｋビット；３１）とＣレジスタ１８の出力（ｋ＋１ビット；３２）とを加算する。【００３４】
なお、選択回路１９は、ｊの値と０とを比較し、ｊの値が０である場合にはα積和回路１０へ０を出力し、ｊの値が０でない場合にはＹレジスタ１５の格納値ｙiをα積和回路１０へ出力する。【００３５】
α積和回路１０は、その演算結果（２ｋ＋１ビット；３３）の上位（ｋ＋１）ビット（３４）を加算回路１７へ出力し、その下位ｋビット（３５）をβ積和回路１１へ出力する。【００３６】
β積和回路１１内にて、Ｎレジスタ１４の出力ｎi（ｋビット）とｍレジスタ１６の出力（ｋビット）とを乗算し、その乗算結果（２ｋビット；３６）にα積和回路１０からの下位ｋビット出力（３５）を加算する。【００３７】
β積和回路１１は、その演算結果（２ｋビット；３７）の上位ｋビット（３８）を加算回路１７へ出力し、その下位ｋビット（３９）をＹレジスタ１５へ出力する。Ｙレジスタ１５は、そのｋビットのデータを値ｙi-1 として格納する。【００３８】
加算回路１７は、α積和回路１０からの出力（ｋ＋１ビット；３４）とβ積和回路１１からの出力（ｋビット；３８）とを加算し、その加算結果（ｋ＋１ビット）をＣレジスタ１８へ出力する。Ｃレジスタ１８は、これを格納する。【００３９】
アルゴリズム４の変形例をアルゴリズム５として説明する。
（アルゴリズム５）
乗算する２数Ａ，Ｂ，パラメータＮ，モンゴメリ乗算のパラメータｎ’0，出力用変数Ｙが何れもｒ進数で、
Ａ＝（ａg-1 ，ａg-2，…，ａ0 ）r ，
Ｂ＝（ｂg-1 ，ｂg-2，…，ｂ0 ）r ，
Ｎ＝（ｎg-1 ，ｎg-2，…，ｎ0 ）r ，
Ｙ＝（ｙg ，ｙg-1，…，ｙ0 ）r ，
ｎ’0，
ｒ＝２k，
Ｒ＝ｒg 
とあらわされ、ｒ進数１桁の一時変数をtmp1，tmp2，tmp4，キャリー変数をｃ1，ｃ2とする場合、次に示すｉ，ｊの繰り返し処理によりＡＢＲ-1mod Ｎを単精度×単精度の計算として求めることができる。【００４０】
Ｙ＝０
for   ｊ＝０  to  ｇ−１                  ……………………………
（tmp2，tmp1）r ＝ｙ0 ＋ａ０・ｂｊ 
ｍ＝tmp1・ｎ’0 mod ｒ
（tmp4，tmp1）r ＝tmp1＋ｍ・ｎ0            コア前処理
（ｃ2 ，ｃ1）r ＝tmp2＋tmp4
for   ｉ＝１  to  ｇ−１                  ……………………………
（tmp2，tmp1）r ＝ｙi ＋ｃ1＋ａi ・ｂj 
（tmp4，ｙi-1 ）r ＝tmp1＋ｍ・ｎi          コア処理
（ｃ2 ，ｃ1）r ＝tmp4＋tmp2＋ｃ2 
next  ｉ                                  ……………………………
（ｃ2 ，ｃ1）r ＝（ｃ2 ，ｃ1 ）r ＋ｙg 
ｙg-1 ＝ｃ1                                 コア後処理
ｙg ＝ｃ2
next  ｊ                                  ……………………………
if  Ｙ≧Ｎ  then  Ｙ＝Ｙ−Ｎ                  補正処理
if  Ｙ＜Ｎ  then  return  Ｙ
ここで、（  ）r は、括弧内のｒ進数１桁の変数を多重精度として扱うことを示している。またキャリー変数ｃ2 はｒ進数１桁で表現しているが、内容は１ビットの値である。【００４１】
図４は、上述したアルゴリズム５のコア処理を実行する乗算剰余計算装置の構成図である。
図４に示す乗算剰余計算装置は、内部で乗算及び加算を行う第１積和回路１０ａ及び第２積和回路１１ａと、乗算する一方の数Ａ：（ａg-1 ，ａg-2 ，…，ａ0 ）を保持する第１レジスタとしてのＡレジスタ１２と、乗算する一方の数Ｂ：（ｂg-1，ｂg-2 ，…，ｂ0 ）を保持する第２レジスタとしてのＢレジスタ１３と、第２積和回路１１ａの前回の下位ｋビット出力を保持し、次回の下位ｋビット出力を格納する第３レジスタとしてのＹレジスタ１５と、キャリー変数ｃ1を保持する第４レジスタとしてのｃ1レジスタ１８ａと、剰余の法Ｎ：（ｎg-1 ，ｎg-2 ，…，ｎ0）を保持する第５レジスタとしてのＮレジスタ１４と、モンゴメリアルゴリズムにおけるパラータｍを保持する第６レジスタとしてのｍレジスタ１６と、キャリー変数ｃ2を保持する第７レジスタとしてのｃ2レジスタ１８ｂと、第１積和回路１０ａの上位ｋビット出力，第２積和回路１１ａの上位ｋビット出力及びｃ2レジスタ１８ｂの出力を加算するキャリー計算部としての加算回路１７ａと、ｊの値と０とを比較してその出力を選択する選択回路１９とを有する。【００４２】
また、第１積和回路１０ａ，第２積和回路１１ａの内部構成を図５Ａ，Ｂに夫々示す。
第１積和回路１０ａは、ｋビット乗算器２０と2kビット加算器２１と2kビット加算器２２ａとを有する。ｋビット乗算器２０は、Ａレジスタ１２及びＢレジスタ１３からの出力を乗算し、2kビット加算器２１は、ｋビット乗算器２０の出力と選択回路１９（Ｙレジスタ１５）の出力とを加算し、2kビット加算器２２ａは、2kビット加算器２１の出力とｃ1レジスタ１８ａの出力とを加算する。【００４３】
なお、図５Ａに示す構成例では、乗算結果に選択回路１９（Ｙレジスタ１５）の出力を先に加算し、その後にｃ1レジスタ１８ａの出力を加算するようになっているが、これとは逆に、先にｃ1レジスタ１８ａの出力、その後に選択回路１９（Ｙレジスタ１５）の出力を加算するように構成しても良い。【００４４】
第２積和回路１１ａは、Ｎレジスタ１４及びｍレジスタ１６からの出力を乗算するｋビット乗算器２３と、ｋビット乗算器２３の出力及び第１積和回路１０ａからの下位ｋビットの出力を加算する2kビット加算器２４とを有する。【００４５】
図６は、アルゴリズム５のコア処理の内容を示す説明図である。
第１積和回路１０ａ内にて、Ａレジスタ１２の出力ａi（ｋビット）とＢレジスタ１３の出力ｂj（ｋビット）とを乗算し、その乗算結果（２ｋビット；３０）に、選択回路１９（Ｙレジスタ１５）の出力（ｋビット；３１）とｃ1レジスタ１８ａの出力（ｋビット；３２ａ）とを加算する。なお、選択回路１９は、ｊの値と０とを比較し、ｊの値が０である場合には第１積和回路１０ａへ０を出力し、ｊの値が０でない場合にはＹレジスタ１５の格納値ｙiを第１積和回路１０ａへ出力する。第１積和回路１０ａは、その演算結果（２ｋビット；３３）の上位ｋビット（３４）を加算回路１７ａへ出力し、その下位ｋビット（３５）を第２積和回路１１ａへ出力する。【００４６】
第２積和回路１１ａ内にて、Ｎレジスタ１４の出力ｎｉ（ｋビット）とｍレジスタ１６の出力（ｋビット）とを乗算し、その乗算結果（２ｋビット；３６）に、第１積和回路１０ａからの出力下位ｋビット（３５）を加算する。第２積和回路１１ａは、その演算結果（２ｋビット；３７）の上位ｋビット（３８）を加算回路１７ａへ出力し、その下位ｋビット（３９）をＹレジスタ１５へ出力する。Ｙレジスタ１５は、そのｋビットのデータを値ｙi-1 として格納する。【００４７】
加算回路１７ａは、第１積和回路１０ａからの出力（ｋビット；３４）と第２積和回路１１ａからの出力（ｋビット；３８）とｃ2レジスタ１８ｂからの出力（１ビット；３２ｂ）とを加算する。そして、次回の演算用として、その加算結果（ｋ＋１ビット）の上位１ビットをｃ2レジスタ１８ｂへ、その下位ｋビットをｃ1レジスタ１８ａへ夫々出力する。各ｃ1レジスタ１８ａ，ｃ2レジスタ１８ｂは、これを格納する。【００４８】
アルゴリズム５を更に変形したアルゴリズムをアルゴリズム６として説明する。
（アルゴリズム６）
乗算する２数Ａ，Ｂ，パラメータＮ，モンゴメリ乗算のパラメータｎ’0，出力用変数Ｙが何れもｒ進数で、
Ａ＝（ａg-1 ，ａg-2，…，ａ0 ）r ，
Ｂ＝（ｂg-1 ，ｂg-2，…，ｂ0 ）r ，
Ｎ＝（ｎg-1 ，ｎg-2，…，ｎ0 ）r ，
Ｙ＝（ｙg ，ｙg-1，…，ｙ0 ）r ，
ｎ’0，
ｒ＝２k，
Ｒ＝ｒg 
とあらわされ、ｒ進１桁の一時変数をtmp1，キャリー変数をｃ3，ｃ4 とする場合、次に示すｉ，ｊの繰り返し処理によりＡＢＲ-1mod Ｎを単精度×単精度の計算として求めることができる。【００４９】
Ｙ＝０
for   ｊ＝０  to  ｇ−１                  ……………………………
（ｃ3 ，tmp1）r＝ｙ0 ＋ａ0 ・ｂj 
ｍ＝tmp1・ｎ’0  mod ｒ                      コア前処理
（ｃ4 ，tmp1）r＝tmp1＋ｍ・ｎ0 
for   ｉ＝１  to  ｇ−１                  ……………………………
（ｃ3 ，tmp1）r＝ｙi ＋ｃ3 ＋ａi ・ｂj 
（ｃ4 ，ｙi-1）r ＝tmp1＋ｍ・ｎi +ｃ4          コア処理
next  ｉ                                  ……………………………
（ｃ4 ，ｃ3）r ＝ｃ3 ＋ｃ4 ＋ｙg 
ｙg-1 ＝ｃ3                                 コア後処理
ｙg ＝ｃ4
next  ｊ                                  ……………………………
if  Ｙ≧Ｎ  then  Ｙ＝Ｙ−Ｎ                  補正処理
if  Ｙ＜Ｎ  then  return  Ｙ
図７は、上述したアルゴリズム６のコア処理を実行する乗算剰余計算装置の構成図である。【００５０】
図７に示す乗算剰余計算装置は、内部で乗算及び加算を行う第３積和回路１０ｂ及び第４積和回路１１ｂと、図４に示すものと同様の第１レジスタとしてのＡレジスタ１２，第２レジスタとしてのＢレジスタ１３，第３レジスタとしてのＹレジスタ１５，第５レジスタとしてのＮレジスタ１４，第６レジスタとしてのｍレジスタ１６及び選択回路１９と、キャリー変数ｃ3を保持する第４レジスタとしてのｃ3レジスタ１８ｃと、キャリー変数ｃ4を保持する第７レジスタとしてのｃ4 レジスタ１８ｄとを有する。【００５１】
なお、第３積和回路１０ｂ及び第４積和回路１１ｂの内部構成は、図５Ａに示す第１積和回路１０ａの内部構成と同じであり、各積和回路１０ｂ及び１１ｂは、ｋビット乗算器２０と2kビット加算器２１と2kビット加算器２２ａとから構成されている。【００５２】
第３積和回路１０ｂのｋビット乗算器２０は、Ａレジスタ１２及びＢレジスタ１３からの出力を乗算し、2kビット加算器２１は、ｋビット乗算器２０の出力と選択回路１９（Ｙレジスタ１５）の出力とを加算し、2kビット加算器２２ａは、2kビット加算器２１の出力とｃ3 レジスタ１８ｃの出力とを加算する。【００５３】
なお、図５Ａに示す構成例では、乗算結果に選択回路１９（Ｙレジスタ１５）の出力を先に加算し、その後にｃ3レジスタ１８ｃの出力を加算するようになっているが、これとは逆に、先にｃ3レジスタ１８ｃの出力、その後に選択回路１９（Ｙレジスタ１５）の出力を加算するように構成しても良い。【００５４】
一方、第４積和回路１１ｂのｋビット乗算器２０は、Ｎレジスタ１４及びｍレジスタ１６からの出力を乗算し、2kビット加算器２１は、ｋビット乗算器２０の出力と第３積和回路１０ｂからの下位ｋビットの出力とを加算し、2kビット加算器２２ａは、2kビット加算器２１の出力とｃ4レジスタ１８ｄの出力とを加算する。【００５５】
なお、図５Ａに示す構成例では、乗算結果に第３積和回路１０ｂからの下位ｋビットの出力を先に加算し、その後にｃ4レジスタ１８ｄの出力を加算するようになっているが、これとは逆に、先にｃ4 レジスタ１８ｄの出力、その後に第３積和回路１０ｂからの下位ｋビットの出力を加算するように構成しても良い。【００５６】
図８は、アルゴリズム６のコア処理の内容を示す説明図である。
第３積和回路１０ｂ内にて、Ａレジスタ１２の出力ａi （ｋビット）とＢレジスタ１３の出力ｂj（ｋビット）とを乗算し、その乗算結果（２ｋビット；３０）に、選択回路１９（Ｙレジスタ１５）の出力（ｋビット；３１）とｃ3レジスタ１８ｃの出力（ｋビット；３２ｃ）とを加算する。【００５７】
なお、選択回路１９は、ｊの値と０とを比較し、ｊの値が０である場合には第３積和回路１０ｂへ０を出力し、ｊの値が０でない場合にはＹレジスタ１５の格納値ｙiを第３積和回路１０ｂへ出力する。【００５８】
第３積和回路１０ｂは、その演算結果（２ｋビット）の上位ｋビット（３４）をｃ3レジスタ１８ｃへ出力し、その下位ｋビット（３５）を第４積和回路１１ｂへ出力する。ｃ3レジスタ１８ｃは、このｋビットを次回の演算用のキャリー変数として格納する。【００５９】
第４積和回路１１ｂ内にて、Ｎレジスタ１４の出力ｎi（ｋビット）とｍレジスタ１６の出力ｍ（ｋビット）とを乗算し、その乗算結果（２ｋビット；３６）に、第３積和回路１０ｂからの下位ｋビット出力（３５）と、ｃ４レジスタ１８ｄのｋビット出力（３２ｄ）を加算する。【００６０】
第４積和回路１１ｂは、その演算結果（２ｋビット；３７）の上位ｋビット（３８）をｃ4レジスタ１８ｄへ出力し、その下位ｋビット（３９）をＹレジスタ１５へ出力する。ｃ4レジスタ１８ｄは、このｋビットを次回の演算用のキャリー変数として格納する。また、Ｙレジスタ１５は、そのｋビットのデータを値ｙi-1 として格納する。【００６１】
図９は、モンゴメリ法による乗算剰余処理の一例を示すフローチャートの概観図である。
このフローチャートにおいて、ｊループが（アルゴリズム３）のループ処理に当たる。ｊループの内側では、Ａ×ｂj 及びｍ×Ｎの多重精度×単精度の部分乗算を行っている。ｉループは、Ａ×ｂj 及びｍ×Ｎの多重精度×単精度の計算を単精度×単精度の部分乗算で行っている部分である。ｉループの内部ではａi ×ｂjとｍ×ｎi との部分乗算を行っている。【００６２】
以下に、アルゴリズム６における、コア処理以外の処理も含めた全体の処理の流れの具体例について説明する。
以下の例では、Ｎ，Ａ，Ｂのビット長を1024ビット、ｇ＝32、処理単位ｋ＝32、Ｒ＝２1024、ｒ＝２32とする。
（コア前処理）
図１０は、コア前処理を行う構成の一例を示す図である。【００６３】
レジスタ４１はモンゴメリ計算用のパラメータｎ’0 を保持する。乗算回路４０は第３積和回路１０ｂの出力とレジスタ４１の出力とを乗算する。このコア前処理では、コア処理で使用するｃ3レジスタ１８ｃ，ｃ4レジスタ１８ｄ及びｍレジスタ１６ａの初期化を行っている。第３積和回路１０ｂは、まず、Ａレジスタ１２，Ｂレジスタ１３からの入力ａ0，ｂj を乗算し、その乗算結果とＹレジスタ１５からの入力ｙ0 とを加算する。【００６４】
なお、コア処理と同じ積和回路を使用する場合は、更にその結果と０とを加算する。
そして、結果の上位32ビットをｃ3レジスタ１８ｃに格納し、下位32ビットを第４積和回路１１ｂとパラメータｍを計算するための乗算回路４０とへ出力する。【００６５】
乗算回路４０は、第３積和回路１０ｂの出力とレジスタ４１の出力ｎ’0 とを乗算し、その乗算結果の下位32ビットをｍレジスタ１６ａに出力する。第４積和回路１１ｂは、Ｎレジスタ１４からの入力ｎ0とｍレジスタ１６ａの値とを乗算し、その乗算結果と第３積和回路１０ｂからの出力とを加算する。【００６６】
なお、コア処理と同じ積和回路を使用する場合は、更にその結果と０とを加算する。
そして、結果の上位32ビットをｃ4レジスタ29に格納する。下位32ビットは使用しない。
（コア処理）
図１１は、ｉループ内部処理であるコア処理を行う構成の一例を示す図である。【００６７】
Ｙレジスタ１５は前回の処理結果の保持及び今回の処理結果の出力用レジスタである。選択回路１９は、アルゴリズム３におけるＹ＝０の処理に相当するものである。第３積和回路１０ｂは、まず、Ａレジスタ１２，Ｂレジスタ１３からの入力ａi ，ｂjを乗算し、その乗算結果とＹレジスタ１５からの入力ｙiとを加算し、更にその加算結果とｃ3レジスタ１８ｃの値とを加算する。そして、結果の上位32ビットをｃ3レジスタ１８ｃに格納し、下位32ビットを第４積和回路１１ｂへ出力する。【００６８】
第４積和回路１１ｂは、まず、Ｎレジスタ１４からの入力ｎi とｍレジスタ１６ａの値とを乗算し、その乗算結果と第３積和回路１０ｂからの出力とを加算し、更にその加算結果とｃ4レジスタ１８ｄの値とを加算する。そして、結果の上位32ビットをｃ4レジスタ１８ｄに格納し、下位32ビットをＹレジスタ１５のｙi-1に格納する。【００６９】
アルゴリズム３のＹ＝Ｙ／ｒの処理は、ｉ回目の計算結果をｙi-1 に格納することで実現している。
（コア後処理）
図１２は、コア後処理を行う構成の一例を示す図である。【００７０】
加算回路４５は、ｃ3レジスタ１８ｃの出力と、ｃ4レジスタ１８ｄの出力と、選択回路１９の出力とを加算する。選択回路４６は、加算回路４５からのキャリー出力を０，１と比較し、０であれば０を、１であれば１を、Ｙレジスタ１５へ出力する。このコア後処理では、コア処理終了後のキャリー変数ｃ3 ，ｃ4 の値の処理を行っている。【００７１】
ｃ3レジスタ１８ｃ，ｃ4レジスタ１８ｄの値、及び、Ｙレジスタ１５からの入力ｙ32を加算回路４５に入力し、その加算結果をＹレジスタ１５のｙ31に出力し、キャリーを処理単位である32ビットの値に変換してＹレジスタ１５のｙ32に出力する。ここで、出力からもわかるように、ｙ32の値はＹレジスタ１５では32ビットとして扱われているが、実際は１ビットの値であるので、加算結果は32ビット＋キャリーの範囲で収まる。
（積和回路の構成）
図１３は、上述の構成例で用いた積和回路の構成の一例を示す図である。【００７２】
ここでは、全ての処理単位を32ビットになるように構成している。
積和回路は、１個の32ビット乗算器５１と、４個の32ビット加算器５２，５３，５４，５５とを有する。【００７３】
Ａ，Ｂの入力値は32ビット乗算器５１で乗算され、上位32ビットと下位32ビットとの２つで出力される。32ビット加算器５３は、32ビット乗算器５１の出力の下位32ビットと入力Ｒの値とを加算し、その加算結果の出力32ビットを32ビット加算器５５へ、キャリーを32ビット加算器５２へそれぞれ出力する。32ビット加算器５２は、32ビット乗算器５１の出力上位32ビットと32ビット加算器５３のキャリー出力とを加算し、その加算結果の出力32ビットを32ビット加算器５４へ出力する。この加算ではキャリーが発生しないことが理論的に証明されている。32ビット加算器５５は、32ビット加算器５３の出力と入力Ｃの値とを加算し、その加算結果の出力32ビットを積和回路のＬ出力（下位32ビット）として出力し、キャリーは32ビット加算器５４へ出力される。32ビット加算器５４は、32ビット加算器５２の出力と32ビット加算器５５のキャリー出力とを加算し、その加算結果の出力32ビットを積和回路のＨ出力（上位32ビット）として出力する。この加算ではキャリーが発生しないことが理論的に証明されている。【００７４】
上記したすべてのアルゴリズム及び回路は特許文献１に記載されている。
上述した従来の乗算剰余装置に使用した積和回路は、図１３に示されるように、４入力２出力の積和回路であった。この積和回路は、２入力の乗算及びその結果と残る２入力との加算を行う。一般的なプロセッサには４入力２出力積和回路が搭載されておらず、図１２の２つの積和回路を単純化できないという問題がある。また、通常、Ｐｅｎｔｉｕｍ（登録商標）プロセッサにおいては、２入力２出力の乗算器しか搭載されていない。それでも、２入力２出力の乗算器と加算器を使って、上記４入力２出力の積和回路と同等の機能を実現する場合には、あまり性能劣化は問題にはならなかった。ところが、最近のＩｔａｎｉｕｍ２プロセッサに代表されるプロセッサには、３入力２出力の積和回路が搭載されている。特に、Ｉｔａｎｉｕｍ２プロセッサには、３入力２出力の積和回路が２台搭載されている。しかし、上記従来の４入力２出力の積和演算を使用するアルゴリズムでは、このような３入力２出力の積和回路を搭載したプロセッサの能力を最大限生かすことはできない。
【特許文献１】特開平１１−２１２４５６号公報
【発明の開示】
【００７５】
本発明の課題は、モンゴメリ法に適した、３入力２出力の積和演算を用いた、効率の良い乗算剰余計算装置、及び、その方法を提供することである。
本発明のモンゴメリ法用乗算剰余計算装置は、ある値ＡとＢの乗算をし、法Ｎによる剰余算を行って、結果Ｙを計算するモンゴメリ法用乗算剰余計算装置において、Ａのある１桁の値と、Ｂのある１桁の値と、キャリー値との３値を入力とし、Ａのある１桁の値とＢのある１桁の値の乗算を行い、これにキャリー値を加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力する第１の積和計算手段と、Ｎのある１桁の値と、ある１桁の値ｍと、キャリー値との３値を入力とし、Ｎのある１桁の値とある値ｍとの乗算を行い、これにキャリー値を加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力する第２の積和計算手段と、第１の積和計算手段の出力の下位桁と、第２の積和計算手段の出力の下位桁と、変数Ｙのある１桁と、キャリー値とを加算した結果を、自身の新たなキャリー値としての上位桁と、下位桁の２値に分けて出力し、該下位桁を変数Ｙのある１桁に格納する加算手段とを備えることを特徴とする。
【図面の簡単な説明】
【００７６】
【図１】従来のアルゴリズム４のコア処理を実行する乗算剰余計算装置の構成図である
【図２Ａ】図１の場合の従来の積和回路の構成図（その１）である。
【図２Ｂ】図１の場合の従来の積和回路の構成図（その２）である。
【図３】従来のアルゴリズム４のコア処理の内容を示す説明図である。
【図４】従来のアルゴリズム５のコア処理を実行する乗算剰余計算装置の構成図である。
【図５Ａ】図４の場合の従来の積和回路の構成図（その１）である。
【図５Ｂ】図４の場合の従来の積和回路の構成図（その２）である。
【図６】従来のアルゴリズム５のコア処理の内容を示す説明図である。
【図７】従来のアルゴリズム６のコア処理を実行する乗算剰余計算装置の構成図である。
【図８】従来のアルゴリズム６のコア処理の内容を示す説明図である。
【図９】モンゴメリ法による乗算剰余処理の一例を示すフローチャートの概観図である。
【図１０】コア前処理を行う構成の一例を示す図である。
【図１１】ｉループ内部処理であるコア処理を行う構成の一例を示す図である。
【図１２】コア後処理を行う構成の一例を示す図である。
【図１３】従来の積和回路の構成の一例を示す図である。
【図１４】本発明の実施形態のアルゴリズムのコア処理を実行する乗算剰余計算装置の構成図である。
【図１５】本発明の実施形態のアルゴリズムにおけるコア前処理を行うための装置構成を示す図である。
【図１６】本発明の実施形態のアルゴリズムにおけるコア後処理を行うための装置構成を示す図である。
【発明を実施するための最良の形態】
【００７７】
本発明の実施形態においては、３入力２出力の積和回路を有効に使用した、モンゴメリ法の使用のための演算回路を提供する。
以下に、３入力２出力の積和回路に適した本発明の実施形態について説明する。【００７８】
本発明の実施形態では、上記アルゴリズム６のコア処理部において、２つの３入力２出力積和回路を用いてアルゴリズムを実行する。本発明の実施形態のアルゴリズムを実行する演算回路においては、第1積和回路が出力する上位ｋビットはキャリー変数ｃ１として第１積和回路に戻し、第2積和回路が出力する上位ｋビットはキャリー変数ｃ２として第2積和回路に戻し、加算回路の出力結果である（ｋ＋２）ビットを上位2ビットと下位ｋビットとに分離し、上位２ビットをキャリー変数ｃ３として加算回路に戻す。
この場合のアルゴリズムを以下に示す。
（アルゴリズム）
乗算する２数Ａ，Ｂ，剰余の法Ｎ，モンゴメリ乗算のパラメータｎ’0，出力用変数Ｙが何れもｒ進数で、
Ａ＝（ａg-1 ，ａg-2，…，ａ0 ）r ，
Ｂ＝（ｂg-1 ，ｂg-2，…，ｂ0 ）r ，
Ｎ＝（ｎg-1 ，ｎg-2，…，ｎ0 ）r ，
Ｙ＝（ｙg ，ｙg-1，…，ｙ0 ）r ，
ｎ’0，
ｒ＝２k，
Ｒ＝ｒg 
とあらわされ、ｒ進１桁の一時変数をtmp1，tmp2，キャリー変数をｃ1 ，ｃ２，ｃ３とする場合、次に示すｉ，ｊの繰り返し処理によりＡＢＲ-1mod Ｎを単精度×単精度の計算として求めることができる。【００７９】
Ｙ＝０
for   ｊ＝０  to  ｇ−１                  ……………………………
（ｃ１，tmp1）r ＝ａ0・ｂj ＋ｙ0 
ｍ＝tmp1・ｎ’0 mod ｒ
（ｃ２，tmp1）r ＝tmp1＋ｍ・ｎ0            コア前処理
ｃ３＝0
for   ｉ＝１  to  ｇ−１                  ……………………………
（ｃ１，tmp1）r ＝ ａi ・ｂj＋ｃ１
（ｃ２，tmp2 ）r ＝ ｍ・ｎi＋ｃ２            コア処理
（ｃ３，ｙi-1 ）r ＝ tmp1＋tmp2＋ｃ3＋ｙi 
next  ｉ                                 ……………………………
（ｃ2 ，ｃ1 ）r ＝ｃ1 ＋ｃ2 ＋ｃ３＋ｙg 
ｙg-1 ＝ｃ1                                   コア後処理
ｙg ＝ｃ2
next  ｊ                                 ……………………………
if  Ｙ≧Ｎ  then  Ｙ＝Ｙ−Ｎ                     補正処理
if  Ｙ＜Ｎ  then  return  Ｙ
ここで、（  ）r は、括弧内のｒ進数１桁の変数を多重精度として扱うことを示している。またキャリー変数ｃ2 はｒ進数１桁で表現しているが、内容は１ビットの値である。【００８０】
図１４は、本発明の実施形態のアルゴリズムのコア処理を実行する乗算剰余計算装置の構成図である。
図１４に示す乗算剰余計算装置は、内部で乗算及び加算を行う積和回路６０及び積和回路６１と、加算回路６２と、乗算する一方の数Ａ：（ａg-1 ，ａg-2 ，…，ａ0 ）を保持する第１レジスタとしてのＡレジスタ６３と、乗算する一方の数Ｂ：（ｂg-1，ｂg-2 ，…，ｂ0 ）を保持する第２レジスタとしてのＢレジスタ６４と、加算回路６２の前回の演算結果の下位ｋビット出力を保持し、次回の演算の下位ｋビット出力を格納する第３レジスタとしてのＹレジスタ６５と、モンゴメリアルゴリズムにおけるパラータｍを保持する第４レジスタとしてのｍレジスタ６６と、剰余の法Ｎ：（ｎg-1，ｎg-2 ，…，ｎ0 ）を保持する第５レジスタとしてのＮレジスタ６７と、キャリー変数ｃ1を保持する第６レジスタとしてのｃ1レジスタ６８と、キャリー変数ｃ2を保持する第７レジスタとしてのｃ2レジスタ６９と、キャリー変数ｃ３を保持する第８レジスタとしてのｃ３レジスタ７０と、ｊの値と０とを比較してその出力を選択する選択回路７１とを有する。【００８１】
なお、図１４中、積和回路６０、積和回路６１のA,B,C,H,Lは全てｋビットである。ｋビットのｋとは、演算に使用するプロセッサが単精度の数を表現する場合に用いるビット数であり、３２ビットプロセッサの場合には、ｋは３２である。A×B+Cの積和結果２ｋビットを（H,L）と表現し、Hが上位ｋビット、Lが下位ｋビットとなる。図１４中、加算回路６２は、A,B,C,D,Lは全てｋビット、Hのみ２ビット（ソフトウェアの場合にはHもkビット）。A+B+C+Dの加算結果（k+2）ビットを（H,L）と表現し、Hが上位２ビット（ソフトウェアの場合にはｋビット）、Lが下位ｋビットとなる。なお、加算回路６２は、４入力２出力の加算回路を用いなくても良い。すなわち、加算演算は、乗算演算に比べ、計算量が少ないので、モンゴメリ法による演算に要する時間や負荷に与える影響は少ない。したがって、たとえば、２入力２出力の加算回路を組み合わせて加算回路６２としても、本発明のアルゴリズムの性能には大きな影響は与えない。よって、図１４では、加算回路は４入力２出力加算回路を使っているが、その構成法はここでは規定しない。２入力２出力加算を３個使用すれば、加算回路６２と同様の回路は実現可能であるし、キャリー付加算命令を使用する方法もあり、この加算は多種の構成法がある。【００８２】
図１４において、積和回路６０は、Ａの１桁とＢの１桁と、キャリー１桁とを入力し、積和計算をし、答えを（Ｈ、Ｌ）として出力している。すなわち、積和回路６０では、前述の本発明の実施形態のアルゴリズムのコア処理の内、（ｃ１，tmp1）r ＝ ａi ・ｂj＋ｃ１を計算している。積和回路６１は、１桁のｍと、Ｎの１桁と、キャリー１桁を入力し、積和計算を行い、答えを（Ｈ、Ｌ）として出力している。すなわち、積和回路６１では、前述の本発明の実施形態のアルゴリズムのコア処理の内、（ｃ２，tmp2 ）r ＝ ｍ・ｎi＋ｃ２を行っている。【００８３】
加算回路６２では、積和回路６０の演算結果の下位ｋビットと積和回路６１の演算結果の下位ｋビットと、Ｙの１桁と、キャリー１桁を入力し、演算結果の下位ｋビットをＹに格納している。すなわち、加算回路６２では、（ｃ３，ｙi-1 ）r ＝ tmp1＋tmp2＋ｃ3＋ｙiを行っている。【００８４】
なお、積和回路６０と６１は、２つの３入力２出力の積和回路を用いて並列に行うのが好ましく、また、加算回路６２の演算が行われている間に、積和回路６０と６１は、次回の演算を行っていることが好ましい。【００８５】
更に、以下に、コア前処理とコア後処理を行う乗算剰余計算装置の構成を示すが、本発明の実施形態のアルゴリズムが、従来技術のアルゴリズム６の変形構成であるため、アルゴリズム６の場合とほぼ同じである。【００８６】
図１５は、本発明の実施形態のアルゴリズムにおけるコア前処理を行うための装置構成を示す図である。
レジスタ４１はモンゴメリ計算用のパラメータｎ’0 を保持する。乗算回路４０は積和回路６０の出力とレジスタ４１の出力とを乗算する。このコア前処理では、コア処理で使用するｃ１レジスタ６８，ｃ２レジスタ６９、ｃ３レジスタ７０及びｍレジスタ６６の初期化を行っている。積和回路６０は、まず、Ａレジスタ６３，Ｂレジスタ６４からの入力ａ0，ｂj を乗算し、その乗算結果とＹレジスタ６５からの入力ｙi とを加算する。【００８７】
そして、結果の上位ｋビットをｃ１レジスタ６８に格納し、下位ｋビットを積和回路６１とパラメータｍを計算するための乗算回路４０とへ出力する。
乗算回路４０は、積和回路６０の出力とレジスタ４１の出力ｎ’0 とを乗算し、その乗算結果の下位ｋビットをｍレジスタ６６に出力する。積和回路６１は、Ｎレジスタ６７からの入力ｎ0とｍレジスタ６６の値とを乗算し、その乗算結果と積和回路６０からの出力とを加算する。そして、結果の上位ｋビットをｃ２レジスタ６９に格納する。下位ｋビットは使用しない。【００８８】
以上のコア前処理の演算装置においても、３入力２出力の積和回路を使っている。従来のアルゴリズム６の場合には、コア前処理で、コア処理のときに使用する積和回路と同じ積和回路を使用する場合には、４入力の内、１つを０としたが、本発明の実施形態においては、使用する積和回路が３入力２出力であるので、このような設定は不要である。【００８９】
また、コア前処理においては、積和回路６０の処理の後に、積和回路６１の処理を行う必要があるため、コア処理のように、積和回路６０と６１を並列に実行することができない。したがって、３入力２出力の積和回路を２つ持っていても、コア前処理では、コア処理ほど効果は出ないが、それでも、３入力２出力の積和回路を有効に使うことはできる。【００９０】
図１６は、本発明の実施形態のアルゴリズムにおけるコア後処理を行うための装置構成を示す図である。
加算回路４５は、ｃ１レジスタ６８の出力と、ｃ２レジスタ６９の出力と、ｃ３レジスタ７０の出力と、選択回路１９の出力とを加算する。選択回路４６は、加算回路４５からのキャリー出力を０，１と比較し、０であれば０を、１であれば１を、Ｙレジスタ６５へ出力する。このコア後処理では、コア処理終了後のキャリー変数ｃ１，ｃ２ ，ｃ３の値の処理を行っている。【００９１】
ｃ１レジスタ６８，ｃ２レジスタ６９，ｃ３レジスタ７０の値、及び、Ｙレジスタ６５からの入力ｙｇを加算回路４５に入力し、その加算結果をＹレジスタ１５のｙｇ−１に出力し、キャリーを処理単位であるｋビットの値に変換してＹレジスタ６５のｙｇに出力する。ここで、出力からもわかるように、ｙｇの値はＹレジスタ６５ではｋビットとして扱われているが、実際は１ビットの値であるので、加算結果はｋビット＋キャリーの範囲で収まる。【００９２】
以上の、本発明の実施形態によれば、３つの変数を入力とし、２つの出力で演算結果を返すような積和命令を持ち、同時に積和命令を２つ処理することの出来るItanium2プロセッサに代表されるプロセッサにおいて、従来法で構成したものに比べ、４倍の高速化を実現した。これは、積和回路６１、６２を並列化したこと、更に、この並列化により伝播遅延時間が短縮されたことによる。本発明の３入力２出力の積和演算回路は積和回路６１、６２を従来どおりに直列に接続したものにも適用できる。【００９３】
以上、本発明によれば、３入力２出力の積和演算回路を有する演算装置に適したモンゴメリ法用乗算剰余計算装置を実現できる。同様に、同じような積和回路を持つDSPに実装する場合に高速化が可能であると期待できる。
【図１】
0004783382.tif 000002
【図２Ａ】
0004783382.tif 000003
【図２Ｂ】
0004783382.tif 000004
【図３】
0004783382.tif 000005
【図４】
0004783382.tif 000006
【図５Ａ】
0004783382.tif 000007
【図５Ｂ】
0004783382.tif 000008
【図６】
0004783382.tif 000009
【図７】
0004783382.tif 000010
【図８】
0004783382.tif 000011
【図９】
0004783382.tif 000012
【図１０】
0004783382.tif 000013
【図１１】
0004783382.tif 000014
【図１２】
0004783382.tif 000015
【図１３】
0004783382.tif 000016
【図１４】
0004783382.tif 000017
【図１５】
0004783382.tif 000018
【図１６】
0004783382.tif 000019