べき乗演算装置
【目的】 べき乗剰余演算ＡB ｍｏｄＮにおいて、剰余逆元Ａ-1ｍｏｄＮにより、剰余乗算の最大回数ばかりでなく、平均回数についても削減を図り、高速なべき乗演算装置を提供する。
【構成】 ０≦Ａ≦Ｎ−１なる関係がある複数ビットで表現される整数ＡとＮ、及び複数ビットで表現される整数Ｂで、ＡB mod Ｎなるべき乗剰余演算を行う。Ａ，Ｂ，Ｎは記憶手段ＡＲ，ＢＲ，ＮＲに記憶される。整数Ａの剰余逆元ＡＩ＝Ａ-1ｍｏｄＮは記憶手段ＡＩＲに、また演算途中結果の整数Ｘは記憶手段ＸＲにそれぞれ記憶される。選択手段ＳＥＬはＡ，Ｘ，ＡＩから一つの整数Ｙを選択する。剰余乗算手段ＳＭはＸ×ＹｍｏｄＮなる剰余乗算を行い、その出力で記憶手段ＸＲを更新する。記憶手段ＢＲのデータをコード変換する手段ＣＣを設け、非０のビットの生起確率を削減する。制御手段ＣＮＴはＢのコード変換したビットの０，１，−１の値に応じて選択手段ＳＥＬを制御する。
【構成】 ０≦Ａ≦Ｎ−１なる関係がある複数ビットで表現される整数ＡとＮ、及び複数ビットで表現される整数Ｂで、ＡB mod Ｎなるべき乗剰余演算を行う。Ａ，Ｂ，Ｎは記憶手段ＡＲ，ＢＲ，ＮＲに記憶される。整数Ａの剰余逆元ＡＩ＝Ａ-1ｍｏｄＮは記憶手段ＡＩＲに、また演算途中結果の整数Ｘは記憶手段ＸＲにそれぞれ記憶される。選択手段ＳＥＬはＡ，Ｘ，ＡＩから一つの整数Ｙを選択する。剰余乗算手段ＳＭはＸ×ＹｍｏｄＮなる剰余乗算を行い、その出力で記憶手段ＸＲを更新する。記憶手段ＢＲのデータをコード変換する手段ＣＣを設け、非０のビットの生起確率を削減する。制御手段ＣＮＴはＢのコード変換したビットの０，１，−１の値に応じて選択手段ＳＥＬを制御する。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、０≦Ａ≦Ｎ−１なる関係がある複数ビットで表現される整数ＡとＮ、ならびに複数ビットで表現される整数Ｂにおける、ＡB ｍｏｄＮなるべき乗剰余演算を実行するとき有用な、べき乗演算装置に関する。さらに、本発明は、複数ビットで表現される０以外の実数Ａと整数Ｂにより、ＡB なるべき乗演算を実行するとき有用な、べき乗演算装置に関する。
【０００２】
【従来の技術】ＡB またはＡB ｍｏｄＮなどのべき乗演算は、基本的には乗算（積Ｘ×Ｙを求める）または剰余乗算（積Ｘ×ＹｍｏｄＮを求める）を繰り返して実行され、べきの指数部Ｂの桁数が大きくなると、単純な乗算または剰余乗算の繰り返し回数の増大が高速化を妨げる要因となる。
（従来法１）〔参考資料；森田：「暗号技術と高速算法」，情報処理，Ｖｏｌ．３４，Ｎｏ．３，ｐｐ．３４１，平成５年３月」
そこで、整数Ｂをｂi からなるビットに分解し、ＡB ｍｏｄＮのべき乗剰余演算を高速化する手法が提案された。手順は、図４に示す様に、ｂi に対応させて、Ｘ×ＸｍｏｄＮ，Ｘ×ＡｍｏｄＮを組み合わせ、剰余乗算の実行回数をＢの桁数程度に削減する。図５に示す様に、装置上では、整数Ａ，Ｂ，Ｎのデータが入力され、それぞれの記憶手段ＡＲ，ＢＲ，ＮＲに蓄積する。前記整数ＡまたはＸから選択し整数Ｙを出力する選択手段ＳＥＬと、演算途中結果の整数Ｘを蓄積する記憶手段ＸＲと、これらの記憶手段ＸＲ，ＮＲと選択手段ＳＥＬの各々の出力から剰余乗算手段ＳＭがＸ×ＹｍｏｄＮを実行し、得られた出力で記憶手段ＸＲのデータを更新する。選択手段ＳＥＬをはじめ各部を制御する制御手段ＣＮＴは、記憶手段ＢＲに蓄積されるｂi の値に従い、図４におけるＸ×ＸｍｏｄＮまたはＸ×ＡｍｏｄＮなどの実行の順序を制御する。
【０００３】ＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）などの暗号分野で用いられるべき乗剰余演算ＡB ｍｏｄＮは、０≦Ａ，Ｂ≦Ｎ−１の関係があり、Ｎは５１２ビット程度が採用されることが多い。この様な場合、Ｂも５１２ビットとするとＸ×ＸｍｏｄＮなる剰余乗算が５１１回、Ｘ×ＡｍｏｄＮなる剰余乗算に最大５１１回、平均２５５回が必要となる。従って、剰余乗算が最大１０２２回、平均７６６回必要になる。一般には、指数部Ｂのビット数をｍとするとき、最大２（ｍ−１）回の剰余乗算、平均３（ｍ−１）／２回の剰余乗算が必要となる。
【０００４】以上、べき乗剰余演算ＡB ｍｏｄＮを対象に説明したが、Ｂのビット数ｍと剰余乗算回数との関係は、べき乗演算ＡB における、Ｂのビット数ｍと乗算回数との関係にも同様のことが成り立つ。但し、べき乗演算ＡB は、法Ｎ内に途中結果が収まるべき乗剰余演算ＡB ｍｏｄＮと異なり、途中結果の桁数が増大するので、仮数部と指数部を分ける近似的な表現が取られることが多い。
（従来法２）〔参考資料；Ｂｒｉｃｋｅｌｌ，Ｅ．Ｆ．：“Ａ Ｆａｓｔ Ｍｏｄｕｌａｒ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｗｉｔｈＡｐｐｌｉｃａｔｉｏｎ ｔｏ Ｔｗｏ Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ，Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ′８２，ｐｐ．５１−６０，Ｐｌｅｎｕｍ（１９８３）〕
剰余乗算の回数を少しでも減らそうとして開発されたのが従来法２である。手順を図６に示す。そこで、Ｂをｂi からなるビット列対応に分解し、そのビットで１が立つ回数が半分を越えるとき、剰余逆元Ａ-1ｍｏｄＮを求め、繰り返しの演算では、半分より少ない筈のｂi ＝０がある時とほぼ同じ回数だけ、ＸとＡ-1ｍｏｄＮとの剰余乗算を実行する。逆に、そのビットで１が立つ回数が半分以下のときは従来法１と同じ処理を行う。
【０００５】図７に示す装置上で図６の処理を実行する場合、整数Ａ，Ｂ，Ｎが記憶手段Ａ（ＡＩ）Ｒ，ＢＲ，ＮＲに入力され、制御手段ＣＮＴにＢの“１”の値を持つビット数の大小を判定させ、“１”が多い場合、Ｘの記憶手段ＸＲに整数Ａを設定したあと、装置外から剰余逆元Ａ-1ｍｏｄＮ＝ＡＩを記憶手段Ａ（ＡＩ）Ｒに読み込み、図４と同様の手順で実行する。装置に剰余逆元手段がある場合、内部的に記憶手段Ａ（ＡＩ）ＲのデータをＡからＡＩ＝Ａ-1ｍｏｄＮに書き換える。
【０００６】Ｂが５１２ビットとすると、Ｘ×ＸｍｏｄＮなる剰余乗算が５１１回、Ｘ×ＡｍｏｄＮなる剰余乗算に最大２５５回が必要となる。従って、剰余乗算が最大７６６回が必要になる。一般には、指数部Ｂのビット数をｍとするとき、最大３（ｍ−１）／２回の剰余乗算が必要となる。同様に、べき乗演算ＡB を求める際、仮数部と指数部を分ける近似的な表現が必要であるが、上記剰余逆元Ａ-1ｍｏｄＮを１／Ａに置き換えることで、同様の乗算回数の削減が可能である。
【０００７】以上の様に、従来法では、べき乗剰余における剰余乗算の回数、べき乗における乗算の回数を削減するため、指数部をビット単位に行う手法、逆元（剰余逆元または逆数）を利用する手法が利用されて来た。
【０００８】
【発明が解決しようとする課題】従来法２は最大の乗算回数を削減する効果が有った。しかし、最大の乗算回数は、Ｂにおけるｍビットが（コインなげで表または裏を出すベルヌーイ試行と同様に）０又は１にランダムに分布している場合、１の生起確率は２項分布に従っているから、Ｘ×ＡｍｏｄＮなる剰余乗算の所要回数は最大ｍであっても、平均はｍ／２近傍にある。この為、従来法２は従来法１に比べ改良の効果が少なく、逆に逆元を演算するのに要する時間が付加されるので有効ではなかった。
【０００９】本発明の目的は、べき乗剰余演算ＡB ｍｏｄＮにおいて、剰余逆元Ａ-1ｍｏｄＮにより、剰余乗算の最大回数ばかりでなく、平均回数も削減を図り、高速なべき乗演算装置を提供することにある。また、同様に、べき乗演算ＡB においては、逆数１／Ａにより、乗算の最大回数ばかりでなく、平均回数も削減を図り、高速なべき乗演算装置を提供することにある。
【００１０】
【課題を解決するための手段】上記目的を達成するために、本発明は、べき乗剰余ＡB ｍｏｄＮまたはべき乗演算ＡB において、数Ａに対する逆元であるＡ-1ｍｏｄＮまたは１／Ａを利用するとともに、指数部Ｂを基数４、つまりバイナリ−コード２ビット分の符号付冗長表現にコード変換する機構により、乗算に要する平均回数を削減できるべき乗演算装置を提供する。
【００１１】
【作用】べき乗剰余演算ＡB ｍｏｄＮまたはべき乗演算ＡB において、指数部Ｂがｍ個の０または１からなるビット列（ｂm-1 ，ｂm-2 ，ｂm-3 ，…ｂ1 ，ｂ0 ）で表現されているとする。この時、降順にビット列を、０，１、または−１の何れかからなるｂ′i に関するビット列（ｂ′m ，…ｂ′i ，…ｂ′1 ，ｂ′0 ）に変換する（方法は請求項７および８、説明は後述する）。
【００１２】こうすることにより、ｂ′2j+1とｂ′2jから成る２桁を単位に考えると、Ｂに関して非０の値が、従来は最大２回平均１回であったものが、最大１回平均３／４回となる。この結果、図４の従来法１では、ｂi ＝１でＸ×ＡｍｏｄＮを実行させたのに対し、本変換後では、ｂ′i ＝１のときＸ×ＡｍｏｄＮ、ｂ′1 ＝−１のときＸ×Ａ-1ｍｏｄＮを実行することにより、Ｂに関して非０の値の減少が、全体の乗算回数の減少として反映できる。なお、ここで使われるＡ-1ｍｏｄＮは初期状態において求め、記憶手段に蓄積する。
【００１３】
【実施例】図２に、本発明のべき乗演算装置の動作フローチャートを示す（請求項５に対応）。べき乗剰余演算ＡB ｍｏｄＮにおいて、予め、整数Ａの剰余逆元Ａ-1ｍｏｄＮを求め、その値を整数ＡＩと置く。変数Ｘは１に初期化し、変数ｉはＢのビット数ｍに初期化し（ステップＳ1 ）、以下の演算をｍ＋１回繰り返す。
【００１４】ステップＳ2 でｉ≧０のとき、ＸをＸ×ＸｍｏｄＮで更新し（ステップＳ3 ）、ステップＳ4 でｂ′i の１，０，−１を判定し、ｂi ′＝１の時、ＸをＸ×ＡｍｏｄＮで更新し（ステップＳ5 ）、ｂi ′＝−１の時、ＸをＸ×ＡＩｍｏｄＮで更新する（ステップＳ6 ）。なお、Ｘ＝１の時は自乗してもＸ×ＸｍｏｄＮ＝１なので、これを検出することにより剰余乗算を不要にできる。以下の議論では、この様な初期の剰余乗算はその回数に含めない。
【００１５】以上のべき乗剰余演算ＡB ｍｏｄＮの処理において、ＡＩ＝Ａ-1ｍｏｄＮをＡＩ＝１／Ａに、Ｘ×ＡｍｏｄＮをＸ×Ａに、Ｘ×ＡＩｍｏｄＮをＸ×ＡＩに置き換えることよりべき乗演算ＡB が実行できる（請求項６）。しかし、Ａは０以外の実数とされる。ｍ個の０または１からなるビット列（ｂm-1 ，ｂm-2 ，ｂm-3 ，…ｂ1 ，ｂ0）で表現されている指数部Ｂを、以下の様に、０、１、または−１からなるビット列（ｂ′m ，ｂ′m-1 ，ｂ′m-2 ，…ｂ′1 ，ｂ′0 ）を生成し、非０のビットの生起確率を削減する。ｊ（ｊは０または正の整数で、ｍが偶数ならｊ≦ｍ／２、ｍが奇数からｊ≦（ｍ−１）／２）に関して、降順にビット列を以下の様に変換する（請求項７）。
しかし、必ずしも上記のテーブルを参照しなくても、ｂ′i を必要の都度、ｂ′2j+1←（−１) b2j+1 ｛（１−ｂ2j+1）ｂ2jｂ2j-1＋ｂ2j+1（１−ｂ2j）（１−ｂ2j-1）｝，ｂ′2j←（−１）b2j+1 ｛（１−ｂ2j）ｂ2j-1＋ｂ2j（１−ｂ2j-1）｝
の様に関数に基づき変換して使用することも可能である（請求項８）。
【００１６】図１に、本発明のべき乗演算装置の実施例を示す。整数Ａ，ＡＩ，Ｂ，Ｎは装置外部より得られるとし、各々対応する記憶手段ＡＲ，ＡＩＲ，ＢＲ，ＮＲに蓄積される。演算途中結果の整数Ｘを記憶する記憶手段ＸＲ及びＸ，ＡＩ，Ａ，のいずれかを選択する選択手段ＳＥＬ及び剰余乗算手段ＳＭ等が設けられる（請求項１）。
【００１７】なお、コード変換手段ＣＣは、必要に応じてｂ′i を生成し出力する。制御手段ＣＮＴはｂ′i の値により、選択手段ＳＥＬの出力を切り替えることにより、Ｘ×ＹｍｏｄＮを実行する剰余乗算手段ＳＭにＸ×ＸｍｏｄＮ，Ｘ×ＡｍｏｄＮ，またはＸ×ＡＩｍｏｄＮの処理を実行させる。なお、繰り返し演算に先立ち予め全てのｂ′i を生成し、それでＢを更新することも可能である。
【００１８】図３に、本発明のべき乗演算装置の第２の実施例を示す。整数Ａ，Ｂ，Ｎは装置外部より得られるとし、各々対応する記憶手段ＡＲ，ＢＲ，ＮＲに蓄積される。また、繰り返し演算に先立ち、Ａ-1ｍｏｄＮが剰余逆元手段ＳＩにより生成され、整数ＡＩとして記憶手段ＡＩＲに蓄積される。その他は図１と同様である（請求項２）。
【００１９】以上の説明では、Ｘ×ＹｍｏｄＮを実行する剰余乗算手段ＳＭおよびＡ-1ｍｏｄＮを実行する剰余逆元手段ＳＩを備えることによりＡB ｍｏｄＮなるべき乗演算を実行する場合を示したが、Ｘ×ＹｍｏｄＮを実行する剰余乗算手段ＳＭをＸ×Ｙを実行する乗算手段に、Ａ-1ｍｏｄＮを実行する剰余逆元手段ＳＩを１／Ａを実行する除算手段に置き換え、Ａを０以外の実数とすることによりＡB なるべき乗演算を実行することが可能となる。なお、１／Ａを実行する除算手段がべき乗演算装置外部に存する場合と（請求項３）、内蔵する場合がある（請求項４）。
【００２０】
【発明の効果】以上の説明から明らかに、本発明によれば以下の様な効果が得られる。
（１）剰余乗算回数の比較に於て、 最大 平均 従来法１ ２（ｍ−１） ３（ｍ−１）／２ 従来法２ ３（ｍ−１）／２ ３（ｍ−１）／２以下の近傍 本発明 ３（ｍ−１）／２ １１（ｍ−１）／８であるから、平均的に約（ｍ−１）／８回剰余乗算回数を削減できる。従って、約８％の処理速度改善効果がある。
（２）指数部Ｂを基数４符号付コードへ変換するには、隣接３ビットを参照することで、テーブルまたは関数を用いて容易に実行できる。このため、従来法２に利用される装置とほぼ同じ構成のまま、僅かな処理を付け加えることで高速化を達成できる。
【図面の簡単な説明】
【図１】請求項１の発明の実施例を示すブロック図。
【図２】図１及び図３の動作フローチャート。
【図３】請求項２の発明の実施例を示すブロック図。
【図４】従来の第１のべき乗演算装置の動作フローチャート。
【図５】図４の従来の第１のべき乗演算装置のブロック図。
【図６】従来の第２のべき乗演算装置の動作フローチャート。
【図７】図６の従来の第２のべき乗演算装置のブロック図。
【０００１】
【産業上の利用分野】本発明は、０≦Ａ≦Ｎ−１なる関係がある複数ビットで表現される整数ＡとＮ、ならびに複数ビットで表現される整数Ｂにおける、ＡB ｍｏｄＮなるべき乗剰余演算を実行するとき有用な、べき乗演算装置に関する。さらに、本発明は、複数ビットで表現される０以外の実数Ａと整数Ｂにより、ＡB なるべき乗演算を実行するとき有用な、べき乗演算装置に関する。
【０００２】
【従来の技術】ＡB またはＡB ｍｏｄＮなどのべき乗演算は、基本的には乗算（積Ｘ×Ｙを求める）または剰余乗算（積Ｘ×ＹｍｏｄＮを求める）を繰り返して実行され、べきの指数部Ｂの桁数が大きくなると、単純な乗算または剰余乗算の繰り返し回数の増大が高速化を妨げる要因となる。
（従来法１）〔参考資料；森田：「暗号技術と高速算法」，情報処理，Ｖｏｌ．３４，Ｎｏ．３，ｐｐ．３４１，平成５年３月」
そこで、整数Ｂをｂi からなるビットに分解し、ＡB ｍｏｄＮのべき乗剰余演算を高速化する手法が提案された。手順は、図４に示す様に、ｂi に対応させて、Ｘ×ＸｍｏｄＮ，Ｘ×ＡｍｏｄＮを組み合わせ、剰余乗算の実行回数をＢの桁数程度に削減する。図５に示す様に、装置上では、整数Ａ，Ｂ，Ｎのデータが入力され、それぞれの記憶手段ＡＲ，ＢＲ，ＮＲに蓄積する。前記整数ＡまたはＸから選択し整数Ｙを出力する選択手段ＳＥＬと、演算途中結果の整数Ｘを蓄積する記憶手段ＸＲと、これらの記憶手段ＸＲ，ＮＲと選択手段ＳＥＬの各々の出力から剰余乗算手段ＳＭがＸ×ＹｍｏｄＮを実行し、得られた出力で記憶手段ＸＲのデータを更新する。選択手段ＳＥＬをはじめ各部を制御する制御手段ＣＮＴは、記憶手段ＢＲに蓄積されるｂi の値に従い、図４におけるＸ×ＸｍｏｄＮまたはＸ×ＡｍｏｄＮなどの実行の順序を制御する。
【０００３】ＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）などの暗号分野で用いられるべき乗剰余演算ＡB ｍｏｄＮは、０≦Ａ，Ｂ≦Ｎ−１の関係があり、Ｎは５１２ビット程度が採用されることが多い。この様な場合、Ｂも５１２ビットとするとＸ×ＸｍｏｄＮなる剰余乗算が５１１回、Ｘ×ＡｍｏｄＮなる剰余乗算に最大５１１回、平均２５５回が必要となる。従って、剰余乗算が最大１０２２回、平均７６６回必要になる。一般には、指数部Ｂのビット数をｍとするとき、最大２（ｍ−１）回の剰余乗算、平均３（ｍ−１）／２回の剰余乗算が必要となる。
【０００４】以上、べき乗剰余演算ＡB ｍｏｄＮを対象に説明したが、Ｂのビット数ｍと剰余乗算回数との関係は、べき乗演算ＡB における、Ｂのビット数ｍと乗算回数との関係にも同様のことが成り立つ。但し、べき乗演算ＡB は、法Ｎ内に途中結果が収まるべき乗剰余演算ＡB ｍｏｄＮと異なり、途中結果の桁数が増大するので、仮数部と指数部を分ける近似的な表現が取られることが多い。
（従来法２）〔参考資料；Ｂｒｉｃｋｅｌｌ，Ｅ．Ｆ．：“Ａ Ｆａｓｔ Ｍｏｄｕｌａｒ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｗｉｔｈＡｐｐｌｉｃａｔｉｏｎ ｔｏ Ｔｗｏ Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ，Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ′８２，ｐｐ．５１−６０，Ｐｌｅｎｕｍ（１９８３）〕
剰余乗算の回数を少しでも減らそうとして開発されたのが従来法２である。手順を図６に示す。そこで、Ｂをｂi からなるビット列対応に分解し、そのビットで１が立つ回数が半分を越えるとき、剰余逆元Ａ-1ｍｏｄＮを求め、繰り返しの演算では、半分より少ない筈のｂi ＝０がある時とほぼ同じ回数だけ、ＸとＡ-1ｍｏｄＮとの剰余乗算を実行する。逆に、そのビットで１が立つ回数が半分以下のときは従来法１と同じ処理を行う。
【０００５】図７に示す装置上で図６の処理を実行する場合、整数Ａ，Ｂ，Ｎが記憶手段Ａ（ＡＩ）Ｒ，ＢＲ，ＮＲに入力され、制御手段ＣＮＴにＢの“１”の値を持つビット数の大小を判定させ、“１”が多い場合、Ｘの記憶手段ＸＲに整数Ａを設定したあと、装置外から剰余逆元Ａ-1ｍｏｄＮ＝ＡＩを記憶手段Ａ（ＡＩ）Ｒに読み込み、図４と同様の手順で実行する。装置に剰余逆元手段がある場合、内部的に記憶手段Ａ（ＡＩ）ＲのデータをＡからＡＩ＝Ａ-1ｍｏｄＮに書き換える。
【０００６】Ｂが５１２ビットとすると、Ｘ×ＸｍｏｄＮなる剰余乗算が５１１回、Ｘ×ＡｍｏｄＮなる剰余乗算に最大２５５回が必要となる。従って、剰余乗算が最大７６６回が必要になる。一般には、指数部Ｂのビット数をｍとするとき、最大３（ｍ−１）／２回の剰余乗算が必要となる。同様に、べき乗演算ＡB を求める際、仮数部と指数部を分ける近似的な表現が必要であるが、上記剰余逆元Ａ-1ｍｏｄＮを１／Ａに置き換えることで、同様の乗算回数の削減が可能である。
【０００７】以上の様に、従来法では、べき乗剰余における剰余乗算の回数、べき乗における乗算の回数を削減するため、指数部をビット単位に行う手法、逆元（剰余逆元または逆数）を利用する手法が利用されて来た。
【０００８】
【発明が解決しようとする課題】従来法２は最大の乗算回数を削減する効果が有った。しかし、最大の乗算回数は、Ｂにおけるｍビットが（コインなげで表または裏を出すベルヌーイ試行と同様に）０又は１にランダムに分布している場合、１の生起確率は２項分布に従っているから、Ｘ×ＡｍｏｄＮなる剰余乗算の所要回数は最大ｍであっても、平均はｍ／２近傍にある。この為、従来法２は従来法１に比べ改良の効果が少なく、逆に逆元を演算するのに要する時間が付加されるので有効ではなかった。
【０００９】本発明の目的は、べき乗剰余演算ＡB ｍｏｄＮにおいて、剰余逆元Ａ-1ｍｏｄＮにより、剰余乗算の最大回数ばかりでなく、平均回数も削減を図り、高速なべき乗演算装置を提供することにある。また、同様に、べき乗演算ＡB においては、逆数１／Ａにより、乗算の最大回数ばかりでなく、平均回数も削減を図り、高速なべき乗演算装置を提供することにある。
【００１０】
【課題を解決するための手段】上記目的を達成するために、本発明は、べき乗剰余ＡB ｍｏｄＮまたはべき乗演算ＡB において、数Ａに対する逆元であるＡ-1ｍｏｄＮまたは１／Ａを利用するとともに、指数部Ｂを基数４、つまりバイナリ−コード２ビット分の符号付冗長表現にコード変換する機構により、乗算に要する平均回数を削減できるべき乗演算装置を提供する。
【００１１】
【作用】べき乗剰余演算ＡB ｍｏｄＮまたはべき乗演算ＡB において、指数部Ｂがｍ個の０または１からなるビット列（ｂm-1 ，ｂm-2 ，ｂm-3 ，…ｂ1 ，ｂ0 ）で表現されているとする。この時、降順にビット列を、０，１、または−１の何れかからなるｂ′i に関するビット列（ｂ′m ，…ｂ′i ，…ｂ′1 ，ｂ′0 ）に変換する（方法は請求項７および８、説明は後述する）。
【００１２】こうすることにより、ｂ′2j+1とｂ′2jから成る２桁を単位に考えると、Ｂに関して非０の値が、従来は最大２回平均１回であったものが、最大１回平均３／４回となる。この結果、図４の従来法１では、ｂi ＝１でＸ×ＡｍｏｄＮを実行させたのに対し、本変換後では、ｂ′i ＝１のときＸ×ＡｍｏｄＮ、ｂ′1 ＝−１のときＸ×Ａ-1ｍｏｄＮを実行することにより、Ｂに関して非０の値の減少が、全体の乗算回数の減少として反映できる。なお、ここで使われるＡ-1ｍｏｄＮは初期状態において求め、記憶手段に蓄積する。
【００１３】
【実施例】図２に、本発明のべき乗演算装置の動作フローチャートを示す（請求項５に対応）。べき乗剰余演算ＡB ｍｏｄＮにおいて、予め、整数Ａの剰余逆元Ａ-1ｍｏｄＮを求め、その値を整数ＡＩと置く。変数Ｘは１に初期化し、変数ｉはＢのビット数ｍに初期化し（ステップＳ1 ）、以下の演算をｍ＋１回繰り返す。
【００１４】ステップＳ2 でｉ≧０のとき、ＸをＸ×ＸｍｏｄＮで更新し（ステップＳ3 ）、ステップＳ4 でｂ′i の１，０，−１を判定し、ｂi ′＝１の時、ＸをＸ×ＡｍｏｄＮで更新し（ステップＳ5 ）、ｂi ′＝−１の時、ＸをＸ×ＡＩｍｏｄＮで更新する（ステップＳ6 ）。なお、Ｘ＝１の時は自乗してもＸ×ＸｍｏｄＮ＝１なので、これを検出することにより剰余乗算を不要にできる。以下の議論では、この様な初期の剰余乗算はその回数に含めない。
【００１５】以上のべき乗剰余演算ＡB ｍｏｄＮの処理において、ＡＩ＝Ａ-1ｍｏｄＮをＡＩ＝１／Ａに、Ｘ×ＡｍｏｄＮをＸ×Ａに、Ｘ×ＡＩｍｏｄＮをＸ×ＡＩに置き換えることよりべき乗演算ＡB が実行できる（請求項６）。しかし、Ａは０以外の実数とされる。ｍ個の０または１からなるビット列（ｂm-1 ，ｂm-2 ，ｂm-3 ，…ｂ1 ，ｂ0）で表現されている指数部Ｂを、以下の様に、０、１、または−１からなるビット列（ｂ′m ，ｂ′m-1 ，ｂ′m-2 ，…ｂ′1 ，ｂ′0 ）を生成し、非０のビットの生起確率を削減する。ｊ（ｊは０または正の整数で、ｍが偶数ならｊ≦ｍ／２、ｍが奇数からｊ≦（ｍ−１）／２）に関して、降順にビット列を以下の様に変換する（請求項７）。
しかし、必ずしも上記のテーブルを参照しなくても、ｂ′i を必要の都度、ｂ′2j+1←（−１) b2j+1 ｛（１−ｂ2j+1）ｂ2jｂ2j-1＋ｂ2j+1（１−ｂ2j）（１−ｂ2j-1）｝，ｂ′2j←（−１）b2j+1 ｛（１−ｂ2j）ｂ2j-1＋ｂ2j（１−ｂ2j-1）｝
の様に関数に基づき変換して使用することも可能である（請求項８）。
【００１６】図１に、本発明のべき乗演算装置の実施例を示す。整数Ａ，ＡＩ，Ｂ，Ｎは装置外部より得られるとし、各々対応する記憶手段ＡＲ，ＡＩＲ，ＢＲ，ＮＲに蓄積される。演算途中結果の整数Ｘを記憶する記憶手段ＸＲ及びＸ，ＡＩ，Ａ，のいずれかを選択する選択手段ＳＥＬ及び剰余乗算手段ＳＭ等が設けられる（請求項１）。
【００１７】なお、コード変換手段ＣＣは、必要に応じてｂ′i を生成し出力する。制御手段ＣＮＴはｂ′i の値により、選択手段ＳＥＬの出力を切り替えることにより、Ｘ×ＹｍｏｄＮを実行する剰余乗算手段ＳＭにＸ×ＸｍｏｄＮ，Ｘ×ＡｍｏｄＮ，またはＸ×ＡＩｍｏｄＮの処理を実行させる。なお、繰り返し演算に先立ち予め全てのｂ′i を生成し、それでＢを更新することも可能である。
【００１８】図３に、本発明のべき乗演算装置の第２の実施例を示す。整数Ａ，Ｂ，Ｎは装置外部より得られるとし、各々対応する記憶手段ＡＲ，ＢＲ，ＮＲに蓄積される。また、繰り返し演算に先立ち、Ａ-1ｍｏｄＮが剰余逆元手段ＳＩにより生成され、整数ＡＩとして記憶手段ＡＩＲに蓄積される。その他は図１と同様である（請求項２）。
【００１９】以上の説明では、Ｘ×ＹｍｏｄＮを実行する剰余乗算手段ＳＭおよびＡ-1ｍｏｄＮを実行する剰余逆元手段ＳＩを備えることによりＡB ｍｏｄＮなるべき乗演算を実行する場合を示したが、Ｘ×ＹｍｏｄＮを実行する剰余乗算手段ＳＭをＸ×Ｙを実行する乗算手段に、Ａ-1ｍｏｄＮを実行する剰余逆元手段ＳＩを１／Ａを実行する除算手段に置き換え、Ａを０以外の実数とすることによりＡB なるべき乗演算を実行することが可能となる。なお、１／Ａを実行する除算手段がべき乗演算装置外部に存する場合と（請求項３）、内蔵する場合がある（請求項４）。
【００２０】
【発明の効果】以上の説明から明らかに、本発明によれば以下の様な効果が得られる。
（１）剰余乗算回数の比較に於て、 最大 平均 従来法１ ２（ｍ−１） ３（ｍ−１）／２ 従来法２ ３（ｍ−１）／２ ３（ｍ−１）／２以下の近傍 本発明 ３（ｍ−１）／２ １１（ｍ−１）／８であるから、平均的に約（ｍ−１）／８回剰余乗算回数を削減できる。従って、約８％の処理速度改善効果がある。
（２）指数部Ｂを基数４符号付コードへ変換するには、隣接３ビットを参照することで、テーブルまたは関数を用いて容易に実行できる。このため、従来法２に利用される装置とほぼ同じ構成のまま、僅かな処理を付け加えることで高速化を達成できる。
【図面の簡単な説明】
【図１】請求項１の発明の実施例を示すブロック図。
【図２】図１及び図３の動作フローチャート。
【図３】請求項２の発明の実施例を示すブロック図。
【図４】従来の第１のべき乗演算装置の動作フローチャート。
【図５】図４の従来の第１のべき乗演算装置のブロック図。
【図６】従来の第２のべき乗演算装置の動作フローチャート。
【図７】図６の従来の第２のべき乗演算装置のブロック図。
【特許請求の範囲】
【請求項１】 ０≦Ａ≦Ｎ−１なる関係がある複数ビットで表現される整数ＡとＮ、ならびに複数ビットで表現される整数Ｂで、ＡB mod Ｎなるべき乗剰余演算を実行するべき乗演算装置において、前記整数Ａ，Ｂ，Ｎを表現する複数ビットの入力データをそれぞれ記憶する記憶手段ＡＲ，ＢＲ，ＮＲと、演算途中結果の整数Ｘを記憶する記憶手段ＸＲと、前記整数Ａの剰余逆元（整数）ＡＩ＝Ａ-1ｍｏｄＮを記憶する記憶手段ＡＩＲと、前記記憶手段ＡＲ，ＸＲ，ＡＩＲから入力される前記整数Ａ，Ｘ，ＡＩから一つの整数Ｙを選択する選択手段と、前記記憶手段ＸＲ，ＮＲから得られる整数Ｘ，Ｎ，ならびに前記選択手段が出力する整数Ｙを入力し、Ｘ×ＹｍｏｄＮなる剰余乗算を行い、その出力を前記記憶手段ＸＲに入力して、そのデータを更新させる剰余乗算手段と、を具備することを特徴とする、べき乗演算装置。
【請求項２】 請求項１記載のべき乗演算装置において、前記記憶手段ＡＲ，ＮＲから前記整数ＡとＮを入力して、Ａ-1ｍｏｄＮなる剰余逆元を求める剰余逆元手段を具備し、その出力を前記整数ＡＩとし、これを前記記憶手段ＡＩＲに記憶することを特徴とする。
【請求項３】 複数ビットで表現される０以外の実数Ａと整数Ｂで、ＡB なるべき乗演算を実行するべき乗演算装置において、前記数Ａ，Ｂを表現する複数ビットの入力データをそれぞれ記憶する記憶手段ＡＲ，ＢＲと、演算途中結果の数Ｘを記憶する記憶手段ＸＲと、前記実数Ａの逆数ＡＩ＝１／Ａを記憶する記憶手段ＡＩＲと、前記記憶手段ＡＲ，ＸＲ，ＡＩＲから入力される前記数Ａ，Ｘ，ＡＩから一つの数Ｙを選択する選択手段と、前記記憶手段ＸＲから得られる数Ｘならびに前記選択手段が出力する数Ｙを入力し、Ｘ×Ｙなる積を求め、その積を前記記憶手段ＸＲに入力して、そのデータを更新させる乗算手段と、を具備することを特徴とする、べき乗演算装置。
【請求項４】 請求項３記載のべき乗演算装置において、前記記憶手段ＡＲから前記数Ａを入力して、その逆数１／Ａを求める除算手段を具備し、その出力を前記数ＡＩとし、これを前記記憶手段ＡＩＲに記憶することを特徴とする。
【請求項５】 請求項１または２に記載のべき乗演算装置において、前記各手段を制御する制御手段を設け、各ビットｂ′i が０，１、または−１で表されるビット列（ｂ′m ，…ｂ′i，…ｂ′1 ，ｂ′0 ）で前記整数Ｂを表現するとき、前記制御手段は、最初に前記整数Ｘ及びビット番号ｉをＸ＝１，ｉ＝ｍに初期化させ、次に、前記制御手段は、前記選択手段を制御して前記Ｙとして前記Ｘを選択させ、その結果、前記剰余乗算手段はＸ×ＸｍｏｄＮなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、次に、前記制御手段は、ｂ′i ＝１の時、前記選択手段を制御して前記Ｙとして前記整数Ａを選択させ、その結果、前記剰余乗算手段はＸ×ＡｍｏｄＮなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、前記制御手段は、前記ｂ′i ＝−１の時、前記選択手段を制御して、前記Ｙとして前記ＡＩを選択させ、その結果、前記剰余乗算手段はＸ×ＡＩｍｏｄＮなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、次に、前記制御手段は、前記ｉをｉ−１で更新して同様の演算処理を繰返させ、ｉ＜０ならば演算処理を終了させ、その時の前記記憶手段ＸＲのデータを前記ＡB ｍｏｄＮなるべき乗剰余演算結果として出力させることを特徴とする。
【請求項６】 請求項３または４に記載のべき乗演算装置において、前記各手段を制御する制御手段を設け、各ビットｂ′i が０，１かまたは−１で表されるビット列（ｂ′m ，…ｂ′i，…ｂ′1 ，ｂ′0 ）で前記整数Ｂを表現するとき、前記制御手段は、最初に前記数Ｘ及びビット番号ｉをＸ＝１，ｉ＝ｍに初期化させ、次に、前記制御手段は、前記選択手段を制御して前記Ｙとして前記Ｘを選択させ、その結果、前記乗算手段はＸ×Ｘなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、次に、前記制御手段は、前記ｂ′i ＝１の時、前記選択手段を制御して前記Ｙとして前記数Ａを選択させ、その結果、前記乗算手段はＸ×Ａなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、前記制御手段は、前記ｂ′i ＝−１の時、前記選択手段を制御して、前記Ｙとして前記ＡＩを選択させ、その結果、前記乗算手段はＸ×ＡＩなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、次に、前記制御手段は、前記ｉをｉ−１で更新して同様の演算処理を繰返させ、ｉ＜０ならば演算処理を終了させ、その時の前記記憶手段ＸＲのデータを前記ＡB なるべき乗演算結果として出力させることを特徴とする。
【請求項７】 請求項５または６記載のべき乗演算装置において、（ｂm-1，…ｂ1 ，ｂ0 ）なるｍ個の０または１からなるビット列で整数Ｂが表現されている時、前記の隣接するビット列（ｂ2j+1，ｂ2j，ｂ2j-1）（ｊは０または正の整数で、ｍが偶数ならｊ≦ｍ／２，ｍが奇数ならｊ≦（ｍ−１）／２）から次の表に示す変換テーブルに従い、０，１、または−１からなるビット列（ｂ′2j+1，ｂ′2j）を大きいｉから降順に生成するコード変換手段が設けられていることを特徴とする。
【請求項８】 請求項５または６記載のべき乗演算装置において、（ｂm-1，…ｂ1 ，ｂ0 ）なるｍ個の０または１からなるビット列で整数Ｂが表現されている時、前記の隣接するビット列（ｂ2j+1，ｂ2j，ｂ2j-1）（ｊは０または正の整数で、ｍが偶数ならｊ≦ｍ／２，ｍが奇数ならｊ≦（ｍ−１）／２）から、ｂ′2j+1＝（−１) b2j+1 ｛（１−ｂ2j+1）ｂ2jｂ2j-1＋ｂ2j+1（１−ｂ2j）（１−ｂ2j-1）｝，ｂ′2j＝（−１）b2j+1 ｛（１−ｂ2j）ｂ2j-1＋ｂ2j（１−ｂ2j-1）｝
の変換を、前記ｂ′i を使用する時点で、その都度行うコード変換手段が設けられていることを特徴とする。
【請求項１】 ０≦Ａ≦Ｎ−１なる関係がある複数ビットで表現される整数ＡとＮ、ならびに複数ビットで表現される整数Ｂで、ＡB mod Ｎなるべき乗剰余演算を実行するべき乗演算装置において、前記整数Ａ，Ｂ，Ｎを表現する複数ビットの入力データをそれぞれ記憶する記憶手段ＡＲ，ＢＲ，ＮＲと、演算途中結果の整数Ｘを記憶する記憶手段ＸＲと、前記整数Ａの剰余逆元（整数）ＡＩ＝Ａ-1ｍｏｄＮを記憶する記憶手段ＡＩＲと、前記記憶手段ＡＲ，ＸＲ，ＡＩＲから入力される前記整数Ａ，Ｘ，ＡＩから一つの整数Ｙを選択する選択手段と、前記記憶手段ＸＲ，ＮＲから得られる整数Ｘ，Ｎ，ならびに前記選択手段が出力する整数Ｙを入力し、Ｘ×ＹｍｏｄＮなる剰余乗算を行い、その出力を前記記憶手段ＸＲに入力して、そのデータを更新させる剰余乗算手段と、を具備することを特徴とする、べき乗演算装置。
【請求項２】 請求項１記載のべき乗演算装置において、前記記憶手段ＡＲ，ＮＲから前記整数ＡとＮを入力して、Ａ-1ｍｏｄＮなる剰余逆元を求める剰余逆元手段を具備し、その出力を前記整数ＡＩとし、これを前記記憶手段ＡＩＲに記憶することを特徴とする。
【請求項３】 複数ビットで表現される０以外の実数Ａと整数Ｂで、ＡB なるべき乗演算を実行するべき乗演算装置において、前記数Ａ，Ｂを表現する複数ビットの入力データをそれぞれ記憶する記憶手段ＡＲ，ＢＲと、演算途中結果の数Ｘを記憶する記憶手段ＸＲと、前記実数Ａの逆数ＡＩ＝１／Ａを記憶する記憶手段ＡＩＲと、前記記憶手段ＡＲ，ＸＲ，ＡＩＲから入力される前記数Ａ，Ｘ，ＡＩから一つの数Ｙを選択する選択手段と、前記記憶手段ＸＲから得られる数Ｘならびに前記選択手段が出力する数Ｙを入力し、Ｘ×Ｙなる積を求め、その積を前記記憶手段ＸＲに入力して、そのデータを更新させる乗算手段と、を具備することを特徴とする、べき乗演算装置。
【請求項４】 請求項３記載のべき乗演算装置において、前記記憶手段ＡＲから前記数Ａを入力して、その逆数１／Ａを求める除算手段を具備し、その出力を前記数ＡＩとし、これを前記記憶手段ＡＩＲに記憶することを特徴とする。
【請求項５】 請求項１または２に記載のべき乗演算装置において、前記各手段を制御する制御手段を設け、各ビットｂ′i が０，１、または−１で表されるビット列（ｂ′m ，…ｂ′i，…ｂ′1 ，ｂ′0 ）で前記整数Ｂを表現するとき、前記制御手段は、最初に前記整数Ｘ及びビット番号ｉをＸ＝１，ｉ＝ｍに初期化させ、次に、前記制御手段は、前記選択手段を制御して前記Ｙとして前記Ｘを選択させ、その結果、前記剰余乗算手段はＸ×ＸｍｏｄＮなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、次に、前記制御手段は、ｂ′i ＝１の時、前記選択手段を制御して前記Ｙとして前記整数Ａを選択させ、その結果、前記剰余乗算手段はＸ×ＡｍｏｄＮなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、前記制御手段は、前記ｂ′i ＝−１の時、前記選択手段を制御して、前記Ｙとして前記ＡＩを選択させ、その結果、前記剰余乗算手段はＸ×ＡＩｍｏｄＮなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、次に、前記制御手段は、前記ｉをｉ−１で更新して同様の演算処理を繰返させ、ｉ＜０ならば演算処理を終了させ、その時の前記記憶手段ＸＲのデータを前記ＡB ｍｏｄＮなるべき乗剰余演算結果として出力させることを特徴とする。
【請求項６】 請求項３または４に記載のべき乗演算装置において、前記各手段を制御する制御手段を設け、各ビットｂ′i が０，１かまたは−１で表されるビット列（ｂ′m ，…ｂ′i，…ｂ′1 ，ｂ′0 ）で前記整数Ｂを表現するとき、前記制御手段は、最初に前記数Ｘ及びビット番号ｉをＸ＝１，ｉ＝ｍに初期化させ、次に、前記制御手段は、前記選択手段を制御して前記Ｙとして前記Ｘを選択させ、その結果、前記乗算手段はＸ×Ｘなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、次に、前記制御手段は、前記ｂ′i ＝１の時、前記選択手段を制御して前記Ｙとして前記数Ａを選択させ、その結果、前記乗算手段はＸ×Ａなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、前記制御手段は、前記ｂ′i ＝−１の時、前記選択手段を制御して、前記Ｙとして前記ＡＩを選択させ、その結果、前記乗算手段はＸ×ＡＩなる演算を実行し、その出力で前記記憶手段ＸＲのデータを更新し、次に、前記制御手段は、前記ｉをｉ−１で更新して同様の演算処理を繰返させ、ｉ＜０ならば演算処理を終了させ、その時の前記記憶手段ＸＲのデータを前記ＡB なるべき乗演算結果として出力させることを特徴とする。
【請求項７】 請求項５または６記載のべき乗演算装置において、（ｂm-1，…ｂ1 ，ｂ0 ）なるｍ個の０または１からなるビット列で整数Ｂが表現されている時、前記の隣接するビット列（ｂ2j+1，ｂ2j，ｂ2j-1）（ｊは０または正の整数で、ｍが偶数ならｊ≦ｍ／２，ｍが奇数ならｊ≦（ｍ−１）／２）から次の表に示す変換テーブルに従い、０，１、または−１からなるビット列（ｂ′2j+1，ｂ′2j）を大きいｉから降順に生成するコード変換手段が設けられていることを特徴とする。
【請求項８】 請求項５または６記載のべき乗演算装置において、（ｂm-1，…ｂ1 ，ｂ0 ）なるｍ個の０または１からなるビット列で整数Ｂが表現されている時、前記の隣接するビット列（ｂ2j+1，ｂ2j，ｂ2j-1）（ｊは０または正の整数で、ｍが偶数ならｊ≦ｍ／２，ｍが奇数ならｊ≦（ｍ−１）／２）から、ｂ′2j+1＝（−１) b2j+1 ｛（１−ｂ2j+1）ｂ2jｂ2j-1＋ｂ2j+1（１−ｂ2j）（１−ｂ2j-1）｝，ｂ′2j＝（−１）b2j+1 ｛（１−ｂ2j）ｂ2j-1＋ｂ2j（１−ｂ2j-1）｝
の変換を、前記ｂ′i を使用する時点で、その都度行うコード変換手段が設けられていることを特徴とする。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開平７−４９７６９
【公開日】平成７年（１９９５）２月２１日
【国際特許分類】
【出願番号】特願平５−１９３４９６
【出願日】平成５年（１９９３）８月４日
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【公開日】平成７年（１９９５）２月２１日
【国際特許分類】
【出願日】平成５年（１９９３）８月４日
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
[ Back to top ]