(57)【要約】      （修正有）【課題】一般化Ｂａｔｃｈ法よりも短い時間で複数の指数に対するべき乗を演算可能とする。【解決手段】底ｂに対して、高々ビット長ｔのｎ個の自然数ｅ＿１，…，ｅ＿ｎを指数とするｎ個のべき乗を求める演算装置は、ｔ個のべき乗ｂ＾（２＾０），…，ｂ＾（２＾｛ｔ−１｝）を算出して保持し、ｎビットの正整数の２進表現を添字とする２＾ｎ−１個の変数Ｘ＿｛０…０１｝，…，Ｘ＿｛１１…１｝を１に初期化した後、指数ｅ＿ｊの２進表現のｉ番目のビットｅ＿｛ｊ，ｉ｝が全てのｊに対して非ゼロである場合にＸ＿｛ｅ＿｛１，ｉ｝…ｅ＿｛ｎ，ｉ｝｝とべき乗ｂ＾（２＾ｉ）の積をｎビットの正整数の２進表現を添字とする変数Ｘ＿｛ｅ＿｛１，ｉ｝…ｅ＿｛ｎ，ｉ｝｝に代入する処理をｉ＝０〜ｔ−１について行い、算出された変数Ｘ＿｛０…０１｝，…，Ｘ＿｛１１…１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせる処理をｊ＝１〜ｎについて行う。【選択図】図１
2015011208.tif 000002
【特許請求の範囲】
【請求項１】
底ｂに対して、高々ビット長ｔのｎ個の自然数ｅ＿１，ｅ＿２，…，ｅ＿ｎを指数とするｎ個のべき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を求めるべき乗演算装置であって、
前記ビット長ｔおよび前記底ｂを用いてｔ個のべき乗ｂ＾（２＾０），ｂ＾（２＾１），…，ｂ＾（２＾｛ｔ−１｝）を算出して保持する２べき乗演算部と、
ｎビットの正整数の２進表現を添字とする２＾ｎ−１個の変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝を１に初期化した後、指数ｅ＿ｊの２進表現をｅ＿｛ｊ，ｔ−１｝ｅ＿｛ｊ，ｔ−２｝…ｅ＿｛ｊ，１｝ｅ＿｛ｊ，０｝としたときに（ｊ＝１，…，ｎ）、（ｅ＿｛１，ｉ｝，ｅ＿｛２，ｉ｝，…，ｅ＿｛ｎ，ｉ｝）≠（０，０，…，０）である場合にＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝と前記べき乗ｂ＾（２＾ｉ）を掛け合わせたものをＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝に代入する処理をｉ＝０からｉ＝ｔ−１までについて行う部分演算部と、
前記部分演算部により算出された変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせることによって前記べき乗ｂ＾｛ｅ＿ｊ｝を算出する処理をｊ＝１からｊ＝ｎまでについて行う統合部と、を備える、べき乗演算装置。
【請求項２】
前記部分演算部は、前記変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のそれぞれに対する乗算を、複数の乗算器を用いて並列に実行する、請求項１に記載のべき乗演算装置。
【請求項３】
前記統合部は、前記べき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を算出する乗算を、複数の乗算器を用いて並列に実行する、請求項１または２に記載のべき乗演算装置。
【請求項４】
底ｂに対して、高々ビット長ｔのｎ個の自然数ｅ＿１，ｅ＿２，…，ｅ＿ｎを指数とするｎ個のべき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を求めるべき乗演算方法であって、
コンピュータが、前記ビット長ｔおよび前記底ｂを用いてｔ個のべき乗ｂ＾（２＾０），ｂ＾（２＾１），…，ｂ＾（２＾｛ｔ−１｝）を算出して記憶部に保持する工程と、
ｎビットの正整数の２進表現を添字とする２＾ｎ−１個の変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝を１に初期化する工程と、
指数ｅ＿ｊの２進表現をｅ＿｛ｊ，ｔ−１｝ｅ＿｛ｊ，ｔ−２｝…ｅ＿｛ｊ，１｝ｅ＿｛ｊ，０｝としたときに（ｊ＝１，…，ｎ）、（ｅ＿｛１，ｉ｝，ｅ＿｛２，ｉ｝，…，ｅ＿｛ｎ，ｉ｝）≠（０，０，…，０）である場合にＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝と前記べき乗ｂ＾（２＾ｉ）を掛け合わせたものをＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝に代入する処理をｉ＝０からｉ＝ｔ−１までについて行う工程と、
算出された変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせることによって前記べき乗ｂ＾｛ｅ＿ｊ｝を算出する処理をｊ＝１からｊ＝ｎまでについて行う工程と、を含む、べき乗演算方法。
【請求項５】
前記コンピュータは、前記変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のそれぞれに対する乗算を並列に実行する、請求項４に記載のべき乗演算方法。
【請求項６】
前記コンピュータは、前記べき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を算出する乗算を並列に実行する、請求項４または５に記載のべき乗演算方法。
【請求項７】
底ｂに対して、高々ビット長ｔのｎ個の自然数ｅ＿１，ｅ＿２，…，ｅ＿ｎを指数とするｎ個のべき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を求める処理をコンピュータに実行させるプログラムであって、
前記ビット長ｔおよび前記底ｂを用いてｔ個のべき乗ｂ＾（２＾０），ｂ＾（２＾１），…，ｂ＾（２＾｛ｔ−１｝）を算出して記憶部に保持する処理と、
ｎビットの正整数の２進表現を添字とする２＾ｎ−１個の変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝を１に初期化する処理と、
指数ｅ＿ｊの２進表現をｅ＿｛ｊ，ｔ−１｝ｅ＿｛ｊ，ｔ−２｝…ｅ＿｛ｊ，１｝ｅ＿｛ｊ，０｝としたときに（ｊ＝１，…，ｎ）、（ｅ＿｛１，ｉ｝，ｅ＿｛２，ｉ｝，…，ｅ＿｛ｎ，ｉ｝）≠（０，０，…，０）である場合にＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝と前記べき乗ｂ＾（２＾ｉ）を掛け合わせたものをＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝に代入する処理をｉ＝０からｉ＝ｔ−１までについて行う処理と、
算出された変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせることによって前記べき乗ｂ＾｛ｅ＿ｊ｝を算出する処理をｊ＝１からｊ＝ｎまでについて行う処理と、を前記コンピュータに実行させる、プログラム。
【請求項８】
前記変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のそれぞれに対する乗算を並列に実行する処理を、前記コンピュータに実行させる、請求項７に記載のプログラム。
【請求項９】
前記べき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を算出する乗算を並列に実行する処理を、前記コンピュータに実行させる、請求項７または８に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、べき乗演算装置、べき乗演算方法およびプログラムに関し、特に、固定された底に対して複数の指数についてべき乗を求めるべき乗演算装置、べき乗演算方法およびプログラムに関する。
【背景技術】
【０００２】
本書では、底ｂ、指数ｅについて、ｂのｅ乗としてべき乗ｂ＾ｅを計算する処理を「べき乗演算処理」という。べき乗演算処理は、Ｅｌｇａｍａｌ暗号などの公開鍵暗号における暗号化処理および復号処理で用いられる。
【０００３】
暗号化処理や復号処理においてべき乗演算処理が用いられる場合、単純な整数演算におけるべき乗ではなく、Ｅｌｇａｍａｌ暗号であれば、巡回群上の乗算となり、ＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｅｌｍａｎ）暗号であれば、ある合成数を法とする乗算となる。以下では、同一の群、同一の法に対してべき乗演算処理を行う方法について記述するため、群や法に関する表現を省略し、単に、底と指数を入力とする演算処理として記述する。
【０００４】
べき乗演算処理は、暗号化処理や復号処理の多くの部分を占める場合がある。したがって、べき乗演算処理を高速化する意義は大きい。
【０００５】
以下では、関連技術について説明する。非特許文献１には、“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”と呼ばれる計算方法が記載されている。また、非特許文献２には、Ｂａｔｃｈ法と呼ばれる計算方法が記載されている。さらに、特許文献１には、複数の指数に対するべき乗を計算する多重べき乗計算器が記載されている。
【０００６】
非特許文献２に記載された方法では、非特許文献１に記載された“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”が用いられる。そこで、“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”について説明した後、非特許文献２に記載されたＢａｔｃｈ法について説明する。以下では、べき乗演算ｂ＾ｅに関して、ｂを「底」といい、ｅを「指数」という。
【０００７】
“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”を用いると、指数のビット長の２倍の回数程度の乗算処理によって、べき乗演算を処理することが可能となる。本書では、特に指定しない場合、数の表記は１０進表記とみなす。また、１０進数ｅの２進表現は（ｅ＿｛ｔ−１｝ｅ＿｛ｔ−２｝…ｅ＿｛１｝ｅ＿｛０｝）＿２と表す。すなわち、Σを可算和として、ｅ＝Σ＿｛ｉ＝０｝＾｛ｔ−１｝ｅ＿｛ｉ｝＊２＾ｉとなる。例えば、１０進数１４は１４＝２＾３＋２＾２＋２＾１であるから、２進数表現は（１１１０）＿２となる。
【０００８】
［Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ］
以下に、“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”の入出力および処理を示す。
【０００９】
入力：ｂ，ｅ
出力：ｂ＾ｅ
【００１０】
処理：
Ｐ１：Ｘ＝１，Ｙ＝ｂ
Ｐ２：ｉ＝０からｉ＝ｔ−１まで順に以下のステップＰ２．１，Ｐ２．２を実行する。
Ｐ２．１：ｅ＿ｉ＝１である場合、Ｘ＝Ｘ＊Ｙとする。
Ｐ２．２：ｉ≠ｔ−１である場合、Ｙ＝Ｙ＊Ｙとする。
Ｐ３：Ｘを出力する。
【００１１】
以下、“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”によりべき乗演算処理が実行される仕組みと処理の効率について説明する。
【００１２】
まず、ステップＰ２．２の処理に注目すると、ステップＰ２．１の段階における変数Ｙにはｂ＾（２＾ｉ）が記憶されている。
【００１３】
記号Πを直積とすると、ステップＰ３の段階で、変数ＸにはΠ＿｛ｉ＝０｝＾｛ｔ−１｝ｂ＾（ｅ＿｛ｉ｝＊２＾ｉ）＝（Ａ）が記録されている。（Ａ）＝ｂ＾（（ｅ＿｛０｝＋ｅ＿｛１｝＊２＋ｅ＿｛２｝＊（２＾２）＋…＋ｅ＿｛ｔ−１｝＊（２＾｛ｔ−１｝））＿２）と書き換えることができる。したがって、目的の値であるべき乗ｂ＾ｅが変数Ｘに記憶されていることが分かる。ステップＰ２の各ループにおける乗算の数は高々２回であるから、“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”で実行される乗算の数は高々２ｔ回となる。
【００１４】
“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”では、底ｂと指数ｅが入力され、ｂ＾ｅの演算が行われる。しかし、Ｅｌｇａｍａｌ暗号やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号では、底ｂには固定の値が用いられるものの、指数ｅは暗号化処理ごとにランダムに定められる。さらに、複数のデータを暗号化する状況を考えると、固定された底ｂに対して、複数の指数ｅ＿１，…，ｅ＿ｎが入力される状況が考えられる。
【００１５】
このような状況において、べき乗ｂ＾（ｅ＿１），…，ｂ＾（ｅ＿ｎ）のそれぞれを“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”で求めた場合と比較して、これらのべき乗をより効率的に求める方法が非特許文献２に記載されている。本書では、非特許文献２に記載された方法を「Ｂａｔｃｈ法」という。
【００１６】
以下、Ｂａｔｃｈ法について説明する。入力される指数が２つの場合について説明した後、一般化した場合について説明する。
【００１７】
［Ｂａｔｃｈ法（入力される指数が２つの場合）］
まず、底ｂに対し、２つの指数ｅ＿１，ｅ＿２が入力され、２つのべき乗ｂ＾（ｅ＿１），ｂ＾（ｅ＿２）を計算する場合を例として、Ｂａｔｃｈ法の基本的なアイデアを説明し、その後、一般化した方法について説明する。なお、以下では、Ａ∧ＢはＡとＢのビット毎の論理積とし、Ａ∨Ｂはビット毎の論理和とし、¬はビット反転とする。
【００１８】
以下、入力される指数の数が２つの場合のＢａｔｃｈ法の入出力および処理を示す。
【００１９】
入力：ｂ，ｅ＿１，ｅ＿２
出力：ｂ＾（ｅ＿１），ｂ＾（ｅ＿２）
【００２０】
処理：
Ｑ１：指数ｅ＿１，ｅ＿２の２進表現の論理積ｅ＿１∧ｅ＿２を計算する。
Ｑ２：Ｘ＿｛１１｝＝ｂ＾（ｅ＿１∧ｅ＿２）を計算する。
Ｑ３：Ｘ＿｛１０｝＝ｂ＾（ｅ＿１∧¬（ｅ＿１∧ｅ＿２））を計算する。
Ｑ４：Ｘ＿｛０１｝＝ｂ＾（ｅ＿２∧¬（ｅ＿１∧ｅ＿２））を計算する。
Ｑ５：ｂ＾（ｅ＿１）＝Ｘ＿｛１１｝＊Ｘ＿｛１０｝を計算して出力する。
Ｑ６：ｂ＾（ｅ＿２）＝Ｘ＿｛１１｝＊Ｘ＿｛０１｝を計算して出力する。
【００２１】
（ｅ＿１∧ｅ＿２）∨（ｅ＿１∧¬（ｅ＿１∧ｅ＿２））＝ｅ＿１であり、（ｅ＿１∧ｅ＿２）∨（ｅ＿２∧¬（ｅ＿１∧ｅ＿２））＝ｅ＿２である。したがって、Ｘ＿｛１１｝＊Ｘ＿｛１０｝はｂ＾（ｅ＿１）に等しく、Ｘ＿｛１１｝＊Ｘ＿｛０１｝はｂ＾（ｅ＿２）に等しい。すなわち、上記の処理によって、所望のべき乗ｂ＾（ｅ＿１），ｂ＾（ｅ＿１）の値が得られる。
【００２２】
２つの指数ｅ＿１，ｅ＿２に対するべき乗を処理するために、３回のべき乗を処理しているため、上記の処理のままでは効率が悪い。しかし、ステップＱ２ないしＱ４におけるべき乗処理は“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”と組み合わせることで演算量を削減することができる。
【００２３】
この方法について、指数ｅ＿１，ｅ＿２を高々ｔビットの整数とし、指数ｅ＿ｊ（ｊ＝１，２）の２進表現を（ｅ＿｛ｊ，ｔ−１｝ｅ＿｛ｊ，ｔ−２｝…ｅ＿｛ｊ，１｝ｅ＿｛ｊ，０｝）＿２として説明する。
【００２４】
［ステップＱ２ないしＱ４の効率的な処理方法］
入力：ｂ，ｅ＿１，ｅ＿２
出力：ｂ＾（ｅ＿１∧ｅ＿２），ｂ＾（ｅ＿１∧¬（ｅ＿１∧ｅ＿２）），ｂ＾（ｅ＿２∧¬（ｅ＿１∧ｅ＿２））
【００２５】
処理：
Ｒ１：Ｗ＝ｂ，Ｘ＿｛１１｝＝１，Ｘ＿｛１０｝＝１，Ｘ＿｛０１｝＝１とする。
Ｒ２：ｉ＝０からｉ＝ｔ−１まで順に以下のステップＲ２．１，Ｒ２．２の処理を実行する。
Ｒ２．１：ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝≠００である場合、Ｘ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝｝＝Ｘ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝｝＊Ｗとする。
Ｒ２．２：ｉ≠ｔ−１である場合、Ｗ＝Ｗ＊Ｗとする。
Ｒ３：Ｘ＿｛１１｝をｂ＾（ｅ＿１∧ｅ＿２）、Ｘ＿｛１０｝をｂ＾（ｅ＿１∧¬（ｅ＿１∧ｅ＿２））、Ｘ＿｛０１｝をｂ＾（ｅ＿２∧¬（ｅ＿１∧ｅ＿２））として出力する。
【００２６】
ステップＲ２の各ループにおいて実行される乗算は、高々２回である。したがって、高々２ｔ回の乗算で所望の２値を得ることができる。以上の処理をＢａｔｃｈ法に導入すると、以下のような処理となる。
【００２７】
［Ｂａｔｃｈ法］
入力：ｂ，ｅ＿１，ｅ＿２，ｔ
出力：ｂ＾（ｅ＿１），ｂ＾（ｅ＿２）
【００２８】
処理：
Ｓ１：Ｗ＝ｂ，Ｘ＿｛１１｝＝１，Ｘ＿｛１０｝＝１，Ｘ＿｛０１｝＝１とする。
Ｓ２：ｉ＝０からｉ＝ｔ−１まで順番に以下のステップＳ２．１，Ｓ２．２の処理を実行する。
Ｓ２．１：ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝≠００である場合、Ｘ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝｝＝Ｘ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝｝＊Ｗ
Ｓ２．２：ｉ≠ｔ−１である場合、Ｗ＝Ｗ＊Ｗとする。
Ｓ３
Ｓ３．１：Ｘ＿｛１１｝＊Ｘ＿｛１０｝を計算して出力する。この値はｂ＾（ｅ＿１）に等しい。
Ｓ３．２：Ｘ＿｛１１｝＊Ｘ＿｛０１｝を計算して出力する。この値はｂ＾（ｅ＿２）に等しい。
【００２９】
ステップＳ２において高々（２ｔ−１）回の乗算処理、ステップＳ３において２回の乗算処理が行われ、結局、（２ｔ＋１）回の乗算で所望の２値を得ることができる。このとき、指数１個当たりのべき乗に要する乗算の回数は、ｔ回程度に効率化されている。
【００３０】
以下に、“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”を指数ｅ＿１，ｅ＿２のそれぞれに対して用いた場合と比較して、Ｂａｔｃｈ法によると、少ない処理で所望の値を求めることができる理由を説明する。
【００３１】
“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”はΠ＿｛Ｉ＝０｝＾｛ｔ−１｝ｂ＾（ｅ＿｛ｉ｝＊２＾ｉ）を計算するが、２つの指数ｅ＿１，ｅ＿２について独立に“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”を処理する場合、以下のような計算が行われる。
【００３２】
指数ｅ＿１について、ｂ＾（ｅ＿１）＝ｂ＾（ｅ＿｛１，０｝）＊ｂ＾（ｅ＿｛１，１｝＊２＾（１））＊ｂ＾（ｅ＿｛１，２｝＊２＾（２））＊．．．＊ｂ＾（ｅ＿｛１，ｔ−１｝＊２＾（ｔ−１））
指数ｅ＿２について、ｂ＾（ｅ＿２）＝ｂ＾（ｅ＿｛２，０｝）＊ｂ＾（ｅ＿｛２，１｝＊２＾（１））＊ｂ＾（ｅ＿｛２，２｝＊２＾（２））＊．．．＊ｂ＾（ｅ＿｛２，ｔ−１｝＊２＾（ｔ−１））
【００３３】
このとき、ｅ＿｛１，ｊ｝＝ｅ＿｛２，ｊ｝である桁に関する処理に注目すると、ｂ＾（ｅ＿１）とｂ＾（ｅ＿２）に関して、重複した演算を行っていることが分かる。
【００３４】
例えば、指数ｅ＿１＝（１１００１１）＿２，ｅ＿２＝（１０１０１１）＿２に対して、“Ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ  ｂｉｎａｒｙ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”を用いる場合、ステップＰ２．１の処理は以下の処理を行う。
ｂ＾（ｅ＿１）＝ｂ＾（１）＊ｂ＾（２）＊ｂ＾（２＾４）＊ｂ＾（２＾５）
ｂ＾（ｅ＿２）＝ｂ＾（１）＊ｂ＾（２）＊ｂ＾（２＾３）＊ｂ＾（２＾５）
ここで、ｂ＾（１）＊ｂ＾（２）＊ｂ＾（２＾５）は、共通の演算となる。したがって、これらをまとめて計算することで、乗算の演算回数を削減することができる。
【００３５】
また、ステップＰ２．２におけるべき乗ｂ＾（２＾ｉ）に関する処理も共通化されることで、さらに、乗算の処理回数が削減され、効率化されている。
【００３６】
２つの指数の２進表現において、ある１桁の値の組み合わせは００，１１，１０，０１の４通りである。００に関する処理は行う必要がないため、Ｂａｔｃｈ法では、途中計算結果を記憶する領域として、３つの変数Ｘ＿｛１１｝，Ｘ＿｛０１｝，Ｘ＿｛１０｝を用意する。ここで、変数Ｘ＿｛１１｝は指数ｅ＿１，ｅ＿２の両方が１である桁に関する演算結果を記憶する領域である。一方、変数Ｘ＿｛１０｝は指数ｅ＿１のみ１が立っているビットに関する演算結果を記憶する領域である。また、変数Ｘ＿｛０１｝は指数ｅ＿２のみ１が立っているビットに関する演算結果を記憶する領域である。これらの記憶領域を用いて、前述したように演算量を削減することができる。
【００３７】
２つの指数に対応する場合、計算途中の値を記憶させる領域として３つの変数Ｘ＿｛１１｝，Ｘ＿｛１０｝，Ｘ＿｛０１｝を用いた。ｎ個の指数に対応する場合、２＾ｎ−１個の領域を用いることで一般化することができる。これらをＸ＿（０…０１）＿２，…，Ｘ＿（１…１）＿２とする。なお、（ｆ＿１…ｆ＿ｎ）＿２はｎビットの２進表記であり、すべてが０である（０…０）＿２を除いた２＾ｎ−１パターンに対応させる。また、上述のＢａｔｃｈ法と同様に、各指数はｔビットの正数とする。さらに、ｎ個の指数ｅ＿ｊ（ｊ＝１，２，…，ｎ）の２進表現を、それぞれ、（ｅ＿｛ｊ，ｔ｝ｅ＿｛ｊ，ｔ−１｝…ｅ＿｛ｊ，１｝ｅ＿｛ｊ，０｝）＿２によって表す。
【００３８】
［一般化Ｂａｔｃｈ法］
以下に、一般化Ｂａｔｃｈ法の入出力および処理を示す。
【００３９】
入力：ｂ，ｅ＿１，…，ｅ＿ｎ
出力：ｂ＾（ｅ＿１），…，ｂ＾（ｅ＿ｎ）
【００４０】
処理：
Ｔ１：Ｘ＿（０…０１）＿２＝１，…，Ｘ＿（１…１）＿２＝１，Ｗ＝ｂとする。
Ｔ２：ｉ＝０からｉ＝ｔ−１まで順番に以下のステップＴ２．１，Ｔ２．２の処理を実行する。
Ｔ２．１：（ｅ＿｛１，ｉ｝…ｅ＿｛ｎ，ｉ｝）＿２＝（０…０）＿２である場合以外、Ｘ＿（ｅ＿｛１，ｉ｝…ｅ＿｛ｎ，ｉ｝）＿２＝Ｘ＿（ｅ＿｛１，ｉ｝…ｅ＿｛１，ｉ｝）＿２＊Ｗとする。
Ｔ２．２：ｉ≠ｔ−１であるとき、Ｗ＝Ｗ＊Ｗとする。
Ｔ３：ｉ＝１からｉ＝ｎまで順番に以下のステップＴ３．１の処理を実行する。
Ｔ３．１：ｆ＿１，…，ｆ＿ｎを１ビットの数として、ｆ＿ｉ＝１であるＸ＿（ｆ＿１…ｆ＿ｎ）を掛け合わせた値をｂ＾（ｅ＿ｉ）として出力する。
【先行技術文献】
【特許文献】
【００４１】
【特許文献１】特開平０７−０１３７４４号公報
【非特許文献】
【００４２】
【非特許文献１】Ａ．Ｊ．Ｍｅｎｅｚｅｓ，ｅｔ  ａｌ．，“Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ，”Ｃｈａｐｔｅｒ  １４，  ｓｕｂｓｅｃｔｉｏｎ  １４．７６，ｐ．６１４，ＣＲＣ  Ｐｒｅｓｓ  （１９９６）．
【非特許文献２】Ａｍｏｓ  Ｆｉａｔ，“Ｂａｔｃｈ  ＲＳＡ，”Ｊ．  Ｃｒｙｐｔｏｌｏｇｙ，１０（２），ｐ．７５−８８（１９９７）．
【発明の概要】
【発明が解決しようとする課題】
【００４３】
上記特許文献１および非特許文献１、２の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。
【００４４】
上記の一般化Ｂａｔｃｈ法によると、ステップＴ２での高々（２ｔ−１）回の乗算と、ステップＴ３でのｎ＊２＾（ｎ−１）回の乗算で所望のべき乗の値を得ることができる。したがって、１回あたりのべき乗に要する乗算の回数は（２ｔ−１）／ｎ＋２＾（ｎ−１）回程度となる。２＾（ｎ−１）の項がｎの指数関数になっているものの、ある程度小さいｎに対しては有効な手法である。
【００４５】
図４は、Ｂａｔｃｈ法ないし一般化Ｂａｔｃｈ法に基づく、べき乗演算装置１００の構成を一例として示すブロック図である。図４を参照して、べき乗演算装置１００について説明する。
【００４６】
図４を参照すると、べき乗演算装置１００は、底ｂ、複数の指数ｅ＿１，…，ｅ＿ｎ、および、指数長ｔを入力とし、演算結果としてｂ＾｛ｅ＿１｝，…，ｂ＾｛ｅ＿ｎ｝を出力する。また、べき乗演算装置１００は、２べき乗演算部１０１、部分演算部１０２、および、統合部１０３を備えている。
【００４７】
２べき乗演算部１０１は、２乗演算部１１１および２べき乗記憶部１２１を備えている。２べき乗記憶部１２１は、上述の一般化Ｂａｔｈ法の説明における変数Ｗを記憶する。
【００４８】
部分演算部１０２は、乗算部（乗算器）１１２、および、複数の部分演算結果記憶部１２２を備えている。部分演算結果記憶部１２２−１，…，１２２−｛２＾ｎ−１｝は、上述の一般化Ｂａｔｃｈ法における変数Ｘ＿（０…１）＿２，…，Ｘ＿（１…１）＿２を記憶する。
【００４９】
統合部１０３は、乗算部１１３を備えている。
【００５０】
図５は、図４に示したべき乗演算装置１００の動作を一例として示すフロー図である。図５を参照して、図４に示したべき乗演算装置１００の動作について説明する。
【００５１】
図５を参照すると、べき乗演算装置１００は、底ｂ、複数の指数ｅ＿１，…，ｅ＿ｎおよび指数長ｔを入力とする（ステップＡ１）。
【００５２】
次に、べき乗演算装置１００は、底ｂと指数長ｔを２べき乗演算部１０１に入力し、指数ｅ＿１，…，ｅ＿ｎを部分演算部１０２に入力する。また、２べき乗演算部１０１は、底ｂを２べき乗記憶部１２１に記録する。さらに、部分演算部１０２は、部分演算結果記憶部１２２−１，…，１２１−｛２＾ｎ−１｝が記憶する値を１に初期化する。この処理は、上述の一般化Ｂａｔｃｈ法におけるステップＴ１の処理に相当する（ステップＡ２）。
【００５３】
次に、以下のステップＡ３，Ａ４をｉ＝０からｉ＝ｔ−１に対して実行する。
【００５４】
２べき乗演算部１０１は、２べき乗記憶部１２１の記憶する値を２乗演算部１１１および部分演算部１０２に入力する。２乗演算部１１１は、入力された値を２乗した結果を２べき乗記憶部１２１に記録する。この処理は、上述の一般化Ｂａｔｃｈ法におけるステップＴ２．２の処理に相当する（ステップＡ３）。
【００５５】
部分演算部１０２は、入力された指数のｉ桁目を参照しながら、２乗演算部１１１から入力された値と部分演算結果記憶部１２２−１，…，１２２−｛２＾ｎ−１｝の記憶している値を乗算部１１２に入力し、その結果を部分演算結果記憶部１２２−１，…，１２２−｛２＾ｎ−１｝に記憶させる。この処理は、上述の一般化Ｂａｔｃｈ法におけるステップＴ２．１の処理に相当する（ステップＡ４）。
【００５６】
統合部１０３は、乗算部１１３を用いて、部分演算結果記憶部１２２の記憶する値を掛け合わせて、所望の結果を得る。この処理は、上述の一般化Ｂａｔｃｈ法におけるステップＴ３の処理に相当する（ステップＡ５）。
【００５７】
一般化Ｂａｔｃｈ法の問題点として、ステップＴ２のループが指数のビット長ｔに等しい回数となることが挙げられる。したがって、一般化Ｂａｔｃｈ法によると、ｔ回分の乗算処理に要する処理時間よりも短い時間でべき乗を処理することは不可能である。なお、特許文献１に記載された多重べき乗算器も、同様の処理を含み、一般化Ｂａｔｃｈ法と同様の問題を有する。
【００５８】
そこで、一般化Ｂａｔｃｈ法よりも短い時間で複数の指数に対するべき乗を演算可能とすることが要望される。本発明の目的は、かかる要望に寄与するべき乗演算装置、べき乗演算方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００５９】
本発明の第１の視点に係るべき乗演算装置は、
底ｂに対して、高々ビット長ｔのｎ個の自然数ｅ＿１，ｅ＿２，…，ｅ＿ｎを指数とするｎ個のべき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を求めるべき乗演算装置であって、
前記ビット長ｔおよび前記底ｂを用いてｔ個のべき乗ｂ＾（２＾０），ｂ＾（２＾１），…，ｂ＾（２＾｛ｔ−１｝）を算出して保持する２べき乗演算部と、
ｎビットの正整数の２進表現を添字とする２＾ｎ−１個の変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝を１に初期化した後、指数ｅ＿ｊの２進表現をｅ＿｛ｊ，ｔ−１｝ｅ＿｛ｊ，ｔ−２｝…ｅ＿｛ｊ，１｝ｅ＿｛ｊ，０｝としたときに（ｊ＝１，…，ｎ）、（ｅ＿｛１，ｉ｝，ｅ＿｛２，ｉ｝，…，ｅ＿｛ｎ，ｉ｝）≠（０，０，…，０）である場合にＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝と前記べき乗ｂ＾（２＾ｉ）を掛け合わせたものをＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝に代入する処理をｉ＝０からｉ＝ｔ−１までについて行う部分演算部と、
前記部分演算部により算出された変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせることによって前記べき乗ｂ＾｛ｅ＿ｊ｝を算出する処理をｊ＝１からｊ＝ｎまでについて行う統合部と、を備える。
【００６０】
本発明の第２の視点に係るべき乗演算方法は、
底ｂに対して、高々ビット長ｔのｎ個の自然数ｅ＿１，ｅ＿２，…，ｅ＿ｎを指数とするｎ個のべき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を求めるべき乗演算方法であって、
コンピュータが、前記ビット長ｔおよび前記底ｂを用いてｔ個のべき乗ｂ＾（２＾０），ｂ＾（２＾１），…，ｂ＾（２＾｛ｔ−１｝）を算出して記憶部に保持する工程と、
ｎビットの正整数の２進表現を添字とする２＾ｎ−１個の変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝を１に初期化する工程と、
指数ｅ＿ｊの２進表現をｅ＿｛ｊ，ｔ−１｝ｅ＿｛ｊ，ｔ−２｝…ｅ＿｛ｊ，１｝ｅ＿｛ｊ，０｝としたときに（ｊ＝１，…，ｎ）、（ｅ＿｛１，ｉ｝，ｅ＿｛２，ｉ｝，…，ｅ＿｛ｎ，ｉ｝）≠（０，０，…，０）である場合にＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝と前記べき乗ｂ＾（２＾ｉ）を掛け合わせたものをＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝に代入する処理をｉ＝０からｉ＝ｔ−１までについて行う工程と、
算出された変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせることによって前記べき乗ｂ＾｛ｅ＿ｊ｝を算出する処理をｊ＝１からｊ＝ｎまでについて行う工程と、を含む。
【００６１】
本発明の第３の視点に係るプログラムは、
底ｂに対して、高々ビット長ｔのｎ個の自然数ｅ＿１，ｅ＿２，…，ｅ＿ｎを指数とするｎ個のべき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝，…，ｂ＾｛ｅ＿ｎ｝を求める処理をコンピュータに実行させるプログラムであって、
前記ビット長ｔおよび前記底ｂを用いてｔ個のべき乗ｂ＾（２＾０），ｂ＾（２＾１），…，ｂ＾（２＾｛ｔ−１｝）を算出して記憶部に保持する処理と、
ｎビットの正整数の２進表現を添字とする２＾ｎ−１個の変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝を１に初期化する処理と、
指数ｅ＿ｊの２進表現をｅ＿｛ｊ，ｔ−１｝ｅ＿｛ｊ，ｔ−２｝…ｅ＿｛ｊ，１｝ｅ＿｛ｊ，０｝としたときに（ｊ＝１，…，ｎ）、（ｅ＿｛１，ｉ｝，ｅ＿｛２，ｉ｝，…，ｅ＿｛ｎ，ｉ｝）≠（０，０，…，０）である場合にＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝と前記べき乗ｂ＾（２＾ｉ）を掛け合わせたものをＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝に代入する処理をｉ＝０からｉ＝ｔ−１までについて行う処理と、
算出された変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせることによって前記べき乗ｂ＾｛ｅ＿ｊ｝を算出する処理をｊ＝１からｊ＝ｎまでについて行う処理と、を前記コンピュータに実行させる。
なお、プログラムは、非一時的なコンピュータ可読記録媒体（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ−ｒｅａｄａｂｌｅ  ｓｔｏｒａｇｅ  ｍｅｄｉｕｍ）に記録されたプログラム製品として提供することができる。
【発明の効果】
【００６２】
本発明に係るべき乗演算装置、べき乗演算方法およびプログラムによると、一般化Ｂａｔｃｈ法よりも短い時間で複数の指数に対するべき乗が演算可能となる。
【図面の簡単な説明】
【００６３】
【図１】第１の実施形態に係るべき乗演算装置の構成を一例として示すブロック図である。
【図２】第１の実施形態に係るべき乗演算装置の初期化処理の動作を一例として示すフロー図である。
【図３】第１の実施形態に係るべき乗演算装置のべき乗演算処理の動作を一例として示すフロー図である。
【図４】関連技術のべき乗演算方法の構成を一例として示すブロック図である。
【図５】関連技術のべき乗演算装置の動作を一例として示すフロー図である。
【発明を実施するための形態】
【００６４】
はじめに、一実施形態の概要について説明する。
【００６５】
本実施形態では、２つの指数を入力とするＢａｔｃｈ法と一般化Ｂａｔｃｈ法に対して以下の２つの変更を行う。ここでは、Ｂａｔｃｈ法に対する変更点と一般化Ｂａｔｃｈ法に対する変更点について説明する。
【００６６】
［変更点１］
Ｂａｔｃｈ法または一般化Ｂａｔｃｈ法を用いて高々ｔビットの複数の指数に対するべき乗を計算する場合、底ｂに関して以下のべき乗を計算する。
ｉ＝０，…，ｔ−１について、ｂ＾（２＾ｉ）
【００６７】
第１の変更点として、これらのべき乗ｂ＾（２＾ｉ）（ｉ＝０，…，ｔ−１）の値を前処理として求めておいて、参照可能なように記憶装置に保持しておく。これにより、同一のべき乗を重複して計算することを回避することが可能となる。
【００６８】
［変更点２］
第２の変更点は、Ｂａｔｃｈ法における変数Ｘ＿｛１１｝，Ｘ＿｛１０｝，Ｘ＿｛０１｝についての乗算処理、または、一般化Ｂａｔｃｈ法における変数Ｘ＿（０…０１）＿２，Ｘ＿（０…０１０）＿２，…，Ｘ＿（１１…１）＿２についての乗算処理に関する。本実施形態では、これらの乗算処理を、複数の乗算部（乗算器）を用いて並列処理する。
【００６９】
第２の変更点は、第１の変更点と組み合わせることで高い効果を発揮し、通常のＢａｔｃｈ法に適用しても効果が乏しい。Ｂａｔｃｈ法のステップＳ２の処理に着目すると、ｉ＝ｊであるとき、変数Ｗにはｂ＾（２＾（ｊ−１））が記憶されており、ステップＳ２．２において２乗され、変数Ｗはｂ＾（２＾（ｊ））を保持する。ステップＳ２．１では、そのときに記憶されている変数Ｗを片酢Ｘ＿｛１１｝，Ｘ＿｛１０｝，Ｘ＿｛０１｝のいずれかに乗じる。第２の変更点では、この乗算処理を並列化することを目的としているが、変数Ｗには１つの値しか記憶されていないため、並列化することできない。したがって、第１の変更点と第２の変更点を併せて用いることで、乗算処理の並列化が可能となり顕著な効果がもたらされる。なお、一般化Ｂａｔｃｈ法についても、同様のことが言える。
【００７０】
変更点１、２をＢａｔｃｈ法に適用した本実施形態の処理方法は、以下のとおりである。
【００７１】
前処理における入出力および処理は、次のとおりである。
【００７２】
入力：ｂ，ｔ
出力：Ｂ＿０＝ｂ，Ｂ＿１＝ｂ＾２，Ｂ＿２＝ｂ＾（２＾２），…，Ｂ＿｛ｔ−１｝＝ｂ＾（２＾（ｔ−１））
【００７３】
処理：
Ｕ１：Ｗ＝ｂとする。
Ｕ２：ｉ＝０からｉ＝ｔ−１まで順番に以下のステップＵ２．１，Ｕ２．２の処理を実行する。
Ｕ２．１：Ｂ＿ｉ＝Ｗとする。
Ｕ２．２：ｉ≠ｔ−１である場合、Ｗ＝Ｗ＊Ｗとする。
【００７４】
一方、べき乗演算処理における入出力および処理は、次のとおりである。
【００７５】
入力：ｅ＿１，ｅ＿２，…，ｅ＿ｎ，Ｂ＿０，…，Ｂ＿｛ｔ−１｝
出力：ｂ＾（ｅ＿１），ｂ＾（ｅ＿２），…，ｂ＾（ｅ＿ｎ）
【００７６】
処理：
Ｖ１：Ｘ＿｛０…０１｝＝１，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝＝１とする。
Ｖ２：ｉ＝０からｉ＝ｔ−１まで順番に以下のステップＶ２．１の処理を実行する。
Ｖ２．１．ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝≠０…０である場合、Ｘ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝＝Ｘ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝＊Ｂ＿ｉ
この処理は、複数個（例えば、（２＾ｎ−１）個）の乗算処理部を用いて並列に実行することができる。
Ｖ３：ステップＶ３．１の処理を実行する。
Ｖ３．１：ｊ＝１からｊ＝ｎまで、Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のうちの下付添字のビット列のｊ番目のビットが１であるものを掛け合わせてべき乗ｂ＾｛ｅ＿ｊ｝を求める。
この処理も、複数個（例えば、ｎ個）の乗算処理部を用いて並列に実行することができる。
【００７７】
本実施形態によると、一般化Ｂａｔｃｈ法よりも短い時間で複数の指数に対するべき乗が演算可能となる。なぜなら、べき乗ｂ＾（２＾ｉ）（ｉ＝０，…，ｔ−１）を重複して計算することを回避できるからである。また、ステップＶ２における乗算、および／または、ステップＶ３における乗算を、複数の乗算器を用いて並列に実行することで処理時間を削減できるからである。
【００７８】
＜実施形態１＞
次に、第１の実施形態に係るべき乗演算装置について、図面を参照して詳細に説明する。図１は、本実施形態に係るべき乗演算装置２００の構成を一例として示すブロック図である。
【００７９】
図１を参照すると、べき乗演算装置２００は、底ｂと複数の指数ｅ＿１，…，ｅ＿ｎと指数長ｔを入力とし、べき乗ｂ＾｛ｅ＿１｝，…，ｂ＾｛ｅ＿ｎ｝を出力する。
【００８０】
べき乗演算装置２００は、２べき乗演算部２０１、部分演算部２０２、および、統合部２０３を備えている。
【００８１】
２べき乗演算部２０１は、２乗演算部２１１、および、２べき乗記憶部２２１−０−２２１−｛ｔ−１｝を備えている。２べき乗記憶部２２１−０−２２１−｛ｔ−１｝は、それぞれ、初期化処理の出力であるＢ＿０，…，Ｂ＿｛ｔ−１｝を記憶する。
【００８２】
部分演算部２０２は、部分演算結果記憶部２２２−１，…，２２２−（２＾ｎ−１）、および、乗算部２１２−１，…，２１２−（２＾ｎ−１）を備えている。部分結果記憶部２２２−１，…，２２２−（２＾ｎ−１）は、べき乗演算処理における変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１…１｝を記憶する。
【００８３】
統合部２０３は、乗算部２１３−１，…，２１３−ｎを備えている。
【００８４】
べき乗演算装置２００は、底ｂと、指数長ｔを２べき乗演算部２０１に入力し、指数ｅ＿１，…，ｅ＿ｎを部分演算部２０２に入力し、統合部２０３の出力を出力する。
【００８５】
図２は、図１に示した本実施形態のべき乗演算装置２００の初期化処理の動作を一例として示すフロー図である。
【００８６】
べき乗演算装置２００は、底ｂと指数長ｔを受け付ける（ステップＢ１）。
【００８７】
べき乗演算装置２００は、底ｂと指数長ｔを２べき乗演算部２０１に入力する。２べき乗演算部２０１は、Ｂ＝ｂを２べき乗記憶部２２１−０に記録する（ステップＢ２）。
【００８８】
次に、２べき乗演算部２０１は、以下のステップをｉ＝０からｉ＝ｔ−２に対して実行する。すなわち、２べき乗演算部２０１は、２べき乗記憶部２２１−ｉの記憶する値を２乗演算部２１１に入力して２乗して、得られた結果を２べき乗記憶部２２１−（ｉ＋１）に記録する（ステップＢ３）。
【００８９】
図２に示した以上の処理は、上記一実施形態における前処理に相当する。
【００９０】
図３は、図１に示した本実施形態のべき乗演算装置２００のべき乗演算処理の動作を一例として示すフロー図である。
【００９１】
べき乗演算装置２００は、指数ｅ＿１，…，ｅ＿ｎを受け付ける（ステップＣ１）。べき乗演算装置２００は、指数ｅ＿１，…，ｅ＿ｎを部分演算部２０２に入力する。
【００９２】
部分演算部２０２は、部分演算結果記憶部２２２−１，…，２２２−｛２＾ｎ−１｝が記憶する変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝を１に初期化する（ステップＣ２）。この処理は、上記一実施形態のべき乗演算処理におけるステップＶ１に相当する。
【００９３】
部分演算部２０２は、以下のステップＣ３をｉ＝０からｉ＝ｔ−１に対して実行する。乗算部２１２−ｊは、入力された指数ｅ＿１，…，ｅ＿ｎのｉ桁目を参照しながら、２べき乗記憶部２２１−ｉが保持する値ｂ＾（２＾ｉ）と、部分演算結果記憶部２２２−ｊが保持する値を乗算した結果を部分演算結果記憶部２２２−ｊに記録する（ステップＣ３）。この処理は、上記一実施形態のべき乗演算処理におけるステップＶ２に相当する。
【００９４】
具体的には、部分演算部２０２は、（ｅ＿｛１，ｉ｝，ｅ＿｛２，ｉ｝，…，ｅ＿｛ｎ，ｉ｝）≠（０，０，…，０）である場合にＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝とべき乗ｂ＾（２＾ｉ）を掛け合わせたものをＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝…ｅ＿｛ｎ，ｉ｝｝に代入する処理をｉ＝０からｉ＝ｔ−１までについて行う。ここで、部分演算部２０２は、変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のそれぞれに対する乗算を、複数の乗算部２１２−１，…，２１２−｛２＾ｎ−１｝を用いて並列に実行してもよい。なお、本実施形態における乗算部２１２の個数（（２＾ｎ−１）個）は例示に過ぎず、かかる個数に限定されない。
【００９５】
統合部２０３は、乗算部２１３−１，…，２１３−ｎを用いて、部分演算結果記憶部２２２の記憶する値を掛け合わせて、所望の結果を得る（ステップＣ４）。この処理は、上記一実施形態のべき乗演算処理におけるステップＶ３に相当する。
【００９６】
具体的には、乗算部２１３−ｊは、部分演算部２０２により算出された変数Ｘ＿｛０…０１｝，Ｘ＿｛０…０１０｝，…，Ｘ＿｛１１…１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせることによってべき乗ｂ＾｛ｅ＿ｊ｝を算出する。ここで、統合部２０３は、べき乗ｂ＾｛ｅ＿ｊ｝を算出する処理を、複数の乗算部２１３−１，…，２１３−ｎを用いて並列に実行してもよい。なお、本実施形態における乗算部２１２の個数（ｎ個）は例示に過ぎず、かかる個数に限定されない。
【００９７】
べき乗演算を伴う暗号化処理または復号処理において、本実施形態に係るべき乗演算装置２００を適用することにより、暗号文または平文を生成するまでに要する処理時間を削減することが可能となる。なぜなら、本実施形態によると、べき乗ｂ＾（２＾ｉ）（ｉ＝０，…，ｔ−１）を重複して計算することを回避するとともに、複数の乗算器を用いて乗算を並列に実行することで、一般化Ｂａｔｃｈ法よりも短い時間で複数の指数に対するべき乗を求めることができるからである。
【００９８】
＜実施例＞
以下、実施例に基づいて、第１の実施形態に係るべき乗演算装置２００（図１）の具体的な動作について説明する。
【００９９】
ここでは、一例として、指数長ｔ＝６の２つの指数ｅ＿１＝（１１００１１）＿２，ｅ＿２＝（１０１０１１）＿２に対して、底ｂに対する２つのべき乗ｂ＾｛ｅ＿１｝，ｂ＾｛ｅ＿２｝を求める場合を考える。
【０１００】
２べき乗演算部２０１は、底ｂおよび指数長ｔ（＝６）を受け付けて、６個のべき乗ｂ＾（２＾０），ｂ＾（２＾１），…，ｂ＾（２＾５）、すなわち、ｂ＾（０００００１）＿２，ｂ＾（００００１０）＿２，ｂ＾（０００１００）＿２，ｂ＾（００１０００）＿２，ｂ＾（０１００００）＿２，ｂ＾（１０００００）＿２を算出して、それぞれ、２べき乗記憶部２２１−０，２２１−１，…，２２１−５に記録する（図２のステップＢ３）。
【０１０１】
部分演算結果記憶部２２２−１，２２２−２，２２２−３は、それぞれ、変数Ｘ＿｛０１｝，Ｘ＿｛１０｝，Ｘ｛１１｝を保持する。部分演算部２０２は、部分演算結果記憶部２２２−１，２２２−２，２２２−３が保持する変数Ｘ＿｛０１｝，Ｘ＿｛１０｝，Ｘ｛１１｝を１に初期値する（図３のステップＣ２）。
【０１０２】
次に、部分演算部２０２は、複数の乗算部２１２−１，２１２−２，２１２−３を用いて、（ｅ＿｛１，ｉ｝，ｅ＿｛２，ｉ｝）≠（０，０）である場合にＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝｝とべき乗ｂ＾（２＾ｉ）を掛け合わせたものをＸ＿｛ｅ＿｛１，ｉ｝ｅ＿｛２，ｉ｝｝に代入する処理をｉ＝０からｉ＝５までについて行う（図３のステップＣ３）。
【０１０３】
具体的には、乗算部２１２−１は、部分演算結果記憶部２２２−１が保持する変数Ｘ＿｛０１｝に対して、指数ｅ＿１のみが１である桁（５桁目）に関する乗算を行う。すなわち、乗算部２１２−１は、乗算１＊ｂ＾（０１００００）＿２を行う。一方、乗算部２１２−２は、部分演算結果記憶部２２２−２が保持する変数Ｘ＿｛１０｝に対して、指数ｅ＿２のみが１である桁（４桁目）に関する乗算を行う。すなわち、乗算部２１２−２は、乗算１＊ｂ＾（００１０００）＿２を行う。また、乗算部２１２−３は、部分演算結果記憶部２２２−３が保持する変数Ｘ＿｛１１｝に対して、指数ｅ＿１，ｅ＿２の双方が１である桁（１、２、６桁目）に関する乗算を行う。すなわち、乗算部２１２−３は、乗算１＊ｂ＾（０００００１）＿２＊ｂ＾（００００１０）＿２＊ｂ＾（１０００００）＿２を行う。
【０１０４】
３つの乗算部２１２−１，２１２−２，２１２−３による上記の乗算は、並列に実行することができる。本実施例では、２個の指数についてべき乗を求める場合を考えたが、一般に、ｎ個の指数ｅ＿１，…，ｅ＿ｎについてべき乗を求める場合、部分演算部２０２における乗算処理は２＾ｎ−１個の乗算部による並列化が可能である。
【０１０５】
次に、統合部２０３は、部分演算部２０２により算出された変数Ｘ＿｛０１｝，Ｘ＿｛１０｝，Ｘ＿｛１１｝のうちの添字のｊ番目のビットが１であるものを掛け合わせることによってべき乗ｂ＾｛ｅ＿ｊ｝を算出する処理をｊ＝１，２について行う（図３のステップＣ４）。
【０１０６】
具体的には、乗算部２１３−１は、Ｘ＿｛０１｝とＸ＿｛１１｝を掛け合わせてべき乗ｂ＾｛ｅ＿１｝を算出する。一方、乗算部２１３−２は、Ｘ＿｛１０｝とＸ＿｛１１｝を掛け合わせてべき乗ｂ＾｛ｅ＿２｝を算出する。
【０１０７】
統合部２０３における２つの乗算部２１３−１，２１２−２による乗算も、並列に実行することができる。本実施例では、２個の指数についてべき乗を求める場合を考えたが、一般に、ｎ個の指数ｅ＿１，…，ｅ＿ｎについてべき乗を求める場合、統合部２０３における乗算処理はｎ個の乗算部による並列化が可能である。
【０１０８】
なお、上記特許文献および非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０１０９】
１００，２００    べき乗演算装置
１０１，２０１    ２べき乗演算部
１０２，２０２    部分演算部
１０３，２０３    統合部
１１１，２１１    ２乗演算部
１１２，２１２−１，…，２１２−（２＾ｎ−１）    乗算部
１１３，２１３−１，…，２１３−ｎ    乗算部
１２１，２２１−０，…，２２１−｛ｔ−１｝    ２べき乗記憶部
１２２−１，…，１２２−（２＾ｎ−１），２２２−１，…，２２２−（２＾ｎ−１）    部分演算結果記憶部
【図１】
2015011208.tif 000003
【図２】
2015011208.tif 000004
【図３】
2015011208.tif 000005
【図４】
2015011208.tif 000006
【図５】
2015011208.tif 000007