JPH0749769A - べき乗演算装置 - Google Patents
べき乗演算装置Info
- Publication number
- JPH0749769A JPH0749769A JP5193496A JP19349693A JPH0749769A JP H0749769 A JPH0749769 A JP H0749769A JP 5193496 A JP5193496 A JP 5193496A JP 19349693 A JP19349693 A JP 19349693A JP H0749769 A JPH0749769 A JP H0749769A
- Authority
- JP
- Japan
- Prior art keywords
- storage means
- integer
- exponentiation
- output
- data
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Abstract
(57)【要約】
【目的】 べき乗剰余演算ＡB ｍｏｄＮにおいて、剰余
逆元Ａ-1ｍｏｄＮにより、剰余乗算の最大回数ばかりで
なく、平均回数についても削減を図り、高速なべき乗演
算装置を提供する。 【構成】 ０≦Ａ≦Ｎ−１なる関係がある複数ビットで
表現される整数ＡとＮ、及び複数ビットで表現される整
数Ｂで、ＡB mod Ｎなるべき乗剰余演算を行う。Ａ，
Ｂ，Ｎは記憶手段ＡＲ，ＢＲ，ＮＲに記憶される。整数
Ａの剰余逆元ＡＩ＝Ａ-1ｍｏｄＮは記憶手段ＡＩＲに、
また演算途中結果の整数Ｘは記憶手段ＸＲにそれぞれ記
憶される。選択手段ＳＥＬはＡ，Ｘ，ＡＩから一つの整
数Ｙを選択する。剰余乗算手段ＳＭはＸ×ＹｍｏｄＮな
る剰余乗算を行い、その出力で記憶手段ＸＲを更新す
る。記憶手段ＢＲのデータをコード変換する手段ＣＣを
設け、非０のビットの生起確率を削減する。制御手段Ｃ
ＮＴはＢのコード変換したビットの０，１，−１の値に
応じて選択手段ＳＥＬを制御する。
逆元Ａ-1ｍｏｄＮにより、剰余乗算の最大回数ばかりで
なく、平均回数についても削減を図り、高速なべき乗演
算装置を提供する。 【構成】 ０≦Ａ≦Ｎ−１なる関係がある複数ビットで
表現される整数ＡとＮ、及び複数ビットで表現される整
数Ｂで、ＡB mod Ｎなるべき乗剰余演算を行う。Ａ，
Ｂ，Ｎは記憶手段ＡＲ，ＢＲ，ＮＲに記憶される。整数
Ａの剰余逆元ＡＩ＝Ａ-1ｍｏｄＮは記憶手段ＡＩＲに、
また演算途中結果の整数Ｘは記憶手段ＸＲにそれぞれ記
憶される。選択手段ＳＥＬはＡ，Ｘ，ＡＩから一つの整
数Ｙを選択する。剰余乗算手段ＳＭはＸ×ＹｍｏｄＮな
る剰余乗算を行い、その出力で記憶手段ＸＲを更新す
る。記憶手段ＢＲのデータをコード変換する手段ＣＣを
設け、非０のビットの生起確率を削減する。制御手段Ｃ
ＮＴはＢのコード変換したビットの０，１，−１の値に
応じて選択手段ＳＥＬを制御する。
Description
【０００１】
【産業上の利用分野】本発明は、０≦Ａ≦Ｎ−１なる関
係がある複数ビットで表現される整数ＡとＮ、ならびに
複数ビットで表現される整数Ｂにおける、ＡB ｍｏｄＮ
なるべき乗剰余演算を実行するとき有用な、べき乗演算
装置に関する。さらに、本発明は、複数ビットで表現さ
れる０以外の実数Ａと整数Ｂにより、ＡB なるべき乗演
算を実行するとき有用な、べき乗演算装置に関する。
係がある複数ビットで表現される整数ＡとＮ、ならびに
複数ビットで表現される整数Ｂにおける、ＡB ｍｏｄＮ
なるべき乗剰余演算を実行するとき有用な、べき乗演算
装置に関する。さらに、本発明は、複数ビットで表現さ
れる０以外の実数Ａと整数Ｂにより、ＡB なるべき乗演
算を実行するとき有用な、べき乗演算装置に関する。
【０００２】
【従来の技術】ＡB またはＡB ｍｏｄＮなどのべき乗演
算は、基本的には乗算（積Ｘ×Ｙを求める）または剰余
乗算（積Ｘ×ＹｍｏｄＮを求める）を繰り返して実行さ
れ、べきの指数部Ｂの桁数が大きくなると、単純な乗算
または剰余乗算の繰り返し回数の増大が高速化を妨げる
要因となる。 （従来法１）〔参考資料；森田：「暗号技術と高速算
法」，情報処理，Ｖｏｌ．３４，Ｎｏ．３，ｐｐ．３４
１，平成５年３月」 そこで、整数Ｂをｂi からなるビットに分解し、ＡB ｍ
ｏｄＮのべき乗剰余演算を高速化する手法が提案され
た。手順は、図４に示す様に、ｂi に対応させて、Ｘ×
ＸｍｏｄＮ，Ｘ×ＡｍｏｄＮを組み合わせ、剰余乗算の
実行回数をＢの桁数程度に削減する。図５に示す様に、
装置上では、整数Ａ，Ｂ，Ｎのデータが入力され、それ
ぞれの記憶手段ＡＲ，ＢＲ，ＮＲに蓄積する。前記整数
ＡまたはＸから選択し整数Ｙを出力する選択手段ＳＥＬ
と、演算途中結果の整数Ｘを蓄積する記憶手段ＸＲと、
これらの記憶手段ＸＲ，ＮＲと選択手段ＳＥＬの各々の
出力から剰余乗算手段ＳＭがＸ×ＹｍｏｄＮを実行し、
得られた出力で記憶手段ＸＲのデータを更新する。選択
手段ＳＥＬをはじめ各部を制御する制御手段ＣＮＴは、
記憶手段ＢＲに蓄積されるｂi の値に従い、図４におけ
るＸ×ＸｍｏｄＮまたはＸ×ＡｍｏｄＮなどの実行の順
序を制御する。
算は、基本的には乗算（積Ｘ×Ｙを求める）または剰余
乗算（積Ｘ×ＹｍｏｄＮを求める）を繰り返して実行さ
れ、べきの指数部Ｂの桁数が大きくなると、単純な乗算
または剰余乗算の繰り返し回数の増大が高速化を妨げる
要因となる。 （従来法１）〔参考資料；森田：「暗号技術と高速算
法」，情報処理，Ｖｏｌ．３４，Ｎｏ．３，ｐｐ．３４
１，平成５年３月」 そこで、整数Ｂをｂi からなるビットに分解し、ＡB ｍ
ｏｄＮのべき乗剰余演算を高速化する手法が提案され
た。手順は、図４に示す様に、ｂi に対応させて、Ｘ×
ＸｍｏｄＮ，Ｘ×ＡｍｏｄＮを組み合わせ、剰余乗算の
実行回数をＢの桁数程度に削減する。図５に示す様に、
装置上では、整数Ａ，Ｂ，Ｎのデータが入力され、それ
ぞれの記憶手段ＡＲ，ＢＲ，ＮＲに蓄積する。前記整数
ＡまたはＸから選択し整数Ｙを出力する選択手段ＳＥＬ
と、演算途中結果の整数Ｘを蓄積する記憶手段ＸＲと、
これらの記憶手段ＸＲ，ＮＲと選択手段ＳＥＬの各々の
出力から剰余乗算手段ＳＭがＸ×ＹｍｏｄＮを実行し、
得られた出力で記憶手段ＸＲのデータを更新する。選択
手段ＳＥＬをはじめ各部を制御する制御手段ＣＮＴは、
記憶手段ＢＲに蓄積されるｂi の値に従い、図４におけ
るＸ×ＸｍｏｄＮまたはＸ×ＡｍｏｄＮなどの実行の順
序を制御する。
【０００３】ＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａ
ｄｌｅｍａｎ）などの暗号分野で用いられるべき乗剰余
演算ＡB ｍｏｄＮは、０≦Ａ，Ｂ≦Ｎ−１の関係があ
り、Ｎは５１２ビット程度が採用されることが多い。こ
の様な場合、Ｂも５１２ビットとするとＸ×ＸｍｏｄＮ
なる剰余乗算が５１１回、Ｘ×ＡｍｏｄＮなる剰余乗算
に最大５１１回、平均２５５回が必要となる。従って、
剰余乗算が最大１０２２回、平均７６６回必要になる。
一般には、指数部Ｂのビット数をｍとするとき、最大２
（ｍ−１）回の剰余乗算、平均３（ｍ−１）／２回の剰
余乗算が必要となる。
ｄｌｅｍａｎ）などの暗号分野で用いられるべき乗剰余
演算ＡB ｍｏｄＮは、０≦Ａ，Ｂ≦Ｎ−１の関係があ
り、Ｎは５１２ビット程度が採用されることが多い。こ
の様な場合、Ｂも５１２ビットとするとＸ×ＸｍｏｄＮ
なる剰余乗算が５１１回、Ｘ×ＡｍｏｄＮなる剰余乗算
に最大５１１回、平均２５５回が必要となる。従って、
剰余乗算が最大１０２２回、平均７６６回必要になる。
一般には、指数部Ｂのビット数をｍとするとき、最大２
（ｍ−１）回の剰余乗算、平均３（ｍ−１）／２回の剰
余乗算が必要となる。
【０００４】以上、べき乗剰余演算ＡB ｍｏｄＮを対象
に説明したが、Ｂのビット数ｍと剰余乗算回数との関係
は、べき乗演算ＡB における、Ｂのビット数ｍと乗算回
数との関係にも同様のことが成り立つ。但し、べき乗演
算ＡB は、法Ｎ内に途中結果が収まるべき乗剰余演算Ａ
B ｍｏｄＮと異なり、途中結果の桁数が増大するので、
仮数部と指数部を分ける近似的な表現が取られることが
多い。 （従来法２）〔参考資料；Ｂｒｉｃｋｅｌｌ，Ｅ．
Ｆ．：“Ａ Ｆａｓｔ Ｍｏｄｕｌａｒ Ｍｕｌｔｉｐ
ｌｉｃａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｗｉｔｈＡｐ
ｐｌｉｃａｔｉｏｎ ｔｏ Ｔｗｏ Ｋｅｙ Ｃｒｙｐ
ｔｏｇｒａｐｈｙ，Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐ
ｔｏｌｏｇｙ−ＣＲＹＰＴＯ′８２，ｐｐ．５１−６
０，Ｐｌｅｎｕｍ（１９８３）〕 剰余乗算の回数を少しでも減らそうとして開発されたの
が従来法２である。手順を図６に示す。そこで、Ｂをｂ
i からなるビット列対応に分解し、そのビットで１が立
つ回数が半分を越えるとき、剰余逆元Ａ-1ｍｏｄＮを求
め、繰り返しの演算では、半分より少ない筈のｂi ＝０
がある時とほぼ同じ回数だけ、ＸとＡ-1ｍｏｄＮとの剰
余乗算を実行する。逆に、そのビットで１が立つ回数が
半分以下のときは従来法１と同じ処理を行う。
に説明したが、Ｂのビット数ｍと剰余乗算回数との関係
は、べき乗演算ＡB における、Ｂのビット数ｍと乗算回
数との関係にも同様のことが成り立つ。但し、べき乗演
算ＡB は、法Ｎ内に途中結果が収まるべき乗剰余演算Ａ
B ｍｏｄＮと異なり、途中結果の桁数が増大するので、
仮数部と指数部を分ける近似的な表現が取られることが
多い。 （従来法２）〔参考資料；Ｂｒｉｃｋｅｌｌ，Ｅ．
Ｆ．：“Ａ Ｆａｓｔ Ｍｏｄｕｌａｒ Ｍｕｌｔｉｐ
ｌｉｃａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｗｉｔｈＡｐ
ｐｌｉｃａｔｉｏｎ ｔｏ Ｔｗｏ Ｋｅｙ Ｃｒｙｐ
ｔｏｇｒａｐｈｙ，Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐ
ｔｏｌｏｇｙ−ＣＲＹＰＴＯ′８２，ｐｐ．５１−６
０，Ｐｌｅｎｕｍ（１９８３）〕 剰余乗算の回数を少しでも減らそうとして開発されたの
が従来法２である。手順を図６に示す。そこで、Ｂをｂ
i からなるビット列対応に分解し、そのビットで１が立
つ回数が半分を越えるとき、剰余逆元Ａ-1ｍｏｄＮを求
め、繰り返しの演算では、半分より少ない筈のｂi ＝０
がある時とほぼ同じ回数だけ、ＸとＡ-1ｍｏｄＮとの剰
余乗算を実行する。逆に、そのビットで１が立つ回数が
半分以下のときは従来法１と同じ処理を行う。
【０００５】図７に示す装置上で図６の処理を実行する
場合、整数Ａ，Ｂ，Ｎが記憶手段Ａ（ＡＩ）Ｒ，ＢＲ，
ＮＲに入力され、制御手段ＣＮＴにＢの“１”の値を持
つビット数の大小を判定させ、“１”が多い場合、Ｘの
記憶手段ＸＲに整数Ａを設定したあと、装置外から剰余
逆元Ａ-1ｍｏｄＮ＝ＡＩを記憶手段Ａ（ＡＩ）Ｒに読み
込み、図４と同様の手順で実行する。装置に剰余逆元手
段がある場合、内部的に記憶手段Ａ（ＡＩ）Ｒのデータ
をＡからＡＩ＝Ａ-1ｍｏｄＮに書き換える。
場合、整数Ａ，Ｂ，Ｎが記憶手段Ａ（ＡＩ）Ｒ，ＢＲ，
ＮＲに入力され、制御手段ＣＮＴにＢの“１”の値を持
つビット数の大小を判定させ、“１”が多い場合、Ｘの
記憶手段ＸＲに整数Ａを設定したあと、装置外から剰余
逆元Ａ-1ｍｏｄＮ＝ＡＩを記憶手段Ａ（ＡＩ）Ｒに読み
込み、図４と同様の手順で実行する。装置に剰余逆元手
段がある場合、内部的に記憶手段Ａ（ＡＩ）Ｒのデータ
をＡからＡＩ＝Ａ-1ｍｏｄＮに書き換える。
【０００６】Ｂが５１２ビットとすると、Ｘ×Ｘｍｏｄ
Ｎなる剰余乗算が５１１回、Ｘ×ＡｍｏｄＮなる剰余乗
算に最大２５５回が必要となる。従って、剰余乗算が最
大７６６回が必要になる。一般には、指数部Ｂのビット
数をｍとするとき、最大３（ｍ−１）／２回の剰余乗算
が必要となる。同様に、べき乗演算ＡB を求める際、仮
数部と指数部を分ける近似的な表現が必要であるが、上
記剰余逆元Ａ-1ｍｏｄＮを１／Ａに置き換えることで、
同様の乗算回数の削減が可能である。
Ｎなる剰余乗算が５１１回、Ｘ×ＡｍｏｄＮなる剰余乗
算に最大２５５回が必要となる。従って、剰余乗算が最
大７６６回が必要になる。一般には、指数部Ｂのビット
数をｍとするとき、最大３（ｍ−１）／２回の剰余乗算
が必要となる。同様に、べき乗演算ＡB を求める際、仮
数部と指数部を分ける近似的な表現が必要であるが、上
記剰余逆元Ａ-1ｍｏｄＮを１／Ａに置き換えることで、
同様の乗算回数の削減が可能である。
【０００７】以上の様に、従来法では、べき乗剰余にお
ける剰余乗算の回数、べき乗における乗算の回数を削減
するため、指数部をビット単位に行う手法、逆元（剰余
逆元または逆数）を利用する手法が利用されて来た。
ける剰余乗算の回数、べき乗における乗算の回数を削減
するため、指数部をビット単位に行う手法、逆元（剰余
逆元または逆数）を利用する手法が利用されて来た。
【０００８】
【発明が解決しようとする課題】従来法２は最大の乗算
回数を削減する効果が有った。しかし、最大の乗算回数
は、Ｂにおけるｍビットが（コインなげで表または裏を
出すベルヌーイ試行と同様に）０又は１にランダムに分
布している場合、１の生起確率は２項分布に従っている
から、Ｘ×ＡｍｏｄＮなる剰余乗算の所要回数は最大ｍ
であっても、平均はｍ／２近傍にある。この為、従来法
２は従来法１に比べ改良の効果が少なく、逆に逆元を演
算するのに要する時間が付加されるので有効ではなかっ
た。
回数を削減する効果が有った。しかし、最大の乗算回数
は、Ｂにおけるｍビットが（コインなげで表または裏を
出すベルヌーイ試行と同様に）０又は１にランダムに分
布している場合、１の生起確率は２項分布に従っている
から、Ｘ×ＡｍｏｄＮなる剰余乗算の所要回数は最大ｍ
であっても、平均はｍ／２近傍にある。この為、従来法
２は従来法１に比べ改良の効果が少なく、逆に逆元を演
算するのに要する時間が付加されるので有効ではなかっ
た。
【０００９】本発明の目的は、べき乗剰余演算ＡB ｍｏ
ｄＮにおいて、剰余逆元Ａ-1ｍｏｄＮにより、剰余乗算
の最大回数ばかりでなく、平均回数も削減を図り、高速
なべき乗演算装置を提供することにある。また、同様
に、べき乗演算ＡB においては、逆数１／Ａにより、乗
算の最大回数ばかりでなく、平均回数も削減を図り、高
速なべき乗演算装置を提供することにある。
ｄＮにおいて、剰余逆元Ａ-1ｍｏｄＮにより、剰余乗算
の最大回数ばかりでなく、平均回数も削減を図り、高速
なべき乗演算装置を提供することにある。また、同様
に、べき乗演算ＡB においては、逆数１／Ａにより、乗
算の最大回数ばかりでなく、平均回数も削減を図り、高
速なべき乗演算装置を提供することにある。
【００１０】
【課題を解決するための手段】上記目的を達成するため
に、本発明は、べき乗剰余ＡB ｍｏｄＮまたはべき乗演
算ＡB において、数Ａに対する逆元であるＡ-1ｍｏｄＮ
または１／Ａを利用するとともに、指数部Ｂを基数４、
つまりバイナリ−コード２ビット分の符号付冗長表現に
コード変換する機構により、乗算に要する平均回数を削
減できるべき乗演算装置を提供する。
に、本発明は、べき乗剰余ＡB ｍｏｄＮまたはべき乗演
算ＡB において、数Ａに対する逆元であるＡ-1ｍｏｄＮ
または１／Ａを利用するとともに、指数部Ｂを基数４、
つまりバイナリ−コード２ビット分の符号付冗長表現に
コード変換する機構により、乗算に要する平均回数を削
減できるべき乗演算装置を提供する。
【００１１】
【作用】べき乗剰余演算ＡB ｍｏｄＮまたはべき乗演算
ＡB において、指数部Ｂがｍ個の０または１からなるビ
ット列（ｂm-1 ，ｂm-2 ，ｂm-3 ，…ｂ1 ，ｂ0 ）で表
現されているとする。この時、降順にビット列を、０，
１、または−１の何れかからなるｂ′i に関するビット
列（ｂ′m ，…ｂ′i ，…ｂ′1 ，ｂ′0 ）に変換する
（方法は請求項７および８、説明は後述する）。
ＡB において、指数部Ｂがｍ個の０または１からなるビ
ット列（ｂm-1 ，ｂm-2 ，ｂm-3 ，…ｂ1 ，ｂ0 ）で表
現されているとする。この時、降順にビット列を、０，
１、または−１の何れかからなるｂ′i に関するビット
列（ｂ′m ，…ｂ′i ，…ｂ′1 ，ｂ′0 ）に変換する
（方法は請求項７および８、説明は後述する）。
【００１２】こうすることにより、ｂ′2j+1とｂ′2jか
ら成る２桁を単位に考えると、Ｂに関して非０の値が、
従来は最大２回平均１回であったものが、最大１回平均
３／４回となる。この結果、図４の従来法１では、ｂi
＝１でＸ×ＡｍｏｄＮを実行させたのに対し、本変換後
では、ｂ′i ＝１のときＸ×ＡｍｏｄＮ、ｂ′1 ＝−１
のときＸ×Ａ-1ｍｏｄＮを実行することにより、Ｂに関
して非０の値の減少が、全体の乗算回数の減少として反
映できる。なお、ここで使われるＡ-1ｍｏｄＮは初期状
態において求め、記憶手段に蓄積する。
ら成る２桁を単位に考えると、Ｂに関して非０の値が、
従来は最大２回平均１回であったものが、最大１回平均
３／４回となる。この結果、図４の従来法１では、ｂi
＝１でＸ×ＡｍｏｄＮを実行させたのに対し、本変換後
では、ｂ′i ＝１のときＸ×ＡｍｏｄＮ、ｂ′1 ＝−１
のときＸ×Ａ-1ｍｏｄＮを実行することにより、Ｂに関
して非０の値の減少が、全体の乗算回数の減少として反
映できる。なお、ここで使われるＡ-1ｍｏｄＮは初期状
態において求め、記憶手段に蓄積する。
【００１３】
【実施例】図２に、本発明のべき乗演算装置の動作フロ
ーチャートを示す（請求項５に対応）。べき乗剰余演算
ＡB ｍｏｄＮにおいて、予め、整数Ａの剰余逆元Ａ-1ｍ
ｏｄＮを求め、その値を整数ＡＩと置く。変数Ｘは１に
初期化し、変数ｉはＢのビット数ｍに初期化し（ステッ
プＳ1 ）、以下の演算をｍ＋１回繰り返す。
ーチャートを示す（請求項５に対応）。べき乗剰余演算
ＡB ｍｏｄＮにおいて、予め、整数Ａの剰余逆元Ａ-1ｍ
ｏｄＮを求め、その値を整数ＡＩと置く。変数Ｘは１に
初期化し、変数ｉはＢのビット数ｍに初期化し（ステッ
プＳ1 ）、以下の演算をｍ＋１回繰り返す。
【００１４】ステップＳ2 でｉ≧０のとき、ＸをＸ×Ｘ
ｍｏｄＮで更新し（ステップＳ3 ）、ステップＳ4 で
ｂ′i の１，０，−１を判定し、ｂi ′＝１の時、Ｘを
Ｘ×ＡｍｏｄＮで更新し（ステップＳ5 ）、ｂi ′＝−
１の時、ＸをＸ×ＡＩｍｏｄＮで更新する（ステップＳ
6 ）。なお、Ｘ＝１の時は自乗してもＸ×ＸｍｏｄＮ＝
１なので、これを検出することにより剰余乗算を不要に
できる。以下の議論では、この様な初期の剰余乗算はそ
の回数に含めない。
ｍｏｄＮで更新し（ステップＳ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）｝ の様に関数に基づき変換して使用することも可能である
（請求項８）。
において、ＡＩ＝Ａ-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 を生成し、それでＢを更新することも可能
である。
てｂ′i を生成し出力する。制御手段ＣＮＴはｂ′i の
値により、選択手段ＳＥＬの出力を切り替えることによ
り、Ｘ×ＹｍｏｄＮを実行する剰余乗算手段ＳＭにＸ×
ＸｍｏｄＮ，Ｘ×ＡｍｏｄＮ，またはＸ×ＡＩｍｏｄＮ
の処理を実行させる。なお、繰り返し演算に先立ち予め
全てのｂ′i を生成し、それでＢを更新することも可能
である。
【００１８】図３に、本発明のべき乗演算装置の第２の
実施例を示す。整数Ａ，Ｂ，Ｎは装置外部より得られる
とし、各々対応する記憶手段ＡＲ，ＢＲ，ＮＲに蓄積さ
れる。また、繰り返し演算に先立ち、Ａ-1ｍｏｄＮが剰
余逆元手段ＳＩにより生成され、整数ＡＩとして記憶手
段ＡＩＲに蓄積される。その他は図１と同様である（請
求項２）。
実施例を示す。整数Ａ，Ｂ，Ｎは装置外部より得られる
とし、各々対応する記憶手段ＡＲ，ＢＲ，ＮＲに蓄積さ
れる。また、繰り返し演算に先立ち、Ａ-1ｍｏｄＮが剰
余逆元手段ＳＩにより生成され、整数ＡＩとして記憶手
段ＡＩＲに蓄積される。その他は図１と同様である（請
求項２）。
【００１９】以上の説明では、Ｘ×ＹｍｏｄＮを実行す
る剰余乗算手段ＳＭおよびＡ-1ｍｏｄＮを実行する剰余
逆元手段ＳＩを備えることによりＡB ｍｏｄＮなるべき
乗演算を実行する場合を示したが、Ｘ×ＹｍｏｄＮを実
行する剰余乗算手段ＳＭをＸ×Ｙを実行する乗算手段
に、Ａ-1ｍｏｄＮを実行する剰余逆元手段ＳＩを１／Ａ
を実行する除算手段に置き換え、Ａを０以外の実数とす
ることによりＡB なるべき乗演算を実行することが可能
となる。なお、１／Ａを実行する除算手段がべき乗演算
装置外部に存する場合と（請求項３）、内蔵する場合が
ある（請求項４）。
る剰余乗算手段ＳＭおよびＡ-1ｍｏｄＮを実行する剰余
逆元手段ＳＩを備えることによりＡB ｍｏｄＮなるべき
乗演算を実行する場合を示したが、Ｘ×ＹｍｏｄＮを実
行する剰余乗算手段ＳＭをＸ×Ｙを実行する乗算手段
に、Ａ-1ｍｏｄＮを実行する剰余逆元手段ＳＩを１／Ａ
を実行する除算手段に置き換え、Ａを０以外の実数とす
ることによりＡB なるべき乗演算を実行することが可能
となる。なお、１／Ａを実行する除算手段がべき乗演算
装置外部に存する場合と（請求項３）、内蔵する場合が
ある（請求項４）。
【００２０】
【発明の効果】以上の説明から明らかに、本発明によれ
ば以下の様な効果が得られる。 （１）剰余乗算回数の比較に於て、 最大 平均 従来法１ ２（ｍ−１） ３（ｍ−１）／２ 従来法２ ３（ｍ−１）／２ ３（ｍ−１）／２以下の近傍 本発明 ３（ｍ−１）／２ １１（ｍ−１）／８ であるから、平均的に約（ｍ−１）／８回剰余乗算回数
を削減できる。従って、約８％の処理速度改善効果があ
る。 （２）指数部Ｂを基数４符号付コードへ変換するには、
隣接３ビットを参照することで、テーブルまたは関数を
用いて容易に実行できる。このため、従来法２に利用さ
れる装置とほぼ同じ構成のまま、僅かな処理を付け加え
ることで高速化を達成できる。
ば以下の様な効果が得られる。 （１）剰余乗算回数の比較に於て、 最大 平均 従来法１ ２（ｍ−１） ３（ｍ−１）／２ 従来法２ ３（ｍ−１）／２ ３（ｍ−１）／２以下の近傍 本発明 ３（ｍ−１）／２ １１（ｍ−１）／８ であるから、平均的に約（ｍ−１）／８回剰余乗算回数
を削減できる。従って、約８％の処理速度改善効果があ
る。 （２）指数部Ｂを基数４符号付コードへ変換するには、
隣接３ビットを参照することで、テーブルまたは関数を
用いて容易に実行できる。このため、従来法２に利用さ
れる装置とほぼ同じ構成のまま、僅かな処理を付け加え
ることで高速化を達成できる。
【図１】請求項１の発明の実施例を示すブロック図。
【図２】図１及び図３の動作フローチャート。
【図３】請求項２の発明の実施例を示すブロック図。
【図４】従来の第１のべき乗演算装置の動作フローチャ
ート。
ート。
【図５】図４の従来の第１のべき乗演算装置のブロック
図。
図。
【図６】従来の第２のべき乗演算装置の動作フローチャ
ート。
ート。
【図７】図６の従来の第２のべき乗演算装置のブロック
図。
図。
Claims (8)
- 【請求項１】 ０≦Ａ≦Ｎ−１なる関係がある複数ビッ
トで表現される整数ＡとＮ、ならびに複数ビットで表現
される整数Ｂで、Ａ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 を使用する時点で、その都度行う
コード変換手段が設けられていることを特徴とする。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP19349693A JP3332270B2 (ja) | 1993-08-04 | 1993-08-04 | べき乗演算装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP19349693A JP3332270B2 (ja) | 1993-08-04 | 1993-08-04 | べき乗演算装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0749769A true JPH0749769A (ja) | 1995-02-21 |
| JP3332270B2 JP3332270B2 (ja) | 2002-10-07 |
Family
ID=16309016
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP19349693A Expired - Fee Related JP3332270B2 (ja) | 1993-08-04 | 1993-08-04 | べき乗演算装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3332270B2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000330470A (ja) * | 1999-03-15 | 2000-11-30 | Matsushita Electric Ind Co Ltd | べき乗演算装置、べき乗剰余演算装置、楕円べき倍点演算装置、並びのそれらの方法、記録媒体 |
| US6567832B1 (en) | 1999-03-15 | 2003-05-20 | Matsushita Electric Industrial Co., Ltd. | Device, method, and storage medium for exponentiation and elliptic curve exponentiation |
| JP2009008993A (ja) * | 2007-06-29 | 2009-01-15 | Nec Electronics Corp | べき乗剰余演算器及びその制御方法 |
-
1993
- 1993-08-04 JP JP19349693A patent/JP3332270B2/ja not_active Expired - Fee Related
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000330470A (ja) * | 1999-03-15 | 2000-11-30 | Matsushita Electric Ind Co Ltd | べき乗演算装置、べき乗剰余演算装置、楕円べき倍点演算装置、並びのそれらの方法、記録媒体 |
| US6567832B1 (en) | 1999-03-15 | 2003-05-20 | Matsushita Electric Industrial Co., Ltd. | Device, method, and storage medium for exponentiation and elliptic curve exponentiation |
| JP2009008993A (ja) * | 2007-06-29 | 2009-01-15 | Nec Electronics Corp | べき乗剰余演算器及びその制御方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3332270B2 (ja) | 2002-10-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Hasan et al. | A modified Massey-Omura parallel multiplier for a class of finite fields | |
| US6920473B2 (en) | Method and apparatus for modular multiplying and calculating unit for modular multiplying | |
| JP3784156B2 (ja) | モジュラ掛け算方法 | |
| EP0917047B1 (en) | Apparatus for modular inversion for information security | |
| JP2009003925A (ja) | ランダム系列の反復周期の拡張 | |
| KR100591761B1 (ko) | 몽고메리 모듈러 곱셈기 및 캐리 저장 가산을 이용한몽고메리 모듈러 곱셈 방법 | |
| JP2004326112A (ja) | マルチプルモジュラス選択器、累算器、モンゴメリー掛け算器、マルチプルモジュラス発生方法、部分掛け発生方法、累算方法、掛け算方法、モジュラス選択器、およびブースレコーダ | |
| US6567832B1 (en) | Device, method, and storage medium for exponentiation and elliptic curve exponentiation | |
| JP3532860B2 (ja) | 剰余系表現を利用した演算装置及び方法及びプログラム | |
| CN114936350A (zh) | 一种基于gpu快速数论转换的全同态加密门自举方法 | |
| US6763366B2 (en) | Method for calculating arithmetic inverse over finite fields for use in cryptography | |
| US7831650B2 (en) | Method for modular multiplication | |
| US6662201B1 (en) | Modular arithmetic apparatus and method having high-speed base conversion function | |
| JP2004258141A (ja) | モンゴメリ乗算剰余の多倍長演算のための演算装置 | |
| US6480870B1 (en) | Random number generator using lehmer algorithm | |
| JP3332270B2 (ja) | べき乗演算装置 | |
| JP3953253B2 (ja) | 暗号生成装置、暗号生成プログラムを使用する電子機器、記憶媒体、暗号文復号装置 | |
| Walter | Still faster modular multiplication | |
| KR100670780B1 (ko) | 유한체 ＧＦ（２＾ｍ）에서의 하이브리드 곱셈 연산 장치및 연산 방법 | |
| US7068785B2 (en) | Table driven method for calculating arithmetic inverse for use in cryptography | |
| KR100257123B1 (ko) | 변형된 몽고메리 모듈라 곱셈을 적용한 고속 멱승 방법 | |
| JP2003084667A (ja) | 同一基底に対する複数の冪乗剰余演算を行う方法と装置並びにプログラム | |
| JP4541485B2 (ja) | べき乗演算装置、べき乗剰余演算装置、楕円べき倍点演算装置、並びのそれらの方法、記録媒体 | |
| JP2777265B2 (ja) | 高基数開平演算装置 | |
| JP3136709B2 (ja) | べき積演算装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |