(57)【特許請求の範囲】
【請求項１】
正の整数Ｎと、Ｎ未満の正の整数ｘ，ｙとを入力とし、剰余演算系の基底を｛ａ１，ａ２，…，ａｉ，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｉ，…，ｂｎ｝（１≦ｉ≦ｎ、ｎは正の整数）としたとき、前記基底の要素の乗積として定義された整数Ｂ（＝ｂ１ｂ２…ｂｎ）を用いて、出力ｗ＝ｘｙＢ−１ｍｏｄ  Ｎを算出するためのモンゴメリ乗算装置であって、
前記各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝と前記出力ｗの算出用の事前計算結果とが記憶される第１記憶手段と、
前記基底の拡張用の入力ξｉを受けたとき、前記入力ξｉの上位ｑビットを抽出すると共に、この今回の抽出値と前回の最上位ビットを除く加算結果とを加算し、得られた加算結果のうち、最上位ビットの値ｋｉを出力する近似演算手段と、
前記第１記憶手段の内容および前記近似演算手段の出力ｋｉに基づいて、前記各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝を法ｍとする剰余算（但し、法ｍ＝２ｒ−μは基底の一要素、ｒはｍ≦２ｒを満たす整数、μは２ｒ未満の非負整数）を実行する剰余演算手段と、
前記剰余演算手段による剰余算の結果が記憶される第２記憶手段とを備え、
前記剰余演算手段は、
前記第１記憶手段又は前記第２記憶手段からの入力ｘ，ｙの積ｘｙと前回の剰余算の結果ｄと前記近似演算手段の出力ｋｉに基づき入力される前記事前計算結果ｃとの和（ｘｙ＋ｄ＋ｃ）からなる入力ｚ（但し、ｚは正の整数）を受けると共に、前記入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行する剰余算部と、
前記剰余算部による実行結果ｈ’と前記法ｍの上限値２ｒとを比較し、前記実行結果ｈ’が２ｒ以上のときには当該実行結果ｈ’を前記入力ｚとして前記剰余算部に戻し、前記実行結果ｈ’が２ｒ未満のときには当該実行結果ｈ’を前記剰余算の結果ｈとして前記第２記憶手段に出力するループ制御部と、
を備えたことを特徴とするモンゴメリ乗算装置。
【請求項２】
請求項１に記載のモンゴメリ乗算装置において、
前記剰余算部は、
前記入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行するとき、前記入力ｚの下位ｒビットの値ｚ０と、前記入力ｚから前記下位の値ｚ０を除いた上位ビットの値ｚ１とを夫々抽出するビット選択部と、
前記ビット選択部により抽出された上位ビットの値ｚ１と前記法ｍに関する入力μとを受けたとき、両者の積ｚ１μを算出する乗算部と、
前記乗算部により得られた積ｚ１μと前記ビット選択部により抽出された下位ｒビットの値ｚ０との和（ｚ１μ＋ｚ０）を算出する加算部とを備え、
前記剰余算部による実行結果ｈ’は、前記加算部により得られた和（ｚ１μ＋ｚ０）であることを特徴とするモンゴメリ乗算装置。
【請求項３】
正の整数Ｎと、Ｎ未満の正の整数ｘ，ｙとを入力とし、剰余演算系の基底を｛ａ１，ａ２，…，ａｉ，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｉ，…，ｂｎ｝（１≦ｉ≦ｎ、ｎは正の整数）としたとき、前記基底の要素の乗積として定義された整数Ｂ（＝ｂ１ｂ２…ｂｎ）を用いて、出力ｗ＝ｘｙＢ−１ｍｏｄ  Ｎを算出するためのモンゴメリ乗算方法であって、
前記各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝と前記出力ｗの算出用の事前計算結果とが記憶される第１記憶工程と、
前記基底の拡張用の入力ξｉを受けたとき、前記入力ξｉの上位ｑビットを抽出すると共に、この今回の抽出値と前回の最上位ビットを除く加算結果とを加算し、得られた加算結果のうち、最上位ビットの値ｋｉを出力する近似演算工程と、
前記第１記憶工程の記憶内容および前記近似演算工程の出力ｋｉに基づいて、前記各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝を法ｍとする剰余算（但し、法ｍ＝２ｒ−μは基底の一要素、ｒはｍ≦２ｒを満たす整数、μは２ｒ未満の非負整数）を実行する剰余演算工程と、
前記剰余演算工程による剰余算の結果が記憶される第２記憶工程とを含んでおり、
前記剰余演算工程は、
前記第１記憶工程の記憶内容又は前記第２記憶工程の記憶内容からの入力ｘ，ｙの積ｘｙと前回の剰余算の結果ｄと前記近似演算工程の出力ｋｉに基づき入力される前記事前計算結果ｃとの和（ｘｙ＋ｄ＋ｃ）からなる入力ｚ（但し、ｚは正の整数）を受けると共に、前記入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行する剰余算工程と、
前記剰余算工程による実行結果ｈ’と前記法ｍの上限値２ｒとを比較し、前記実行結果ｈ’が２ｒ以上のときには当該実行結果ｈ’を前記入力ｚとして前記剰余算工程に戻し、前記実行結果ｈ’が２ｒ未満のときには当該実行結果ｈ’を前記剰余算の結果ｈとして前記第２記憶工程に出力するループ制御工程と、
を含んでいることを特徴とするモンゴメリ乗算方法。
【請求項４】
請求項３に記載のモンゴメリ乗算方法において、
前記剰余算工程は、
前記入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行するとき、前記入力ｚの下位ｒビットの値ｚ０と、前記入力ｚから前記下位の値ｚ０を除いた上位ビットの値ｚ１とを夫々抽出するビット選択工程と、
前記ビット選択工程により抽出された上位ビットの値ｚ１と前記法ｍに関する入力μとを受けたとき、両者の積ｚ１μを算出する乗算工程と、
前記乗算工程により得られた積ｚ１μと前記ビット選択工程により抽出された下位ｒビットの値ｚ０との和（ｚ１μ＋ｚ０）を算出する加算工程とを含んでおり、
前記剰余算工程による実行結果ｈ’は、前記加算工程により得られた和（ｚ１μ＋ｚ０）であることを特徴とするモンゴメリ乗算方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、剰余演算系におけるモンゴメリ乗算アルゴリズムを用いるモンゴメリ乗算装置及び方法に係り、特に、剰余算のループ制御の高速化により、全体の処理速度を向上し得るモンゴメリ乗算装置及び方法に関する。
【０００２】
【従来の技術】
近年、公開鍵暗号の重要性が増すにつれ、公開鍵暗号における大きな整数の剰余乗算に関し、その高速化を図る旨の要望が高まっている。例えば現在、事実上の標準（デファクトスタンダード）であるＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）方式では、１，０２４ビットの整数による剰余演算を高速に行なう必要がある。
【０００３】
係る剰余演算の高速化の一方法として、剰余演算系（Ｒｅｓｉｄｕｅ  Ｎｕｍｂｅｒ  Ｓｙｓｔｅｍ、以後ＲＮＳという）が知られている。このＲＮＳは、互いに素な比較的小さな整数の組｛ａ１，ａ２，…，ａｎ｝を用意し、演算対象の大きな整数をこれらの整数で割った余りの組で表現する方式である。
【０００４】
以後、これら割る数の組｛ａ１，ａ２，…，ａｎ｝をＲＮＳの基底と呼び、基底を構成する要素の個数ｎを基底のサイズと呼ぶ。また基底の集合をａ＝｛ａ１，ａ２，…，ａｎ｝で表す。
【０００５】
例えば、整数ｘと基底｛ａ１，ａ２，…，ａｎ｝が与えられたとき、ｘを基底ａｉ（ｉ＝１，２，…，ｎ）で割った余りｘｉの組（ｘ１，ｘ２，…，ｘｎ）がｘのＲＮＳ表現である。ここで、ｘｉ＝ｘ  ｍｏｄ  ａｉである。
【０００６】
このとき、ｘは、基底の全要素の積Ａ＝ａ１ａ２…ａｎを法として一意的に表現できる。すなわち、ｘがＡ未満の正整数であれば、ｘとそのＲＮＳ表現（ｘ１，ｘ２，…，ｘｎ）は一対一に対応する。
【０００７】
ＲＮＳ表現の数値同士の剰余乗算方法は、ポッシュら（Ｐｏｓｃｈ  ｅｔ  ａｌ）による提案（Ｋ．  Ｃ．  Ｐｏｓｃｈ，  Ｒ．  Ｐｏｓｃｈ，  “Ｍｏｄｕｌｏ  Ｒｅｄｕｃｔｉｏｎ  ｉｎ  Ｒｅｓｉｄｕｅ  Ｎｕｍｂｅｒ  Ｓｙｓｔｅｍｓ”，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，Ｖｏｌ．６，Ｎｏ．５，Ｍａｙ  １９９５，ｐｐ．４４９−４５４  及び“ＲＮＳ−Ｍｏｄｕｌｏ  Ｒｅｄｕｃｔｉｏｎ  Ｕｐｏｎ  ａ  Ｒｅｓｔｒｉｃｔｅｄ  Ｂａｓｅ  Ｖａｌｕｅ  Ｓｅｔ  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｂｉｌｉｔｙ  ｔｏ  ＲＳＡ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，Ｃｏｍｐｕｔｅｒ  ＆  Ｓｅｃｕｒｉｔｙ，Ｖｏｌ．１７，ｐｐ．６３７−６５０，１９９８）並びに川村による提案（特願平１１−３１０６１９号）がある。
【０００８】
これらの剰余乗算方法は、ＲＮＳ表現での演算において不利な除算を避けるために、モンゴメリ（Ｍｏｎｔｇｏｍｅｒｙ）の提案による剰余乗算方法（以下、モンゴメリ乗算という。詳細は  Ｐ．  Ｌ．  Ｍｏｎｔｇｏｍｅｒｙ，“Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｗｉｔｈｏｕｔ  Ｔｒｉａｌ  Ｄｉｖｉｓｉｏｎ”，Ｍａｔｈｅｍａｔｉｃｓ  ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎ，Ｖｏｌ．４４，Ｎｏ．１７０，ｐｐ．５１９−５２１，Ａｐｒｉｌ，１９８５）を利用することと、あるＲＮＳ基底で表現された整数を、基底拡張を用いて別の基底で表現すること、などが特徴として挙げられる。
【０００９】
ここで、基底拡張は、例えば、整数ｘにおいて、基底ａ＝｛ａ１，ａ２，…，ａｎ｝での表現（ｘ  ｍｏｄ  ａ１，ｘ  ｍｏｄ  ａ２，…，ｘ  ｍｏｄ  ａｎ）から基底ａ∪｛ｂ１｝＝｛ａ１，ａ２，…，ａｎ，ｂ１｝での表現（ｘ  ｍｏｄ  ａ１，ｘ  ｍｏｄ  ａ２，…，ｘ  ｍｏｄ  ａｎ，ｘ  ｍｏｄ  ｂ１）を生成する操作である。
【００１０】
この例では、基底のサイズを１つ増やしたが、この操作を繰り返して基底のサイズをｎ’個（ｎ’は整数）増やし、その基底の下でのＲＮＳ表現を作り出すことも基底拡張と呼ぶ。
【００１１】
続いて、以上のような剰余乗算方法について具体的に説明する。
図４は川村により提案されたモンゴメリ乗算装置の構成を示す模式図である。このモンゴメリ乗算装置は、ＲＮＳ表現でのモンゴメリ乗算を実行するものであり、本発明者並びに川村らによりＣｏｘ−Ｒｏｗｅｒアーキテクチャと命名された構成を備えている。係るＣｏｘ−Ｒｏｗｅｒアーキテクチャでは、互いに並列接続されてそれぞれ剰余乗算を行なうｎ個のＲｏｗｅｒユニットに対し、補正項を計算する１個のＣｏｘユニットが接続されている。なお、ｎは基底のサイズである。
【００１２】
ここで、Ｃｏｘユニットは、基底拡張のためのものであり、ビット選択部１１及び加算器１２からなる。ビット選択部１１は、ＲｏｗｅｒユニットのＲＡＭ２１ｉから入力されたｒビットの整数ξｉの上位ｑビットを取り出して加算器１２に与える。
【００１３】
加算器１２は、そのｑビットの整数を前回の加算結果に加算し、得られた加算結果のｑ＋１ビット目（加算のキャリー１ビット）に位置する１ビットの数ｋｉを各Ｒｏｗｅｒユニットに出力する。ここでｒは基底ａの各要素ａ１〜ａｎのビット数であり、ｑはｒ未満の正整数である。
【００１４】
川村によれば、１，０２４ビットのべき乗剰余算のパラメータをｎ＝３３、ｒ＝３２、ｑ＝７と取れば良いことが分かる。従って、Ｃｏｘユニットの処理は、７ビット程度の加算で済むので、高速に実行可能である。
ｎ個のＲｏｗｅｒユニットは、ＲＮＳの基底を法とした剰余演算（ｆｇ＋ｃ＋ｈ）ｍｏｄ  ｍを計算可能なものであり、ＲＮＳ基底の下での剰余演算を行なう積和回路２０１〜２０ｎ、ＲＡＭ２１１〜２１ｎ及びＲＯＭ２２１〜２２ｎからなる。ここで、ｍはＲＮＳ基底のある一要素であり、ｆ，ｇ，ｃ，ｄ（前回のｈ）はｍ未満の整数である。
各積和回路２０ｉ（但し１≦ｉ≦ｎ）は、図５に示すように、（ｆｇ＋ｃ＋ｄ）ｍｏｄ  ｍを計算するユニットであり、乗算器２３、加算器２４、スイッチ２５、第１レジスタ２６、第２レジスタ２７、剰余演算器２８及び第３レジスタ２９を備えている。
乗算器２３は、入力ｆ，ｇの積ｆｇを算出して加算器２４に出力する。
加算器２４は、その出力ｆｇとスイッチ２５からの入力ｃ、及び第３レジスタ２９内の前回の剰余演算結果ｄを加算し、得られた結果（ｆｇ＋ｃ＋ｄ）を剰余演算器２８に出力する。なお、スイッチ２５は、Ｃｏｘユニットからの１ビットの入力ｋｉに基づいて、ＲＯＭ２２ｉから第１レジスタ２６に格納された入力ｃを加算器２４に入力又は遮断するものである。
【００１５】
剰余演算器２８は、ＲＯＭ２２ｉから第２レジスタ２７に格納された基底要素ａｉ又はｂｉとしての法ｍを用い、加算器の出力結果ｆｇ＋ｃ＋ｄを法ｍで割った剰余演算（ｆｇ＋ｃ＋ｄ）ｍｏｄ  ｍを実行する。
【００１６】
ここで、ポッシュ又は川村のモンゴメリ乗算アルゴリズムによれば、ＲＮＳの基底としてｍ＝２ｒ−μ（但し、μ≪２ｒ）の形式を適用可能なため、剰余演算器における剰余算ｚ  ｍｏｄ  ｍ、（但し、ｚは整数）を次のように加算と乗算で実行可能である。
【００１７】
Ｗｈｉｌｅ（ｚ＜ｍ）｛
ｚ０←ｚ  ｍｏｄ  ２ｒ
ｚ１←ｚ／２ｒの商    （すなわちｚ＝ｚ１２ｒ＋ｚ０、ｚ０＜２ｒ）
ｚ  ←ｚ１μ＋ｚ０
｝
なお、このアルゴリズムは次式に基づいている。
【００１８】
0003554525.tif 000002
係るｚ０とｚ１の計算は、剰余算（ｚ１μ＋ｚ０）ｍｏｄ  ｍがあるものの、ｚ０がｚの下位ｒビットを抽出して得られ、ｚ１がｚをｒビット右シフトして得られるため、計算機で十分高速に実行可能である。
【００１９】
剰余演算器２８は、このように剰余演算ｈ＝（ｆｇ＋ｃ＋ｄ）ｍｏｄ  ｍ＝（ｚ１μ＋ｚ０）ｍｏｄ  ｍを実行する。ここで、実行中の剰余演算結果ｈ’は、図示しないループ制御部により、法ｍと比較され、法ｍよりも大きい場合もしくは同じ場合（ｍ≦ｈ’）、再度、入力側に戻されて前述した抽出・乗算・加算からなる剰余算が繰返され、法ｍよりも小さい場合（ｈ’＜ｍ）には剰余演算結果ｈ（以下、剰余ともいう）として第３レジスタ２９に出力される。なお、大小比較は、減算ｈ’−ｍにより行われる。
【００２０】
第３レジスタ２９内の剰余演算結果ｈは、積和回路２０ｉから出力されてＲＡＭ２１ｉに書込まれる一方、次回の積和回路２０ｉの演算時には前回の剰余演算結果ｄとして加算器２３に与えられる。
【００２１】
【発明が解決しようとする課題】
しかしながら従来のモンゴメリ乗算装置及び方法では、ポッシュ又は川村の方式において、各積和回路２０ｉの剰余演算器２８における剰余算ｍｏｄ  ｍが加算や乗算と比較して処理量が多いので、Ｒｏｗｅｒユニットの演算を高速化、ひいてはＣｏｘ−Ｒｏｗｅｒアーキテクチャによる演算を高速化するためのネックとなっている。
【００２２】
このため、剰余算ｍｏｄ  ｍの更なる高速化が望まれている。
【００２３】
本発明は上記実情を考慮してなされたもので、剰余算の高速化により、少なくとも部分的な剰余演算を高速化でき、さらに全体的な演算速度の高速化を実現し得るモンゴメリ乗算装置及び方法を提供することを目的とする。
【００２４】
【課題を解決するための手段】
本発明の骨子は、Ｒｏｗｅｒユニットでの除算の条件を緩和し、剰余算を効率的に行なうことにあり、具体的には、Ｒｏｗｅｒユニットの積和回路における剰余算の終了条件を緩和することにある。
【００２５】
例えば、従来の剰余算ｈ＝ｚ  ｍｏｄ  ｍの終了条件は、実行結果ｈがｍよりも小さいとき（ｈ＜ｍ）である。
これに対し、本発明に係る剰余算ｈ＝ｚ  ｍｏｄ  ｍの終了条件は、実行結果ｈが２ｒよりも小さいとき（ｈ＜２ｒ）である。ここで、ｒはｍを２進表現したときのビット数である。すなわち、ｍ＜２ｒの関係がある。従って、本発明は、実行結果ｈが、法ｍよりも大きい値２ｒ未満に下がった時点で剰余算を終了するので、従来よりも剰余算を高速化することができる。
【００２６】
また、このように終了条件を緩和しても、後述する誤差の評価により演算の正確性を確認しているので、演算の信頼性を維持することができる。
さて以上のような本発明の骨子に基づいて、具体的には以下のような手段が講じられる。
請求項１に対応する発明は、正の整数Ｎと、Ｎ未満の正の整数ｘ，ｙとを入力とし、剰余演算系の基底を｛ａ１，ａ２，…，ａｉ，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｉ，…，ｂｎ｝（１≦ｉ≦ｎ、ｎは正の整数）としたとき、前記基底の要素の乗積として定義された整数Ｂ（＝ｂ１ｂ２…ｂｎ）を用いて、出力ｗ＝ｘｙＢ−１ｍｏｄ  Ｎを算出するためのモンゴメリ乗算装置であって、前記各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝と前記出力ｗの算出用の事前計算結果とが記憶される第１記憶手段と、前記基底の拡張用の入力ξｉを受けたとき、前記入力ξｉの上位ｑビットを抽出すると共に、この今回の抽出値と前回の最上位ビットを除く加算結果とを加算し、得られた加算結果のうち、最上位ビットの値ｋｉを出力する近似演算手段と、前記第１記憶手段の内容および前記近似演算手段の出力ｋｉに基づいて、前記各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝を法ｍとする剰余算（但し、法ｍ＝２ｒ−μは基底の一要素、ｒはｍ≦２ｒを満たす整数、μは２ｒ未満の非負整数）を実行する剰余演算手段と、前記剰余演算手段による剰余算の結果が記憶される第２記憶手段とを備え、前記剰余演算手段としては、前記第１記憶手段又は前記第２記憶手段からの入力ｘ，ｙの積ｘｙと前回の剰余算の結果ｄと前記近似演算手段の出力ｋｉに基づき入力される前記事前計算結果ｃとの和（ｘｙ＋ｄ＋ｃ）からなる入力ｚ（但し、ｚは正の整数）を受けると共に、前記入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行する剰余算部と、前記剰余算部による実行結果ｈ’と前記法ｍの上限値２ｒとを比較し、前記実行結果ｈ’が２ｒ以上のときには当該実行結果ｈ’を前記入力ｚとして前記剰余算部に戻し、前記実行結果ｈ’が２ｒ未満のときには当該実行結果ｈ’を前記剰余算の結果ｈとして前記第２記憶手段に出力するループ制御部と、を備えたモンゴメリ乗算装置である。
【００２７】
また、請求項２に対応する発明は、請求項１に対応するモンゴメリ乗算装置において、前記剰余算部としては、前記入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄｍを実行するとき、前記入力ｚの下位ｒビットの値ｚ０と、前記入力ｚから前記下位の値ｚ０を除いた上位ビットの値ｚ１とを夫々抽出するビット選択部と、前記ビット選択部により抽出された上位ビットの値ｚ１と前記法ｍに関する入力μとを受けたとき、両者の積ｚ１μを算出する乗算部と、前記乗算部により得られた積ｚ１μと前記ビット選択部により抽出された下位ｒビットの値ｚ０との和（ｚ１μ＋ｚ０）を算出する加算部とを備え、前記剰余算部による実行結果ｈ’は、前記加算部により得られた和（ｚ１μ＋ｚ０）であるモンゴメリ乗算装置である。
【００２８】
さらに、請求項３に対応する発明は、正の整数Ｎと、Ｎ未満の正の整数ｘ，ｙとを入力とし、剰余演算系の基底を｛ａ１，ａ２，…，ａｉ，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｉ，…，ｂｎ｝（１≦ｉ≦ｎ、ｎは正の整数）としたとき、前記基底の要素の乗積として定義された整数Ｂ（＝ｂ１ｂ２…ｂｎ）を用いて、出力ｗ＝ｘｙＢ−１ｍｏｄ  Ｎを算出するためのモンゴメリ乗算方法であって、前記各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝と前記出力ｗの算出用の事前計算結果とが記憶される第１記憶工程と、前記基底の拡張用の入力ξｉを受けたとき、前記入力ξｉの上位ｑビットを抽出すると共に、この今回の抽出値と前回の最上位ビットを除く加算結果とを加算し、得られた加算結果のうち、最上位ビットの値ｋｉを出力する近似演算工程と、前記第１記憶工程の記憶内容および前記近似演算工程の出力ｋｉに基づいて、前記各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝を法ｍとする剰余算（但し、法ｍ＝２ｒ−μは基底の一要素、ｒはｍ≦２ｒを満たす整数、μは２ｒ未満の非負整数）を実行する剰余演算工程と、前記剰余演算工程による剰余算の結果が記憶される第２記憶工程とを含んでおり、前記剰余演算工程としては、前記第１記憶工程の記憶内容又は前記第２記憶工程の記憶内容からの入力ｘ，ｙの積ｘｙと前回の剰余算の結果ｄと前記近似演算工程の出力ｋｉに基づき入力される前記事前計算結果ｃとの和（ｘｙ＋ｄ＋ｃ）からなる入力ｚ（但し、ｚは正の整数）を受けると共に、前記入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行する剰余算工程と、前記剰余算工程による実行結果ｈ’と前記法ｍの上限値２ｒとを比較し、前記実行結果ｈ’が２ｒ以上のときには当該実行結果ｈ’を前記入力ｚとして前記剰余算工程に戻し、前記実行結果ｈ’が２ｒ未満のときには当該実行結果ｈ’を前記剰余算の結果ｈとして前記第２記憶工程に出力するループ制御工程と、を含んでいるモンゴメリ乗算方法である。
【００２９】
また、請求項４に対応する発明は、請求項３に対応するモンゴメリ乗算方法において、前記剰余算工程としては、前記入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行するとき、前記入力ｚの下位ｒビットの値ｚ０と、前記入力ｚから前記下位の値ｚ０を除いた上位ビットの値ｚ１とを夫々抽出するビット選択工程と、前記ビット選択工程により抽出された上位ビットの値ｚ１と前記法ｍに関する入力μとを受けたとき、両者の積ｚ１μを算出する乗算工程と、前記乗算工程により得られた積ｚ１μと前記ビット選択工程により抽出された下位ｒビットの値ｚ０との和（ｚ１μ＋ｚ０）を算出する加算工程とを含んでおり、前記剰余算工程による実行結果ｈ’は、前記加算工程により得られた和（ｚ１μ＋ｚ０）であるモンゴメリ乗算方法である。
【００３０】
（作用）
従って、請求項１，３に対応する発明は以上のような手段を講じたことにより、剰余演算手段としては、剰余算部が、第１記憶手段又は第２記憶手段からの入力ｘ，ｙの積ｘｙと前回の剰余算の結果ｄと近似演算手段の出力ｋｉに基づき入力される事前計算結果ｃとの和（ｘｙ＋ｄ＋ｃ）からなる入力ｚ（但し、ｚは正の整数）を受けると共に、入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行し、ループ制御部が、剰余算部による実行結果ｈ’と法ｍの上限値２ｒとを比較し、実行結果ｈ’が２ｒ以上のときには当該実行結果ｈ’を入力ｚとして剰余算部に戻し、実行結果ｈ’が２ｒ未満のときには当該実行結果ｈ’を剰余算の結果ｈとして第２記憶手段に出力する。
【００３１】
このように、法ｍでの剰余算であるにも関わらず、剰余算の実行結果ｈ’を法ｍよりも大きい値２ｒと比較するように剰余算の終了条件を緩和したので、剰余算の高速化により、少なくとも部分的な剰余演算を高速化でき、さらに全体的な演算速度の高速化を実現させることができる。
【００３２】
また、剰余算の終了条件を緩和したが、後述する誤差の評価により演算の正確性を確認しているので、演算結果の信頼性を維持することができる。
【００３３】
また、請求項２，４に対応する発明は、剰余算部としては、ビット選択部が、入力ｚの法ｍによる剰余算ｈ＝ｚ  ｍｏｄ  ｍを実行するとき、入力ｚの下位ｒビットの値ｚ０と、入力ｚから下位の値ｚ０を除いた上位ビットの値ｚ１とを夫々抽出し、乗算部が、ビット選択部により抽出された上位ビットの値ｚ１と法ｍに関する入力μとを受けたとき、両者の積ｚ１μを算出し、加算部が、乗算部により得られた積ｚ１μとビット選択部により抽出された下位ｒビットの値ｚ０との和（ｚ１μ＋ｚ０）を算出し、剰余算部による実行結果ｈ’を、加算部により得られた和（ｚ１μ＋ｚ０）としたので、剰余算をビットの抽出・加算・乗算などの簡単な処理で実行でき、請求項１，３に対応する作用を容易且つ確実に奏することができる。
【００３４】
【発明の実施の形態】
以下、本発明の一実施形態について図面を参照して説明する。
始めに、本発明のモンゴメリ乗算装置及び方法に適用されるモンゴメリ乗算アルゴリズムについて説明する。
まず、ＲＮＳ表現におけるモンゴメリ乗算アルゴリズムを説明する。ここで、モンゴメリ乗算の法をＮとし、入力をｘ，ｙ＜２Ｎとする。出力は、ｗ＝ｘｙＢ−１ｍｏｄ  Ｎ、又はｗ＝ｘｙＢ−１ｍｏｄ  Ｎ＋Ｎである。係るモンゴメリ乗算アルゴリズムは、次のような７つのステップＳＴ１〜ＳＴ７で表せる。
ＳＴ１．＜ｓ＞ａ←＜ｘ＞ａ＜ｙ＞ａ、＜ｓ＞ｂ←＜ｘ＞ｂ＜ｙ＞ｂ
ＳＴ２．＜ｔ＞ｂ←＜ｓ＞ｂ＜（−Ｎ）−１＞ｂ
ＳＴ３．＜ｔ＞ｂから基底拡張により＜ｔ＞ａ∪ｂを求める。
ＳＴ４．＜ｕ＞ａ←＜ｔ＞ａ＜Ｎ＞ａ
ＳＴ５．＜ｖ＞ａ←＜ｓ＞ａ＋＜ｕ＞ａ
ＳＴ６．＜ｗ＞ａ←＜ｖ＞ａ＜Ｂ−１＞ａ
ＳＴ７．＜ｗ＞ａから基底拡張により＜ｗ＞ａ∪ｂを求める。
【００３５】
ここで、＜ｓ＞ａは、基底ａの下でのｓのＲＮＳ表現を表す。その他の＜ｔ＞ｂなども同様である。例えば＜ｓ＞ａは、Ａ＝ａ１ａ２…ａｎを法とする剰余環の元ｓを基底ａの各要素ａ１〜ａｎで割った余りの組（ｓ１，ｓ２，…，ｓｎ）を表す。
【００３６】
基底ｂ＝｛ｂ１，ｂ２，…，ｂｎ｝は基底ａとは別のＲＮＳ基底であり、Ｂ＝ｂ１ｂ２…ｂｎとしたとき、ＡとＢの最大公約数ｇｃｄ（Ａ，Ｂ）＝１である基底である。ステップＳＴ１〜ＳＴ７の正確な計算には、少なくともＮ＜Ａ，Ｎ＜Ｂという条件が必要である。この条件からｘやｙは、基底ａのみ、あるいは基底ｂのみで一意的に表現できるので、入力ｘを＜ｘ＞ａ、＜ｘ＞ｂのペアで表すことは冗長である。しかし、入力ｘ，ｙは、両者の積ｓのとる範囲が０≦ｓ＜Ｎ２であるため、基底ａ，ｂの合併集合ａ∪ｂを基底ａ∪ｂとして始めて正しく表現される。
【００３７】
次に、以上のようなモンゴメリ乗算アルゴリズムのうち、ステップＳＴ３，ＳＴ７の基底拡張について説明する。
いまβをＡ未満の非負整数とし（０≦β＜Ａ）、非負整数βのＲＮＳ表現を＜β＞ａ＝（β１，β２，…，βｎ）とする。ここで、＜β＞ａから基底拡張により＜β＞ａ∪ｂを求めるとする。
【００３８】
このとき、周知の中国剰余定理から次の（１）式が成り立つ。
【００３９】
【数１】
0003554525.tif 000003
【００４０】
但し、Ａｉ＝Ａ／ａｉであり、Ａｉ−１は法ａｉにおけるＡｉの乗法逆元である。このとき（１）式のｍｏｄＡを次の（２）式のように減算でも表せる。
【００４１】
【数２】
0003554525.tif 000004
【００４２】
（２）式のように、ｍｏｄ  Ａを減算で表すとき、−Ａの倍数となる非負整数ｋがただ一つ存在する。この−Ａの倍数ｋの計算が、ポッシュや川村のＲＮＳ表現でのモンゴメリ乗算の処理速度を決めるポイントとなっている。
【００４３】
次に、倍数ｋを算出する際に、効率の良い川村のアルゴリズムを説明する。（２）式の両辺をＡで割ると、次の（３）式になる。
【００４４】
【数３】
0003554525.tif 000005
【００４５】
ここで、小数部の切捨て操作を記号［］で表すと、（５）式に基づき、次の（６）式のように倍数ｋを表すことができる。
【００４６】
【数４】
0003554525.tif 000006
【００４７】
この（６）式は、除算を含むため、川村は次の（７）式のように近似計算をして倍数ｋ’を求めている。
【００４８】
【数５】
0003554525.tif 000007
【００４９】
ここで、ξｉ＝βｉ×Ａｉ−１ｍｏｄ  ａｉである。ｔｒｕｎｃ（）は、ｒビットの変数ξｉのうち、上位ｑビットを維持して上位ｑビット目より下位の（ｒ−ｑ）ビットを全て０にする切捨て関数である。ｒは基底要素のビット数であり、ｑはｒ未満の正整数である。
【００５０】
実際に（７）式は、ハードウェアで計算されるとき、以下のように逐次的に実行される。
ｆｏｒ（ｉ＝０；ｉ＜＝ｎ；ｉ＋＋）｛
σｉ＝σｉ−１＋ｔｒｕｎｃ（ξｉ）／２ｒ
ｋｉ＝［σｉ］
σｉ＝σｉ−ｋｉ
｝
ここで、σ０＝α、０≦α＜１を初期値とする。αは誤差の補正のために導入されている。また、規則正しい処理を行なう観点から、ビット数ｒは全ての基底要素で共通とするのが望ましく、ここではそのように仮定する。
【００５１】
（７）式で近似計算した倍数ｋ’は、（６）式で得られる正確な倍数ｋに対して近似誤差が生じる。そこで、（７）式の近似誤差の評価のため、次の（８）〜（９）式に示すように、（７）式の分母の評価変数εａ，と、分子の評価変数δａとが導入される。
【００５２】
εａ＝ｍａｘ｛（２ｒ−ａｉ）／２ｒ｝      …（８）
δａ＝ｍａｘ｛（ξｉ−ｔｒｕｎｃ（ξｉ））／ａｉ｝      …（９）
なお、ｍａｘ｛｝はｉを１，２，…，ｎと動かしたときの最大値を表す。
川村によれば、これら評価変数εａ，δａを用い、入力βが次の（１０）式の範囲内にあるとき、近似計算の（７）式は正しいｋの値を与える。
【００５３】
ｎ（εａ＋δａ）Ａ≦β＜Ａ      …（１０）
また、川村によれば、入力βが次の（１１）式の範囲内のとき、近似計算の（７）式は正しいｋ又はｋ−１の値を与える。
【００５４】
０≦β＜ｎ（εａ＋δａ）Ａ      …（１１）
また、（７）式に基づいて、近似値ｋ’を計算し、次の（１２）式を各ｉ＝１，２，…，ｎについて実行することで、基底ａから基底ｂの表現を作り出すことができる。但しこの（１２）式の場合は誤差が生じる可能性がある。
【００５５】
【数６】
0003554525.tif 000008
【００５６】
以上の説明では、基底ａから基底ｂへの拡張方法を述べたが、記号ａと記号ｂとの交換により、基底ｂから基底ａへの基底拡張方法、および評価変数εｂ，δｂが得られる。
【００５７】
さらに、川村によれば、この近似値ｋ’を使った基底拡張アルゴリズム（１２）式を用いて、ステップＳＴ１〜ＳＴ７のＲＮＳ表現でのモンゴメリ乗算アルゴリズムを実行した場合、次の５つの条件（１３）〜（１７）式を満たすときには、ｗ＝ｘｙＢ−１ｍｏｄ  Ｎ，ｗ＜２Ｎなる＜ｗ＞ａ∪ｂを出力することが示されている。ここで、Δ＝ｎ（ε＋δ）、ε＝ｍａｘ｛εａ，εｂ｝、δ＝ｍａｘ｛δａ，δｂ｝である。
【００５８】
ｇｃｄ（Ａ，Ｂ）＝１      …（１３）
ｇｃｄ（Ｂ，Ｎ）＝１      …（１４）
０≦Δ≦α＜１          …（１５）
４Ｎ／（１−Δ）≦Ｂ      …（１６）
２Ｎ／（１−α）≦Ａ      …（１７）
以上が本発明に適用されるモンゴメリ乗算アルゴリズムである。次に、以上のようなモンゴメリ乗算アルゴリズムを適用対象とする本発明の一実施形態について図面を参照しながら説明する。
【００５９】
図１は本発明の一実施形態に係るモンゴメリ乗算装置の構成を示す模式図であり、図２はこのモンゴメリ乗算装置内の積和回路の構成を示す模式図であり、図３はこの積和回路内の除算回路の構成を示す模式図であって、前述した図面と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００６０】
すなわち、本実施形態は、前述したＣｏｘ−Ｒｏｗｅｒユニットの高速化を図るものであり、具体的には図１〜図３に示すように、前述した剰余演算器２８を有する各積和回路２０１〜２０ｎに代えて、除算回路４０を有する積和回路３０１〜３０ｎを備えている。
【００６１】
ここで、各積和回路３０ｉ（但し１≦ｉ≦ｎ）は、図２に示すように、（ｆｇ＋ｃ＋ｄ）ｍｏｄ  ｍを計算するユニットであり、前述した剰余演算器２８に代えて、除算回路４０を備えている。なお、ｍは、前述同様にＲＮＳ基底のある一要素である。但し、ｆ，ｇ，ｃ，ｄは、従来のｍ未満の整数とは異なり、２ｒ以下の正整数である。
【００６２】
除算回路（剰余演算器）４０は、加算器２４の出力結果ｆｇ＋ｃ＋ｄを法ｍで割った剰余ｈを計算するものであり、ハードウェア又はソフトウェアのいずれでもよいが、図３に示すように、ビット選択部４１、乗算器４２、加算器４３及びループ制御部４４を備えている。
【００６３】
ビット選択部４１は、入力された整数ｚを下位ｒビットの値ｚ０と、入力された整数ｚから下位ｒビットを除いた上位ビットの値ｚ１とを夫々抽出する機能を持っている。ここで、値ｚ０，ｚ１は、夫々次式を満たすものとなる。
【００６４】
ｚ０＝ｚ  ｍｏｄ  ｍ
ｚ１＝［ｚ／２ｒ］
乗算器４２は、ビット選択部４１により抽出された上位ビットの値ｚ１と、法ｍをｍ＝２ｒ−μと表したときのμとの積ｚ１μを計算し、得られた積ｚ１μを加算器４３に出力する機能をもっている。
【００６５】
加算器４３は、ビット選択部４１で選択されたｚ０と乗算器４２の出力ｚ１μを加算する。
【００６６】
ループ制御部４４は、加算器４３の出力結果ｚ１μ＋ｚ０を法ｍの上限値２ｒと比較し、大きい場合もしくは同じ場合（２ｒ≦ｚ１μ＋ｚ０（＝ｈ’））はｚ１μ＋ｚ０を改めてｚとしてビット選択部４１に入力して処理を繰返し、小さい場合はｚ１μ＋ｚ０を剰余算結果ｈとして第３レジスタ２９を介してＲＡＭ２１ｉに出力するように制御する機能をもっている。すなわち、除算回路４０の出力ｈは、ｈ＝ｚ  ｍｏｄ  ｍ、ｈ＜２ｒを満たすものである。
【００６７】
次に、以上のように構成されたモンゴメリ乗算装置によるモンゴメリ乗算方法について説明する。
【００６８】
いま、本実施形態装置は、入力ｘ，ｙ、法Ｎ、基底ａ，ｂを準備し、ＲＯＭ２１１〜２１ｎに各基底の要素｛ａ１，ａ２，…，ａｎ｝および｛ｂ１，ｂ２，…，ｂｎ｝と出力ｗの算出用の事前計算結果とを記憶させた後、ステップＳＴ１〜ＳＴ７のモンゴメリ乗算アルゴリズムを実行する。また、ステップＳＴ３，ＳＴ７の基底拡張は、川村のアルゴリズム（１２）式に従って実行される。このとき、Ｃｏｘユニットとしては、基底の拡張用の入力ξｉを受けると、入力ξｉの上位ｑビットを抽出すると共に、この今回の抽出値と前回の最上位ビットを除く加算結果とを加算し、得られた加算結果のうち、最上位ビットの値ｋｉを各Ｒｏｗｅｒユニットの積和回路３０１〜３０ｎに出力する。
【００６９】
さて、ここでモンゴメリ乗算アルゴリズムＳＴ１〜ＳＴ７内の各基底成分の計算について詳述する。
例えば、ＳＴ１の計算＜ｓ＞ａ←＜ｘ＞ａ・＜ｙ＞ａの第一成分ｘ１・ｙ１  ｍｏｄ  ａ１を考える。
【００７０】
この計算は、図１中、第１のＲｏｗｅｒユニットで行なわれ、剰余乗算が第１の積和回路３０１により実行される。
具体的には図２に示すように、まず積和回路３０１に入力されたｘ１，ｙ１が乗算器２３に入力される。乗算器２３はその積ｘ１・ｙ１を計算して加算器２４に出力する。
【００７１】
この計算では、スイッチ２５が開いているので入力ｃが無く、前回の演算結果ｄも０である。このため、積ｘ１・ｙ１とｄ＝０とが加算器２４に入力される。
【００７２】
加算器２４はこの和を計算して除算回路４０に出力する。この結果ｘ１・ｙ１と、基底ａ１をａ１＝２ｒ−μ１としたときのμ１とが除算回路４０に入力される。
【００７３】
ここで、除算回路４０は、ｈ＝ｘ１・ｙ１  ｍｏｄ  ａ１（但しｈ＜２ｒ）を出力する。なお、この除算回路４０は、法ａ１の除算を実行するものの、従来とは異なり、大小比較の対象を２ｒとして除算結果ｈを出力する。
なお、除算回路４０は、大小比較の対象を２ｒとしたので、図３に示した構成に限らず、剰余算を高速化することができる。但し、ここでは図３に示した構成を例に挙げて述べる。
【００７４】
まず、整数ｚ＝ｘ１・ｙ１が除算回路４０に入力される。
【００７５】
除算回路４０においては、ビット選択部４１が、下位ｒビットの値ｚ０＝ｚ  ｍｏｄ  ２ｒと、残りの上位ビットの値ｚ１＝［ｚ／２ｒ］とを抽出し、上位ビットの値ｚ１と入力μ１とが乗算器４２に入力される。
【００７６】
乗算器４２は積ｚ１μ１を計算して加算器４３に出力する。この出力ｚ１μ１と、ビット選択部４１で抽出された下位ビットの値ｚ０とが加算器４３に入力される。
【００７７】
加算器４３は、これらの和ｈ＝ｚ１μ１＋ｚ０を計算して出力する。
【００７８】
ループ制御部４４は、加算器４３からの出力ｈ’を法ｍの上限値２ｒと大小比較し、出力ｈ’が２ｒ以上のとき、出力ｈ’を改めてビット選択部の入力ｚとして処理を繰り返す。
【００７９】
また、ループ制御部４４は、大小比較の結果、出力ｈが２ｒ未満のときにはループ終了と判断し、出力ｈ’を剰余ｈとして出力する。なお、本来、法ａ１の剰余算を行なうものであるが、出力ｈが法ａ１より大でもよい。
【００８０】
このときｈ＝ｘ１・ｙ１  ｍｏｄ  ａ１、ｈ＜２ｒを満たす。ｈは、積和回路３０１から出力され、ＲＡＭ２１１に格納される。
【００８１】
この部分以外にもＲｏｗｅｒユニットでの剰余演算が必要なときは同様の処理を行なう。
ここで、本発明の除算回路４０による剰余算の高速化について補足的に説明する。
従来は、図示しないループ制御部にて、剰余演算結果ｈ’と、基底の一要素（例、ａ１）とを大小比較するため、減算ｈ’−ａ１を行ない、その減算結果が負になるか否かを確認することが必要である。
【００８２】
一方、本発明は、加算器４３からの出力ｈ’と、基底要素のビット数ｒで示せる上限値２ｒとを大小比較するため、出力ｈ’が（ｒ＋１）ビット以上であるか否かを確認すればよいので、従来の減算よりも、効率的かつ高速にループの制御を実行できる。
【００８３】
本発明は、このようなループ制御自体の高速化に加え、ループ回数自体も減少していることにより高速化を実現している。
例えば、本願発明でのループ回数は、出力ｈが上限値２ｒ未満（ｈ＜２ｒ）に減少するまでの繰返し回数である。一方、従来のループ回数は、出力ｄが法ａ１未満（ｄ＜ａ１）に減少するまでの繰返し回数である。ここで、基底の要素ａ１はそのビット数ｒにおける上限値２ｒよりも小さい（ａ１＜２ｒ）。
【００８４】
従って、一般に、出力ｈが上限値２ｒ未満に低減するまでのループ回数の方が、出力ｄが法ａ１未満に低減するまでのループ回数よりも少ない。すなわち、本願発明のループ回数の方が従来のループ回数よりも通常少ない。
【００８５】
すなわち、本発明は、このようにループ回数が少ないことにもより、剰余算の高速化を実現することができる。
（誤差の評価）
本発明のモンゴメリ乗算装置及び方法を用いてステップＳＴ１〜ＳＴ７のモンゴメリ乗算アルゴリズムを実行するときの誤差の評価は次の各式で与えられる。
【００８６】
いま、分母の評価関数εを、ε＜２−τ（但しτ＞０）の範囲とする。ここで、τは、εの範囲を規定するために導入した正整数である。
【００８７】
このとき、βが次の（１０ａ）式の範囲内にあれば、（７）式の近似計算は正しいｋの値を与える。
【００８８】
ｎ（ε・２τ／（２τ−１）＋δ）Ａ≦β＜１      …（１０ａ）
また、βが次の（１１ａ）式の範囲内にあれば、（７）式の近似計算は正しいｋ又はｋ−１を与える。
【００８９】
０≦β＜ｎ（ε・２τ／（２τ−１）＋δ）Ａ      …（１１ａ）
これら（１０ａ），（１１ａ）式は、それぞれ前述した（１０），（１１）式に対応した条件であり、考えている状況も（１０），（１１）式の状況と同じとする。
また、モンゴメリ乗算も前述した５つの条件（１３）〜（１７）式のうち、補正項αの範囲を定めた（１５）式を次の（１５ａ）式と置換することで、ｗ＝ｘｙＢ−１ｍｏｄ  Ｎ、またはｗ＝ｘｙＢ−１ｍｏｄ  Ｎ＋Ｎを出力する。
【００９０】
０≦ｎ（ε・２τ／（２τ−１）＋δ）Ａ≦α＜１      …（１５ａ）
実用上、Ｎが１，０２４ビットの場合を考えると、ｎ＝３３、α＝０．５と取れば良く、このとき上のτは、τ≧２２程度と取れることが確認できる。
【００９１】
このとき２τ／（２τ−１）は１に十分近く、（１０ａ），（１１ａ），（１５ａ）式の条件は、それぞれ（１０），（１１），（１５）式と対応しているが、これらとほぼ同じ条件となっている。
【００９２】
すなわち、本実施形態を実行した場合であっても、誤差を正確に評価できるので、本実施形態の装置及び方法の信頼性を確保することができる。
上述したように本実施形態によれば、法ｍでの剰余算であるにも関わらず、剰余算の実行結果ｈ’を法ｍよりも大きい値２ｒと比較するように剰余算の終了条件を緩和したので、２ｒという比較の容易な数の採用によるループ制御自体の高速化と、２ｒという大きい数の採用によるループ回数の低減化とによる剰余算の高速化により、少なくとも部分的な剰余演算を高速化でき、さらに全体的な演算速度の高速化を実現させることができる。
【００９３】
また、剰余算の終了条件を緩和したが、（１０ａ），（１１ａ），（１５ａ）式からなる誤差の評価により演算の正確性を確認しているので、演算結果の信頼性を維持することができる。
【００９４】
また、除算回路４０が、ビット選択部４１、乗算部４２、加算部４３を有し、実行結果ｈ’を、加算部により得られた和（ｚ１μ＋ｚ０）とする場合、剰余算をビットの抽出・加算・乗算などの簡単な処理で実行できるので、前述した効果を容易且つ確実に奏することができる。
【００９５】
また、本実施形態に係るＣｏｘ−Ｒｏｗｅｒアーキテクチャは、例えばチップを搭載したボード等により実現でき、このボードをサーバ装置にさし込むことにより、サーバ上に実現させることもできる。
【００９６】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピーディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【００９７】
なお、本願発明は、上記各実施形態に限定されるものでなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は可能な限り適宜組み合わせて実施してもよく、その場合、組み合わされた効果が得られる。さらに、上記各実施形態には種々の段階の発明が含まれており、開示される複数の構成用件における適宜な組み合わせにより種々の発明が抽出され得る。例えば実施形態に示される全構成要件から幾つかの構成要件が省略されることで発明が抽出された場合には、その抽出された発明を実施する場合には省略部分が周知慣用技術で適宜補われるものである。
【００９８】
その他、本発明はその要旨を逸脱しない範囲で種々変形して実施できる。
【００９９】
【発明の効果】
以上説明したように本発明によれば、剰余算の高速化により、少なくとも部分的な剰余演算を高速化でき、さらに全体的な演算速度の高速化を実現し得るモンゴメリ乗算装置及び方法を提供できる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係るモンゴメリ乗算装置の構成を示す模式図
【図２】同実施形態における積和回路の構成を示す模式図
【図３】同実施形態における除算回路の構成を示す模式図
【図４】従来のモンゴメリ乗算装置の構成を示す模式図
【図５】従来の積和回路の構成を示す模式図
【符号の説明】
１１，４１…ビット選択部
１２，２４，４３…加算器
２３，４２…乗算器
２５…スイッチ
２６，２７，２９…レジスタ
３０１〜３０ｎ…積和回路
４０…除算回路
４４…ループ制御部
【図１】
0003554525.tif 000009
【図２】
0003554525.tif 000010
【図３】
0003554525.tif 000011
【図４】
0003554525.tif 000012
【図５】
0003554525.tif 000013