(57)【要約】【課題】有限体や有限体の拡大体において行うべき乗計算の計算量を削減可能な計算時靴を提供する。【解決手段】ｐ進数展開部５１は、べき指数ｑをｐ進数展開する。ｒ進数展開部５２は、係数ｑｉをｒ進数展開する。第１計算部５４は、計算値記憶テーブル５３を参照して、各ｊについてＳｊを計算する。計算値記憶テーブル５３は、Ｓｊの値を計算するために用いるものであり、ｄ個のビットの組み合わせ全てについて、ｐの各べき乗との積の値を記憶したものである。第１計算部５４が全てのｊについてＳｊを計算すると、第２計算部５５は、各Ｓｊを用いて、ａのｑ乗を計算する。【選択図】        図１
2010078833.tif 000002
【特許請求の範囲】
【請求項１】
有限体の元ａ（ａ∈Ｆｐ＾ｍ、ｍは自然数、‘＾’はべき乗を表す）のべき乗を計算する計算装置であって、
べき指数ｑをｓ毎にｓ進数展開して
ｑ＝Σｉ＝０ｗ−１ｑｉ×ｓ＾ｉ  （０≦ｑｉ＜ｓ）
となる各係数ｑｉを求めるｓ進数展開部と、
各係数ｑｉをｒ進数展開して
ｑｉ＝Σｊ＝０ｈ−１ｑｉｊ×ｒ＾ｊ  （０＜ｒ＜ｓ，０≦ｑｉｊ＜ｒ）
となる各係数ｑｉｊを求めるｒ進数展開部と、
各係数ｑｉｊを用いて、べき乗を計算するべき乗計算部とを備える
ことを特徴とする計算装置。
【請求項２】
前記べき乗計算部は、
各ｊについて、
Ｓｊ＝Πｉ＝０ｗ−１ａ＾｛ｑｉｊ×ｓ＾ｉ｝
を計算する第１計算部と、
各ｊについて計算されたＳｊを用いて、べき指数ｑの元ａのべき乗として
ａ＾ｑ＝（（（（（Ｓ（ｈ−１））＾ｒ×Ｓ（ｈ−２））＾ｒ×Ｓ（ｈ−３））＾ｒ×・・・）＾ｒ×Ｓ１）＾ｒ×Ｓ０
を計算する第２計算部とを有する
ことを特徴とする請求項１に記載の計算装置。
【請求項３】
ｓ進数展開する際のｓは、有限体の元ａの標数ｐであり、
前記ｓ進数展開部は、べき指数ｑをｐ毎にｐ進数展開して
ｑ＝Σｉ＝０ｗ−１ｑｉ×ｐ＾ｉ  （０≦ｑｉ＜ｐ）
となる各係数ｑｉを求める
ことを特徴とする請求項１又は２記載の計算装置。
【請求項４】
前記べき乗計算部は、フロベニウス写像と各前記係数ｑｉｊを用いて、前記元のべき乗を計算する
ことを特徴とする請求項１乃至３のいずれか一項に記載の計算装置。
【請求項５】
前記有限体は２項式で拡大した拡大体であって、
前記べき乗計算部は、前記計算手法により、各前記係数ｑｉｊを用いて、前記拡大体の元のべき乗を計算する
ことを特徴とする請求項１乃至４のいずれか一項に記載の計算装置。
【請求項６】
前記有限体は円分多項式で拡大した拡大体であって、
前記べき乗計算部は、前記計算手法により、各前記係数ｑｉｊを用いて、前記拡大体の元のべき乗を計算する
ことを特徴とする請求項１乃至４のいずれか一項に記載の計算装置。
【請求項７】
前記ｒ進数展開部は、各係数ｑｉに対して、２進数展開を行う
ことを特徴とする請求項１乃至６のいずれか一項に記載の計算装置。
【請求項８】
同一のｊに対するｄ個の連続する係数ｑ０ｊ,ｑ１ｊ,・・・，ｑ(ｄ−１)ｊ（２≦ｄ≦ｗ）について取り得る値の組み合わせの全てについて各々計算された‘ａ＾（ｑ０ｊ＋ｑ１ｊ×ｓ＋・・・＋ｑ(ｄ−１)ｊ×ｓ＾｛ｄ−１｝）’の値を記憶する記憶手段を更に備え、
前記第１計算部は、前記記憶手段に記憶された値を用いて、各ｊについてＳｊを計算する
ことを特徴とする請求項２乃至７のいずれか一項に記載の計算装置。
【請求項９】
同一のｊに対するｄ個以下の連続する係数ｑ０ｊ,ｑ１ｊ,・・・，ｑ(ｕ−１)ｊ（２≦ｕ≦ｄ≦ｗ）について、ｑ０ｊとｑ（ｕ−１）ｊが０でない取り得るｕとｑｉｊの組み合わせの全てについて各々計算された‘ａ＾（ｑ０ｊ＋ｑ１ｊ×ｓ＋・・・＋ｑ(ｕ−１)ｊ×ｓ＾｛ｕ−１｝）’の値を記憶する記憶手段を更に備え、
前記第１計算部は、前記記憶手段に記憶された値を用いて、各ｊについてＳｊを計算する
ことを特徴とする請求項２乃至７のいずれか一項に記載の計算装置。
【請求項１０】
ｄ≧２に対して、０でない係数ｑｕｊと０でない係数ｑ（ｕ＋ｄ−１）ｊを含む同一のｊに対するｄ個の連続する係数列ｑｕｊ，・・・，ｑ（ｕ＋ｄ−１）ｊと各係数の値が同一のｄ個の連続する係数列ｑ（ｕ＋ｔ）（ｊ＋ｖ），・・・，ｑ（ｕ＋ｔ＋ｄ−１）（ｊ＋ｖ）が存在する場合には、
‘ａ＾（ｑｕｊ＋ｑ（ｕ＋１）ｊ×ｓ＋ｑ（ｕ＋２）ｊ×ｓ＾２＋・・・＋ｑ（ｕ＋ｄ−１）ｊ×ｓ＾｛ｄ−１｝’が前記記憶手段に予め記憶され、
前記第１計算部は、前記記憶手段に記憶された値を用いて各ｊについてＳｊを計算することを特徴とする請求項２乃至７のいずれか一項に記載の計算装置。
【請求項１１】
べき指数が同じであるべき乗を複数計算する場合、前記ｓ進数展開部は、先のべき乗の計算の際にｓ進数展開した結果の一部又は全部を後のべき乗の計算の際に利用して、べき指数ｑをｓ毎にｓ進数展開する
ことを特徴とする請求項１乃至１０のいずれか一項に記載の計算装置。
【請求項１２】
べき指数が同じであるべき乗を複数計算する場合、前記ｒ進数展開部は、先のべき乗の計算の際にｒ進数展開した結果の一部又は全部を後のべき乗の計算の際に利用して、各係数ｑｉをｒ進数展開する
ことを特徴とする請求項１乃至１１のいずれか一項に記載の計算装置。
【請求項１３】
元が同じであるべき乗を複数計算する場合、前記べき乗計算部は、先のべき乗の計算の際に得られた計算結果の一部又は全部を利用して、前記計算手法により、前記元のべき乗を計算する
ことを特徴とする請求項１乃至１２のいずれか一項に記載の計算装置。
【請求項１４】
前記ｒ進数展開部は、ｓ進数展開後の係数ｑｙ，ｑ（ｙ＋１）（０≦ｙ≦ｗ−２）について、係数ｑ（ｙ＋１）の値の一部のｓ倍を係数ｑｙに加えて、各係数ｑｙ，ｑ（ｙ＋１）をｒ進数展開する
ことを特徴とする請求項１乃至１３のいずれか一項に記載の計算装置。
【請求項１５】
ｓ進数展開部と、ｒ進数展開部と、べき乗計算部とを備え、有限体の元ａ（ａ∈Ｆｐ＾ｍ、ｍは自然数、‘＾’はべき乗を表す）のべき乗を計算する計算装置で実行される計算方法であって、
前記ｓ進数展開部が、べき指数ｑをｓ毎にｓ進数展開して
ｑ＝Σｉ＝０ｗ−１ｑｉ×ｓ＾ｉ  （０≦ｑｉ＜ｓ） 
となる各係数ｑｉを求め、
前記ｒ進数展開部が、各係数ｑｉをｒ進数展開して
ｑｉ＝Σｊ＝０ｈ−１ｑｉｊ×ｒ＾ｊ  （０＜ｒ＜ｓ，０≦ｑｉｊ＜ｒ）
となる各係数ｑｉｊを求め、
前記べき乗計算部は、各係数ｑｉｊを用いて、べき指数ｑの元のべき乗を計算する
ことを特徴とする計算方法。
【請求項１６】
請求項１５に記載の計算方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体の拡大体においてべき乗計算を行う計算装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来より、通信路を流れる情報を保護するために、暗号を用いる方法がある。暗号を用いる方法には、通信相手と事前に鍵を共有しておく共通鍵暗号方式がある。この方法では、鍵の共有や管理に大きな手間がかかる。一方、公開鍵暗号方式では、事前に鍵を共有することなしに安全な通信を実現できる。このため、ネットワーク・セキュリティの基盤技術として幅広く用いられている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキームやプロトコルが用いられるようになってきている。しかし、公開鍵暗号方式は共通鍵暗号方式と比較して、計算処理にかかるコストが大きく、計算処理より一層の高速化が求められている。公開鍵暗号方式内で使用される計算手法については様々な高速化が図られてきた。高速なべき乗計算手法に適用できる手法に循環窓法がある（特許文献１、非特許文献１参照）。
【０００３】
ここで循環窓法について説明する。循環窓法は楕円曲線Ｅ（ＧＦ（ｐ＾ｍ））上の点Ｐのスカラーｋ（∈Ｚ）倍を求める演算手法である。なお段落０００３〜００１０で用いる記号は特に断らない限り、特許文献１に合わせた記述とするため、この他の部分で用いている記号と意味は異なる。
【０００４】
［用語の説明］
φはフロベニウス写像であり、φ（ｘ，ｙ）＝（ｘ＾ｐ，ｙ＾ｐ）と表される。楕円曲線上の点Ｐに対して、φ＾ｉ（Ｐ）はフロベニウス写像を用いて高速に計算できる。
【０００５】
非負整数であるｂに対して、ベクトルｖｂは以下のようにＢ＋２個の要素で表され、各要素ｖｂ，ｈはｂ＝０のときｖｂ，０＝１で、ｂ≠０のときｖｂ，ｈ＝（［ｂ／３＾（ｈ−１）＋１］ｍｏｄ３）−１である。
ｖｂ＝（ｖｂ,０,ｖｂ，１，・・・，ｖｂ，Ｂ，ｖｂ，Ｂ＋１）
ここで、Ｂ＝［ｌｏｇ３ｂ］である。なお、［ａ］はａの小数点以下を切り捨てたものである。また、ｗＨ（ｖｂ）はベクトルｖｂの非ゼロの要素数を表すもので、
ｗＨ（ｖｂ）＝Σｈ＝０Ｂ＋１｜ｖｂ，ｈ｜
である。
【０００６】
Ｓｔｅｐ１：
［適当な長さｗのテーブル作成］
いくつかのｂを選択しておき、それぞれのｂに対して
Ｑｂ=Σｉ＝０Ｂ−１  ｖｂ，ｉφ＾ｉ（Ｐ）
を計算し、テーブルとして保持しておく。
【０００７】
Ｓｔｅｐ２：
［ｐ進ｄ進展開＋初期化］
ｋを以下のように展開し、ｃｉ，ｊ（∈｛−１，０，１｝）を求め、Ｒ＝О、ｊ＝ｎ’−１をセットする。ただしОはＥ（ＧＦ（ｐ＾ｍ））の単位元を表す。
ｋ＝Σｉ＝０ｎ’−１  Σｊ＝０ｍ’−１  ｃｉ，ｊ  ｄ＾ｊ  φ＾ｉ
【０００８】
Ｓｔｅｐ３：
［マッチング］
選択したｂの中で、ｗＨ（ｖｂ）が大きいものから順にｖｂの非ゼロの要素すべてに対しｃｉ＋ｈ，ｊ＝（−１）＾ｅ  ｖｂ，ｈとなるｂ，ｅ，ｉを探し、０≦ｈ≦Ｂ＋１の各ｈに対しｃｉ＋ｈ，ｊ＝ｃｉ＋ｈ，ｊ−（−１）＾ｅ  ｖｂ，ｈを実行し、Ｒ＝Ｒ＋（−１）＾ｅ  ｖｂ，ｈ  φ＾ｉとする処理を０≦ｉ＜ｍ’のｃｉ，ｊがすべて０になるまでｂを変えながら実行する。ただし、ｅ＝｛０，１｝である。
【０００９】
Ｓｔｅｐ４：
［Ａ＆Ｄ］
ｊ＝ｊ−１とし、Ｒ＝Ｒ×ｄを実行し、
ｊ＝０となるまで、Ｓｔｅｐ３とＳｔｅｐ４を繰り返す。
【００１０】
【特許文献１】特許第３６０４１２６号公報
【非特許文献１】巡回Window法の楕円曲線暗号への適用  青木和麻呂、小林鉄太郎、星野文学  ２０００年９月  ISEC2000-75  p.147〜p.154
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかし、特許文献１、非特許文献１に記載された方式は以下のような問題点があった。
（１）楕円曲線上の点のスカラー倍算を想定して考案されているため有限体のべき乗算にはそのまま適用できない
（２）テーブル作成のコストでは優位であるが、テーブルの数を削減することにより、繰り返し各ｊについて探索をする必要がある
（３）逆元を用いた演算は楕円曲線上の特別な点を用いると高速に計算できるということを利用しているため、一般のべき乗算には適用できない
（２）については拡大次数ｍが小さい間はテーブルの探索コストは小さくて済むが、拡大次数ｍが大きくなると、探索コストも無視できなくなる。（３）については、‘（１＋φ＋φ＾２＋・・・φ＾（ｍ−１））（Ｐ）＝О’（ｍは拡大次数）となる楕円曲線上の点Ｐを用いており、有限体上の任意の元に対して同様のことはいえない。このため、テーブルＱｂに‘−１’をかけた値を加減算することでスカラー倍算を実現する手法と同様のことは行えない。また、テーブルに負値を含めたものすべてを保持しても良いが、拡大次数ｍが大きくなると、それに適したテーブルサイズも大きくなるため、保持すべきテーブルの数が爆発的に（２＾Ｂから３＾Ｂ（Ｂはテーブルサイズ）へ）増加する。
【００１２】
本発明は、上記に鑑みてなされたものであって、有限体の拡大体において行うべき乗計算の計算量を削減可能な計算装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上述した課題を解決し、本発明は、有限体の元のべき乗を計算する計算装置であって、有限体の元ａ（ａ∈Ｆｐ＾ｍ、ｍは自然数、‘＾’はべき乗を表す）のべき乗を計算する計算装置であって、べき指数ｑをｓ毎にｓ進数展開して
ｑ＝Σｉ＝０ｗ−１ｑｉ×ｓ＾ｉ  （０≦ｑｉ＜ｓ）
となる各係数ｑｉを求めるｓ進数展開部と、各係数ｑｉをｒ進数展開して
ｑｉ＝Σｊ＝０ｈ−１ｑｉｊ×ｒ＾ｊ  （０＜ｒ＜ｓ，０≦ｑｉｊ＜ｒ）
となる各係数ｑｉｊを求めるｒ進数展開部と、各係数ｑｉｊを用いて、べき指数ｑの元のべき乗を計算するべき乗計算部とを備えることを特徴とする。
【００１４】
また、本発明は、ｓ進数展開部と、ｒ進数展開部と、べき乗計算部とを備え、有限体の元ａ（ａ∈Ｆｐ＾ｍ、ｍは自然数、‘＾’はべき乗を表す）のべき乗を計算する計算装置で実行される計算方法であって、前記ｓ進数展開部が、べき指数ｑをｓ毎にｓ進数展開して
ｑ＝Σｉ＝０ｗ−１ｑｉ×ｓ＾ｉ  （０≦ｑｉ＜ｓ）
となる各係数ｑｉを求め、前記ｒ進数展開部が、各係数ｑｉをｒ進数展開してｑｉ＝Σｊ＝０ｈ−１ｑｉｊ×ｒ＾ｊ  （０＜ｒ＜ｓ，−ｒ＜ｑｉｊ＜ｒ）
となる各係数ｑｉｊを求め、前記べき乗計算部は、各係数ｑｉｊを用いて、べき指数ｑの元のべき乗を計算することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、有限体の拡大体において行うべき乗計算の計算量を削減可能になる。
【発明を実施するための最良の形態】
【００１６】
以下に添付図面を参照して、この発明にかかる計算装置、方法及びプログラムの最良な実施の形態を詳細に説明する。
【００１７】
[第１の実施の形態]
（１）構成
まず、本実施の形態の計算装置のハードウェア構成について説明する。本実施の形態の計算装置は、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、計算装置には、情報を表示する表示装置と、ユーザの指示入力を受け付けるキーボードやマウス等の入力装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）とが有線又は無線により各々接続される。このようなハードウェア構成において、計算装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について説明する。図１は、計算装置の機能的構成を例示する図である。計算装置は、ｐ進数展開部５１と、ｒ進数展開部５２と、計算値記憶テーブル５３と、第１計算部５４と、第２計算部５５とを有する。これらの各部は、ＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。計算値記憶テーブル５３は、例えばＨＤＤなどの外部記憶装置に記憶される。
【００１８】
ここでまず、本実施の形態において利用する計算原理について説明する。有限体Fpの拡大体Fp＾ｍの元であり、以下の式１で表される元ｂのべき乗ｂ＾ｐは、フロベニウス写像を用いると、式２により表される。
ｂ＝ｂ０＋ｂ１×ｚ＋ｂ２×ｚ＾２＋ｂ３ｚ＾３＋・・・＋ｂ（ｍ−１）×ｚ＾｛ｍ−１｝・・・（１）
ｂ＾ｐ＝ｂ０＋ｂ１ｚ＾ｐ＋ｂ２ｚ＾｛２ｐ｝＋・・・＋ｂ（ｍ−１）ｚ＾｛ｐ（ｍ−１）｝・・・（２）
これを以下の式３で表される２項式の法多項式ｇｍで割ることにより、ｂ＾ｐを簡単に求めることができる。この場合はｚ＾ｍを順次‘−α’で置き換えていけばよい。
ｇｍ（ｚ）＝ｚ＾｛ｍ｝＋α・・・（３）
【００１９】
例えば、べき乗する元として代数的トーラスの元を考える。代数的トーラスの元T６（Fp＾m）はFp＾m＾６の部分群であるので、有限体の拡大体の元である。代数的トーラスの元の場合はFpの元の要素ｂｎはｐ乗してもｂｎにはならないので、ｂｎ＾ｐとしておく必要があることに注意が必要である。そして、このような元について、上述の手法を利用して高速にべき乗計算を行うことが可能となる。
【００２０】
ここで、計算装置は、有限体の拡大体の元をａ（ａ∈Ｆｐ＾ｍ）としてａのｑ乗を行うものとする説明する。ｐ進数展開部５１は、べき指数ｑをｐ進数展開する。べき指数ｑをｐ進数展開したものは、以下の式４により表される。
ｑ＝ｑ０＋ｑ１×ｐ＋ｑ２×ｐ＾２＋・・・＋ｑ（ｗ−１）×ｐ＾｛ｗ−１｝・・・（４）
尚、ｑｉ（０≦ｉ≦ｗ−１）は係数であり、‘ｑｉ＜ｐ’である。
【００２１】
ｒ進数展開部５２は、係数ｑｉをｒ進数展開する。‘ｒ＝２’のとき、係数ｑｉをｒ進数展開したものは、以下の式５により表される。
ｑｉ＝ｑｉ０＋ｑｉ１×２＋ｑｉ２×２＾２＋・・・＋ｑｉ（ｈ−１）×２＾｛ｈ−１｝・・・（５）
【００２２】
このとき、ｑｉｊ∈｛０，１｝（０≦ｉ≦ｗ−１，０≦ｊ≦ｈ−１）である。尚、ここでは簡単のため‘ｗ＝ｄ×ｎ’（ｗはｄの倍数である）とする。ｄについては後述の計算値記憶テーブル５３の説明において説明する。ｗがｄの倍数とならない場合は、‘ｑｗ＝０，ｑ（ｗ＋１）＝０，・・・’としてパディングすれば良い。
【００２３】
図２は、元ａのｑ乗であるａ＾ｑを視覚的に表現するために２次元の表形式で示した図である。同図においては、縦の列毎に、横の各行に示される２のべき乗の値を乗算した値が、係数ｑiを表している。一方、横の行毎に、縦の各列に示されるｐのべき乗の値を乗算した値をＳjとする。Ｓｊは以下の式６により表される。
Ｓｊ＝ａ＾｛ｑ０ｊ＋ｑ１ｊ×ｐ＋ｑ２ｊ×ｐ＾２＋・・・＋ｑ（ｗ−１）ｊ×ｐ＾｛ｗ−１｝｝・・・（６）
【００２４】
第１計算部５４は、計算値記憶テーブル５３を参照して、各ｊについてＳｊを計算する。計算値記憶テーブル５３は、Ｓｊの値を計算するために用いるものであり、‘ｒ＝２’であるときのｄ個のビットの組み合わせ（ｂ０、ｂ１、ｂ２、・・、ｂ（ｄ−１））全てについて、以下の式７により表されるＴ（ｋ）の値を記憶したものである。
Ｔ（ｋ）＝ａ＾｛ｂ０＋ｂ１×ｐ＋ｂ２×ｐ＾２＋ｂ３×ｐ＾３＋・・・＋ｂ（ｄ−１）×ｐ＾｛ｄ−１｝｝・・・（７）
【００２５】
尚、以降、ｄをwindow幅という。また、ｋ∈｛０，１｝＾ｄであり、ｋは、２進数表記でｄ個のビットの順序付き組み合わせを示すものとなる。ビットの順序付き組み合わせをビット列という。
【００２６】
Ｔ（ｋ）の値は予め計算（事前計算）されて計算値記憶テーブル５３に記憶される。Ｔ（ｋ）の事前計算においてａ＾ｐやａ＾｛ｐ＾２｝のべき乗計算を行う際には、フロベニウス写像を用いると容易に計算可能である。図３は、‘ｄ＝４’である場合の計算値記憶テーブル５３を視覚的に示した図である。同図においては、ｐ＾０〜ｐ＾３について、（ｂ０，ｂ１，ｂ２，ｂ３）の全ての組み合わせのそれぞれに対応してＴ（ｋ）が計算されていることが各々示されている。尚、この計算値記憶テーブル５３においては、ｐ＾０〜ｐ＾３についての組み合わせに対応したＴ（ｋ）の値しか記憶されていないが、ｐ＾４以降のｄ個のビットの組み合わせに対応する値については、Ｔ（ｋ）の値を用いて容易に計算することができる。例えば、ｐ＾４〜ｐ＾７についての組み合わせに対応する各値は、ｐ＾０〜ｐ＾３の組み合わせについての組み合わせに対応するＴ（ｋ）にｐ＾４を各々乗算することにより求められ、ｐ＾４はフロベニウス写像を用いると容易に計算が可能である。従って、全てのＳｊの計算にＴ（ｋ）を複数回適用することが可能であり、計算の高速化に大きく寄与する。
【００２７】
第１計算部５４は、このＴ(ｋ)の値を用い、各ｊについてＳｊを計算する。この結果、式６により表されるＳｊは、以下の式８により表される。
Ｓｊ＝Ｔ（ｑ（ｄ−１）ｊｑ（ｄ−２）ｊ・・・ｑ０ｊ）×Ｔ（ｑ（２ｄ−１）ｊｑ（２ｄ−２）ｊ・・・ｑｄｊ）＾｛ｐ＾ｄ｝×Ｔ（ｑ（３ｄ−１）ｊｑ（３ｄ−２）ｊ・・・ｑ（２ｄ）ｊ）＾｛ｐ＾（２ｄ）｝×・・・×Ｔ（ｑ（ｎｄ−１）ｊｑ（ｎｄ−２）ｊ・・・ｑ（（ｎ−１）ｄ）ｊ）＾｛ｐ＾｛ｄ（ｎ−１）｝｝・・・（８）
【００２８】
そして、第１計算部５４が全てのｊについてＳｊを計算すると、第２計算部５５は、各Ｓｊを用いて、以下の式９により、ａのｑ乗を計算する。
Ｓ＝ａ＾ｑ＝（（（（（Ｓ（ｈ−１））＾２×Ｓ（ｈ−２））＾２×Ｓ（ｈ−３））＾２×・・・）＾２×Ｓ１）＾２×Ｓ０・・・（９）
【００２９】
（２）動作
次に、本実施の形態にかかる計算装置の行うべき乗計算処理の手順について図４を用いて説明する。尚、ここでは、計算装置は、有限体の拡大体の元ａ（ａ∈Ｆｐ＾ｍ）のｑ乗を行うものとする。計算装置は、べき指数ｑをｐ進数展開する（ステップＳ１）。図５は、ｐ進数展開の処理の詳細な手順を示すフローチャートである。計算装置は、まず、‘ｉ＝０’、‘ｔ０＝ｑ’として（ステップＳ１０）、係数ｑｉを‘ｑｉ＝ｔｉｍｏｄ ｐ’として求め、‘ｔｉ＋１＝ｔｉ／ｐ’ を求める（ステップＳ１１）。次いで、計算装置は、ｉをインクリメントして、‘ｉ＝ｉ＋１’とし（ステップＳ１２）、次いで、‘ｔｉ＝０’か否かを判断する（ステップＳ１３）。ステップＳ１３の判断結果が否定的である場合、ステップＳ１１に進み、ステップＳ１３の判断結果が肯定的である場合、処理を終了する。以上のようにして、‘ｑｉ＜ｐ’である係数ｑｉを全てのｉ（０≦ｉ≦ｗ−１）について求めて、上述の式４により表されるように、べき指数ｑをｐ進数展開する。
【００３０】
図４に戻り、次いで、計算装置は、係数ｑｉをｒ進数展開する。（ステップＳ２）。図６は、ｒ進数展開の処理の詳細な手順を示すフローチャートである。計算装置は、まず、‘ｊ＝０’、‘ｔ０＝ｑｉ’として（ステップＳ２０）、係数ｑｉを‘ｑｉｊ＝ｔｉｍｏｄ ｒ’として求め、‘ｔｉ＋１＝ｔｉ／ｒ’を求める（ステップＳ２１）。次いで、計算装置は、ｊをインクリメントして、‘ｊ＝ｊ＋１’とし（ステップＳ２２）、次いで、‘ｔｊ＝０’か否かを判断する（ステップＳ２３）。ステップＳ２３の判断結果が否定的である場合、ステップＳ２１に進み、ステップＳ２３の判断結果が肯定的である場合、処理を終了する。以上のようにして、係数ｑｉについて、ｑｉｊ∈｛０，１，・・・，ｒ−１｝である係数ｑｉｊを全てのｊ（０≦ｊ≦ｈ−１）について求める。‘ｒ＝２’のとき、係数ｑｉをｒ進数展開したものは、上述の式５により表される。計算装置は、全てのｉ（０≦ｉ≦ｗ−１）について係数ｑｉに対する係数ｑｉｊを求める。
【００３１】
図４に戻り、次いで、計算装置は、計算値記憶テーブル５３を参照して、係数ｑiｊにおける同一のｊに対して積を計算したＳｊを求める（ステップＳ３）。図７は、Ｓｊを計算する処理の詳細な手順を示すフローチャートである。計算装置は、まず、Ｓｊを単位元として‘Ｓｊ＝１’とし、‘ｌ＝０’とし（ステップＳ３０）、‘ｖ＝ｄ−１’とする（ステップＳ３１）。次いで、計算装置は、‘ｋ＝０’とし（ステップＳ３２）、新たなｋの値として‘ｋ＝ｋ＋ｑ（ｌ×ｄ＋ｖ）ｊ×２＾ｖ’を求める（ステップＳ３３）。ｄは、上述のwindow幅である。次いで、計算装置は、‘ｖ＝ｖ−１’とし（ステップＳ３４）、‘ｖ＝０’か否かを判断する（ステップＳ３５）。ステップＳ３５の判断結果が否定的である場合、ステップＳ３３に進む。ステップＳ３５の判断結果が肯定的である場合、計算装置は、ステップＳ３３で求めたｋの値を用いて、計算値記憶テーブル５３に記憶されたＴ（ｋ）の値を参照して、Ｓｊの値を‘Ｓｊ＝Ｓｊ×Ｔ（ｋ）＾（ｌ×ｄ）’として求める（ステップＳ３６）。そして、計算装置は、ｌをインクリメントして‘ｌ＝ｌ＋１’とし（ステップＳ３７）、‘ｌ＝ｎ’か否かを判断する（ステップＳ３８）。‘ｎ＝ｗ／ｄ’である。ステップＳ３８の判断結果が否定的である場合、ステップＳ３１に進み、ステップＳ３８の判断結果が肯定的である場合、処理を終了する。以上のようにして、計算装置は、計算値記憶テーブル５３を参照して各Ｔ（ｋ）の値を取得し、Ｔ（ｋ）を用いて乗算及びべき乗計算を行うことにより、Ｓｊを求める。
【００３２】
図８は、ａ＾ｑを示した図２の表において、図３に示した計算値記憶テーブル５３に記憶されるＴ（ｋ）を用いて求められた各Ｓｊを模式的に示した図である。同図に示されるように、各ｊについて、ｐに対して４個ずつ連続するべき指数の組み合わせについて、その積がＴ（ｋ）を用いて計算されていることが示されている。
【００３３】
そして、全てのｊについてＳｊを計算すると、図４に戻り、計算装置は各Ｓｊを用いて、上述の式９によりａのｑ乗を計算する（ステップＳ４）。図９は、ａのｑ乗であるＳを計算する処理の詳細な手順を示すフローチャートである。計算装置は、まず、‘ｐ＜ｒ＾ｖ’なる最小のｖの値を求め（ステップＳ４０）、次いで、‘Ｓ＝Ｓｖ−１’とし、‘ｖ＝ｖ−１’とする（ステップＳ４１）。更に、計算装置は、‘ｖ＝ｖ−１’とし（ステップＳ４２）、‘Ｓ＝Ｓ＾｛ｒ｝×Ｓｖ’とする（ステップＳ４３）。次いで、計算装置は、‘ｖ＞０‘であるか否かを判断し（ステップＳ４４）、当該判断結果が肯定的である場合、ステップＳ４２に進む。ステップＳ４４の判断結果が否定的である場合、計算装置は処理を終了する。以上のようにして、計算装置は、ステップＳ３で求めたＳｊを用いてべき乗計算及び乗算を行って、ａのｑ乗を求める。
【００３４】
次に、計算装置が、上述したべき乗計算を行う前に、計算値記憶テーブル５３に記憶されるＴ（ｋ）の値を事前計算する処理の手順について図１０を用いて説明する。計算装置は、まず、単位元として‘Ｔ（０）＝１’として、‘Ｔ（１）＝ａ’とし（ステップＳ５０）、‘ｋ＝１０２’とする（ステップＳ５１）。‘１０２’は二進数表記で‘１’と‘０’との順序付き組み合わせを示すビット列である。次いで、計算装置は、‘ｋ ｍｏｄ ２＝１’か否かを判断する（ステップＳ５２）。ステップＳ５２の判断結果が否定的である場合、計算装置は、‘Ｔ（ｋ）＝Ｔ（ｋ／２）＾ｐ’とし（ステップＳ５３）、ステップＳ５２の判断結果が肯定的である場合、‘Ｔ（ｋ）＝Ｔ（（ｋ−１）／２）＾ｐ×ａ’とする（ステップＳ５４）。
【００３５】
ここでは、計算装置はフロベニウス写像を用いてＴ（ｋ）を求める。例えば、‘ｄ＝４’の場合、以下の式１０〜１１が成り立つ。
Ｔ（１１０２）＝Ｔ（１１００２）＾ｐ・・・（１０）
Ｔ（１１１０２）＝Ｔ（１１０２）×ａ・・・（１１）
このため、Ｔ（ｋ）の値の全てを乗算のみで求める必要はない。従って、計算装置は、ステップＳ５３又はステップＳ５４では、既に求められたＴ（ｋ／２）やＴ（（ｋ−１）／２）の値を用いて新たなＴ（ｋ）の値を求めることにより、各Ｔ（ｋ）の値を高速に求めることができる。
【００３６】
その後、その後いずれの場合もステップＳ５５に進み、計算装置は、‘ｋ＝ｋ＋１’とし（ステップＳ５５）、次いで、‘ｋ＜２＾ｄ’か否かを判断する（ステップＳ５６）。ステップＳ５６の判断結果が肯定的である場合、ステップＳ５２に進み、ステップＳ５６の判断結果が否定的である場合、計算装置は、処理を終了する。以上のようにして、計算装置は、window幅ｄに対してｄ個のビットの全ての組み合わせについて、Ｔ（ｋ）を求めてこれを計算値記憶テーブル５３に記憶させる。
【００３７】
以上のようにして、ある特殊な場合の有限体の拡大体のｐ乗はフロベニウス写像を高速に計算できることを利用して、べき指数ｑを標数ｐでｐ進数展開し、ｐ進数展開後の各係数ｑｉについてｒ進数展開する。そして、ｄ個のビットの全ての組み合わせについてべき乗計算の値を事前計算して記憶させ、記憶した値を用いて、Ｓｊを計算することにより、計算量を削減することが可能になる。このようなべき乗計算の方法は、例えば、公開鍵暗号に用いて好適である。
【００３８】
[第２の実施の形態]
次に、計算装置の第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００３９】
（１）構成
計算装置の有するｐ進数展開部５１及びｒ進数展開部５２の構成は上述の第１の実施の形態と同様である。計算値記憶テーブル５３の作成方法及び第１計算部５４の構成は上述の第１の実施の形態と異なる。上述の第１の実施の形態においては、Ｔ（ｋ）の値を予め計算して計算値記憶テーブル５３に記憶させることにより計算値記憶テーブル５３を予め作成し、第１計算部５４は、当該計算値記憶テーブル５３を参照して、Ｓｊを計算した。本実施の形態においては、Ｔ（ｋ）の値を事前に計算するのではなく、第１計算部５４がＳｊを計算する過程で、Ｔ（ｋ）の値を随時求めてこの値を計算値記憶テーブル５３に随時記憶させることにより計算値記憶テーブル５３を作成しながら、各ｊについてＳｊを計算する。尚、上述の第１の実施の形態に係るＴ（ｋ）と区別するため、以降、Ｔ’（ｋ）と表記する。
【００４０】
（２）動作
次に、本実施の形態にかかる計算装置の行うべき乗計算処理の手順について図１１を用いて説明する。ステップＳ１〜Ｓ２は上述の第１の実施の形態と同様である。ステップＳ３´では、計算装置は、計算値記憶テーブル５３を作成しながら、各ｊについてＳｊを計算する。図１２は、ステップＳ３´の処理の詳細な手順を示すフローチャートである。なお、ここではｂは最大長さｗのビット列であり、ｂには左から順に下位のビットが保存され、‘ｂ＝ｂ||｛０｝’であるとする（||はビットの連結）。計算装置は、まず、‘Ｔ’（１）＝ａ’とし、‘ｔ＝０’とし、‘Ｓｊ＝１’とする（ステップＳ６０）。次いで、計算装置は、‘ｑｔｊ＝１’であるか否かを判断し（ステップＳ６１）、当該判断結果が肯定的である場合（ステップＳ６１：ＹＥＳ）、‘ｂ＝１’とし、‘ｓ＝ｔ’とする（ステップＳ６２）。そして、計算装置は、‘ｔ＝ｔ＋１’とし（ステップＳ６３）、次いで、‘ｔ＜ｗ’であるか否かを判断する（ステップＳ６４）。当該判断結果が肯定的である場合（ステップＳ６４：ＹＥＳ）、計算装置は、‘ｑｔｊ＝１’であるか否かを判断する（ステップＳ６５）。当該判断結果が肯定的である場合（ステップＳ６５：ＹＥＳ）、計算装置は、Ｔ’（ｂ||１）が計算値記憶テーブル５３に記憶されているか否かを判断する（ステップＳ６６）。当該判断結果が否定的である場合（ステップＳ６６：ＮＯ）、計算装置は、以下の式１２によりＴ’（ｂ||１）を計算して、これを計算値記憶テーブル５３に記憶させる（ステップＳ６７）。
Ｔ’（ｂ||１）＝Ｔ’（ｂ）×ａ＾｛ｐ＾（ｔ−ｓ）｝・・・（１２）
次いで、計算装置は、以下の式１３によりＳｊを計算する（ステップＳ６８）。
Ｓｊ＝Ｓｊ×Ｔ’（ｂ||１）＾｛ｐ＾ｓ｝・・・（１３）
そして、計算装置は、ｔをインクリメントして‘ｔ＝ｔ＋１’とし（ステップＳ７１）、次いで、‘ｔ＜ｗ’であるか否かを判断する（ステップＳ７２）。当該判断結果が肯定的である場合、ステップＳ６１に戻る。ステップＳ７２の判断結果が否定的である場合、処理を終了する。
【００４１】
ステップＳ６６の判断結果が肯定的である場合、計算装置は、‘ｂ＝ｂ||ｑｔｊ’とすることによりビットｑｔｊをｂに連結し（ステップＳ７０）、上述のステップＳ６３に進む。即ち、‘ｑｔｊ＝０’である場合は、次に対象となるビット列についての処理に移る。
【００４２】
ステップＳ６４の判断結果が否定的である場合、計算装置は、以下の式１３によりＳｊを計算して（ステップＳ６９）、処理を終了する。
Ｓｊ＝Ｓｊ×Ｔ’（ｂ||１）＾｛ｐ＾ｓ｝・・・（１３）
【００４３】
以上のようにして、計算装置は、ステップＳ３´で全てのｊについてＳｊを計算すると、ステップＳ４で上述の第１の実施の形態と同様にして、ａのｑ乗を計算する。
【００４４】
以上のように、各Ｓｊを計算する過程で求められたＴ’（ｋ）の値を再利用して新たなＴ’（ｋ）の計算値記憶テーブル５３に随時記憶させることにより、事前計算を行う必要がなく、ａのｑ乗を高速に計算することが可能になる。
【００４５】
[第３の実施の形態]
次に、計算装置の第３の実施の形態について説明する。なお、上述の第１の実施の形態又は第２の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００４６】
本実施の形態においてはSliding Window法と同様の概念を利用する。この場合、先頭の値が‘０’とならないようにｄ個のビットの組み合わせを選択する。ｄは上述のwindow幅である。なぜなら、べき指数における係数ｑｉｊの値が‘０’である場合、当該係数との乗算の結果は‘０’であるため、乗算の必要がないからである。このため、‘０’が先頭となる場合にはこの値をスキップして先頭が‘１’となるビットの組み合わせを選択することにより、Ｓｊを計算する際にＴ（ｋ）を用いる個数ｎを‘ｗ／ｄ’より小さくすることが可能になり、さらに計算量を削減することが可能になる。
【００４７】
本実施の形態にかかるべき乗計算処理全体の手順は図４に示したとおりであり、第１の実施の形態と同様である。本実施の形態においては、ステップＳ３におけるＳｊを計算する処理の詳細な手順が第１の実施の形態と異なる。図１３は、本実施の形態においてＳｊを計算する処理の詳細な手順を示すフローチャートである。計算装置は、まず、Ｓｊを単位元として‘Ｓｊ＝１’とし、‘ｌ＝０’とし（ステップＳ８０）、次いで、‘ｑｉｊ＝０’か否かを判断する（ステップＳ８１）。当該判断結果が否定的である場合、計算装置は、‘ｔ＝１’とし、‘ｋ＝１’とし（ステップＳ８２）、次いで、新たなｋの値として‘ｋ＝ｋ＋ｑ（ｌ＋ｔ）ｊ×２＾ｔ’を求める（ステップＳ８３）。次いで、計算装置は、‘ｔ＝ｔ＋１’とし（ステップＳ８４）、‘ｌ＋ｔ＝ｎ’か否かを判断する（ステップＳ８５）。ステップＳ８５の判断結果が肯定的である場合、ステップＳ８７に進み、ステップＳ８５の判断結果が否定的である場合、計算装置は、次いで、‘ｔ＝ｄ’か否かを判断する（ステップＳ８６）。ステップＳ８６の判断結果が肯定的である場合、ステップＳ８３に進み、ステップＳ８６の判断結果が否定的である場合、ステップＳ８７に進む。ステップＳ８７では、計算装置は、ステップＳ８３で求めたｋの値を用いて、計算値記憶テーブル５３に記憶されたＴ（ｋ）の値を参照して、Ｓｊの値を‘Ｓｊ＝Ｓｊ×Ｔ（ｋ）＾ｌ’として求める（ステップＳ８７）。そして、計算装置は、‘ｌ＝ｌ＋ｄ’とし（ステップＳ８８）、‘ｌ＜ｎ’か否かを判断する（ステップＳ８９）。‘ｎ＝ｗ／ｄ’である。ステップＳ８９の判断結果が否定的である場合、ステップＳ８１に進み、ステップＳ８９の判断結果が肯定的である場合、処理を終了する。また、ステップＳ８１の判断結果が肯定的である場合、計算装置は、‘ｌ＝ｌ＋１’として（ステップＳ９０）、ステップＳ８１に進む。以上のようにして、計算装置は、Ｔ（ｋ）を用いる際のビット列について、先頭の値が‘０’とならないようにｄ個のビットの組み合わせを選択し、選択したビット列に対応するＴ（ｋ）の値を計算値記憶テーブル５３において参照して、Ｓｊを求める。
【００４８】
図１４は、ａ＾ｑを示した図２の表において、図３に示した計算値記憶テーブル５３に記憶されるＴ（ｋ）を用いて求められた各Ｓｊを模式的に示した図である。同図に示されるように、各ｊについて、ｐに対して４個ずつ連続するべき指数の組み合わせについて先頭が‘０’にならない４個のビットの組み合わせが選択され、その組み合わせに対応するＴ（ｋ）を用いて計算されていることが示されている。
【００４９】
次に、計算装置が、上述のべき乗計算を行う前に、計算値記憶テーブル５３に記憶されるＴ（ｋ）の値を事前計算する処理の手順について図１５を用いて説明する。計算装置は、まず、‘Ｔ（１）＝ａ’とし（ステップＳ１００）、‘ｋ＝１１２’とする（ステップＳ１０１）。次いで、計算装置は、‘Ｔ（ｋ）＝Ｔ（（ｋ−１）／２）＾ｐ×ａ’とする（ステップＳ１０２）。その後、計算装置は、‘ｋ＝ｋ＋２’とし（ステップＳ１０３）、次いで、‘ｋ＜２＾ｄ’か否かを判断する（ステップＳ１０４）。ステップＳ１０４の判断結果が肯定的である場合、ステップＳ１０２に進み、ステップＳ１０４の判断結果が否定的である場合、計算装置は、処理を終了する。以上のようにして、計算装置は、ｄ個のビットの組み合わせのうち、先頭のビットが‘０’でない組み合わせについてＴ（ｋ）を求めてこれを計算値記憶テーブル５３に記憶させる。
【００５０】
以上のような構成によれば、計算装置が有限体の拡大体において行うべき乗計算の計算量をより効果的に削減することができる。
【００５１】
[第４の実施の形態]
次に、計算装置の第４の実施の形態について説明する。なお、上述の第１の実施の形態乃至第３の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００５２】
（１）構成
本実施の形態においては、計算装置のｒ進数展開部５２は、ｐ進展開後の係数ｑｙ，ｑｙ＋１（０≦ｙ≦ｗ−２）について、係数ｑｙ＋１の下位数ビット分を係数ｑｙの項に振り分ける、即ち、係数ｑｙ＋１の値の一部のｐ倍を係数ｑｙに加えて、係数ｑｙ，ｑｙ＋１をｒ進数展開する。
【００５３】
ｐが‘ｐ≠ｒ＾ｎ（ｒ＾｛ｎ−１｝≦ｐ＜ｒ＾ｎ、ｎは自然数）’を満たす場合、ｑをｐ進数展開した後の係数ｑｉ（式４参照）は、‘ｑｉ＜ｒ＾ｎ’を満たしている。ここで、便宜上、‘ｒ＝２’として説明を進める。‘ｒ≠２’の場合でも概念としては同じである。例えば、‘ｐ＝９’、‘ｑ＝４８’とする。このとき、ｑをｐ進数展開すると、以下の式１５が成り立つ。
ｑ＝ｑ０＋ｑ１×ｐ＝３＋５×９（＝３×ｐ＾０＋５×ｐ＾１）・・・（１５）
このとき、‘ｑ０＝３’，‘ｑ１＝５’である。このｑ０、ｑ１を２進表記で各々表すと、‘ｑ０＝（１１２）’、‘ｑ１＝（１０１２）’となる。‘ｑｉ＜ｐ’のため、‘１１＝（１０１１２）’や‘１４＝（１１１０２）’などとなるｑｉは通常存在しない。ここではｑｉの表現として（１１１０２）などの、‘ｑｉ≧ｐ’となる表現をあえて許すことにより、係数ｑｉの表現の幅を持たせ、結果的に計算回数が少なくなるように係数ｑｉの表現を選択することにより、係数ｑｉをｒ進数展開する。
【００５４】
上記の例では‘ｑ０＝１２＝（１１００２）’、‘ｑ１＝４＝（１００２）’としても、‘ｑ＝ｑ０×ｐ＾０＋ｑ１×ｐ＾１’は満たされる上、ビット長の増加もない。図１６は、‘ｉ＝４’、‘ｒ＝２’及び‘ｈ＝１４’のとき、係数ｑ４，ｑ５について、係数ｑ５を２進数展開したときの係数ｑ５（０）が‘１’である場合のａ＾ｑを２次元の表形式で示した図である。同図においては、係数ｑ４を２進数展開したときの係数ｑ４（０）, ｑ４（１３）は各々‘０’である。図１７は、図４における係数ｑ５（０）を係数ｑ４の係数に振り分け、係数ｑ４（０）, ｑ４（１３）を各々‘１’にし、係数ｑ５（０）を‘０’にした状態を示す図である。このように、係数ｑi＋１の値の一部のｐ倍を係数ｑiに加えても、ａ＾ｐの計算結果は、図１６に示した場合と図１７に示した場合とで同じである。このような計算原理を利用して、本実施の形態においては、ｒ進数展開部５２は、ｐ進数展開後の係数ｑｉについて、‘１’の出現頻度を減らせる場合に限り‘ｑｉ≧ｐ’となるよう係数ｑｉを最適化して、ｒ進数展開する。
【００５５】
図１８は、本実施の形態にかかる係数最適化処理の手順を示すフローチャートである。計算装置は、‘k=０’とし(ステップＳ１１０）、‘ｑｋ＋ｐ＜ｒ＾ｎ’であるか否かを判断する（ステップＳ１１１）。当該判断結果が肯定的である場合、計算装置は、‘ｑ（ｋ＋１）０＝１’であるか否かを判断する（ステップＳ１１２）。当該判断結果が肯定的である場合、次いで、計算装置は、ｑｋの場合に‘１’が出現する個数と、‘ｑｋ＋ｐ’の場合に‘１’が出現する個数とを比較し、前者が後者以上であるか否かを判断する（ステップＳ１１３）。即ち、‘ｑｋ＋ｐ’とすることにより、ｑｋの場合と比べて‘１’が出現する個数が増えるか否かを計算装置は判断する。そして、ステップＳ１１３の判断結果が肯定的である場合、即ち、‘１’が出現する個数が増えない場合、計算装置は、‘ｑｋ＝ｑｋ＋ｐ’とし、‘ｑ（ｋ＋１）０＝ｑ（ｋ＋１）０−１’とし（ステップＳ１１４）、ステップＳ１１５に進む。ステップＳ１１１，Ｓ１１２又はＳ１１３の判断結果が否定的である場合も、ステップＳ１１５に進む。ステップＳ１１５では、計算装置は、ｋをインクリメントして‘ｋ＝ｋ＋１’とする。そして、計算装置は、‘ｋ＜ｎ’か否かを判断する(ステップＳ１１６)。ステップＳ１１６の判断結果が肯定的である場合、ステップＳ１１１に進み、ステップＳ１１６の判断結果が否定的である場合、当該係数最適化処理を終了する。このように、‘ｑｋ＋ｐ’とすることにより、ｑｋの場合と比べて‘１’が出現する個数が増えない場合には、計算装置は、‘ｑｋ＝ｑｋ＋ｐ’として、各ｑｉｊを計算し直す。以上のようにして、計算装置は、‘ｑi＋ｐ＜ｒ＾ｎ’且つ‘ｑ（i＋１）０＝１’となるｉを検索して、係数ｑiを最適化する。
【００５６】
以上の最適化処理の後、計算装置は、上述の第１の実施の形態又は第２の実施の形態において説明したステップＳ２以降の処理を行えば良い。このような本実施の形態における構成を第１の実施の形態や第２の実施の形態と組み合わせた場合、計算値記憶テーブル５３を参照する際のWindow幅の先頭又は後尾に存在する‘１’を‘０’に変換できると、‘１’の出現頻度を減らして乗算の回数を削減できる可能性が高い。このため、Window幅の先頭又は後尾になり易い係数ｑｄや係数ｑ（２ｄ）に注目すると高い効果が期待できる。従って、本実施の形態における構成によって、ｐ進数展開及びｒ進数展開後のビットの配列をべき指数の値を変えずに計算量が少なくなるよう最適化することで、効果的に計算量を削減することが可能になる。
【００５７】
尚、上述においてはビット長を増やさないよう処理を行うように構成したが、ビット長の増加を許せば、‘（ｑ０，ｑ１）＝（２１，３），（３０，２），（３９，１）’等も表現としては取り得る。
【００５８】
他の例として、‘ｐ＝１９’，‘ｑ＝２１６’である場合について説明する。このとき、‘ｑ＝７＋１１×１９’なので‘（ｑ０，ｑ１）＝（７，１１）’であるが、‘（ｑ０，ｑ１）＝（６４，８）’とすると、係数として‘１’が出現する個数は６個から２個に減少する。しかしながらｐは５ビットで表現できるのに対して、ｑ０を表現するのに７ビット必要となる。このため、このように表現を変換した場合、表現を変換する前に比べて、第１の実施の形態におけるステップ５の処理を２回多く繰り返す必要がある。しかし、最終的な目的はべき乗計算処理全体の処理量を削減することであるから、このような変換を複数回行って、全体として乗算の回数が削減できるように制御できれば良い。‘（ｑ０，ｑ１）＝（６４，８）’とした場合には、べき乗計算処理全体として乗算の回数が４回以上削減可能である。乗算の回数を減少させられるか否かについては実験的に決定され得る。例えば、べき指数が予め与えられていて、オフラインでの事前計算ができるような環境において、このようなビット長を長くした変換を行うことができれば、べき乗計算処理全体の計算量を削減することができる。
【００５９】
[第５の実施の形態]
次に、計算装置の第５の実施の形態について説明する。なお、上述の第１の実施の形態乃至第４の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００６０】
本実施の形態にかかるべき乗計算処理全体の手順は図４に示したとおりであり、第１の実施の形態と同様である。本実施の形態においては、ステップＳ３におけるＳｊを計算する処理の詳細な手順も第３の実施の形態と同様である。第３の実施の形態と異なるのは計算値記憶テーブルの作成方法である。ここでは計算値記憶テーブルの作成方法について説明する。
【００６１】
ここで用いる計算値記憶テーブルの作成方法はデータ圧縮等で用いられるＢＰＥ法と類似の概念を用いる。ＢＰＥ法の概念は出現頻度の高い２バイトの文字列を、使用していない１バイト文字に置き換える操作を繰り返すことである。
【００６２】
べき乗計算においては繰り返し出現する係数列に対応する乗算結果を予めテーブルとして保持しておけば、全体の乗算回数を削減できる。ただし、データ圧縮と異なるのは乗算をすべきなのは係数が‘１’のときであるため、係数が‘０’の場合は扱わなくても良い場合が存在することである。このため、ここでは‘０’以外で始まり‘０’以外で終わる系列を１つの「文字列」とみなし、この「文字列」が複数回出現するような系列に対応する乗算結果を記憶した計算値記憶テーブルを計算装置は作成する。計算値記憶テーブルに記憶する値のデータ長が長ければ長いほど乗算回数を削減できるものと考えられるが、長いデータ長の値を記憶する計算値記憶テーブルを作成するためにＢＰＥ法の概念を適用する。すなわち、‘０’以外の係数あるいは「文字」で始まり次の‘０’以外の係数あるいは「文字」まで（例えば（１，１），（１，０，０，１），（Ｃ，０，１）など）を１つの「文字列」として扱い、複数回出現する「文字列」を別の「文字」に便宜的に置き換えていくことを繰り返すことで、計算値記憶テーブルを計算装置は作成する。これを本実施の形態における作成方針とする。ここで「文字」は係数列または係数列と「文字」を束ねたものを表し、「文字列」は係数列あるいは「文字」の組み合わせの列であるものとする。
【００６３】
図１９は、本実施の形態にかかる計算値記憶テーブルを作成する処理の手順を示すフローチャートである。ここでは具体例として、‘ｈ＝１’、‘ｗ＝１０’、‘ｒ＝２’の場合を考える。‘（ｑ００，・・・，ｑ９０）＝（１，１，０，１，０，０，１，１，０，１）’であった場合、これを上述の作成方針に従って計算装置は変換する。まず計算装置は、この係数列の中で頻度の高い係数列を探す（ステップＳ２０１）。この結果、ここでは、（1,1）という係数列（「文字列」）が見つかる。計算装置はこれを新たな「文字」‘Ａ’に置き換える（ステップＳ２０２）。
（ｑ００，・・・，ｑ９０）＝（Ａ,０，１，０，０，Ａ，０，１）
【００６４】
次いで、計算装置は、変換後の係数列に対して、頻度の高い「文字列」を探すと（ステップＳ２０３）、ここでは、（Ａ，０，１）が見つかる（ステップＳ２０３：Ｙｅｓ）。また、これ以外に同じ「文字列」が存在しないのでステップＳ２０１からステップＳ２０２に進んで、これを‘Ｂ’と計算装置は置き換える。この結果、
（ｑ００，・・・，ｑ９０）＝（Ｂ,０，１，０，０,Ｂ）
となる。ここで２度以上同一の「文字列」が出現することはない（ステップＳ２０３：Ｎｏ）ので、「文字列」を係数列で表すと
Ａ：（１，１）
Ｂ：（Ａ，０，１）（＝（１，１，０，１））
となる。これを第３の実施の形態で示した計算値記憶テーブルのようなテーブル表現に変換すると、
Ａ：Ｔ（１１）＝ａ＾（１＋ｐ）
Ｂ：Ｔ（１１０１）＝ａ＾（１＋ｐ＾２＋ｐ＾３）
となる。計算装置はこれを求めて計算値記憶テーブル５３に記憶させる（ステップＳ２０４）。
【００６５】
以上のような構成によれば、計算装置が有限体の拡大体において行うべき乗計算の計算量をより効果的に削減することができる。
【００６６】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【００６７】
＜変形例１＞
上述した各実施の形態において、計算装置で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。
【００６８】
＜変形例２＞
上述の第１の実施の形態又は第３の実施の形態においては、Ｔ（ｋ）の値について、計算装置自体が事前計算を行って計算値記憶テーブル５３に予め記憶させるように構成した。しかし、計算装置は、他の情報処理装置が計算したＴ（ｋ）の値を取得して、これを計算値記憶テーブル５３に記憶させるようにしても良い。Ｔ（ｋ）の値の取得は、通信Ｉ／Ｆを介して通信により行うようにしても良いし、コンピュータで読み取り可能な記録媒体等からの読み出しにより行うようにしても良い。
【００６９】
また、上述の第１の実施の形態又は第３の実施の形態においては、Window幅を‘４’としたが、これに限らず、Window幅は‘２’以上且つ‘ｗ’以下であれば良い。
【００７０】
＜変形例３＞
上述の第１の実施の形態又は第２の実施の形態においては、べき指数が同じであるべき乗計算を複数行う場合、先のべき乗計算の際に行ったｐ進数展開の結果及びｒ進数展開の結果のうち少なくとも一方を再利用して、後のべき乗計算を行うようにしても良い。この場合、例えば、図２に示したような、ｐ進数展開後及びｒ進数展開後の各係数ｑｉｊの値をＨＤＤなどの外部記憶装置に記憶させておけばこれを後のべき乗計算の際に再利用することが可能である。
【００７１】
また、元が同じであるべき乗計算を複数行う場合、先のべき乗計算の過程で得られる計算結果の一部又は全部を再利用して、後のべき乗計算を行うようにしても良い。この場合、例えば、計算値記憶テーブル５３を後のべき乗計算の際に再利用することができる。
【００７２】
以上のように、複数のべき乗算においてべき指数又は元が同じであれば、共通の計算結果を共用することにより、計算量を効果的に削減することができる。
【００７３】
＜変形例４＞
上述の第２の実施の形態においては、ｂの値の上限を定めるように構成しても良い。このような構成によれば、計算値記憶テーブル５３への記憶と各Ｓｊの計算とをより効果的に行うことができる。
【００７４】
＜変形例５＞
上述の各実施の形態においては、べき乗を高速に計算可能な計算手法としてフロベニウス写像を用いたが、これに限らない。
【図面の簡単な説明】
【００７５】
【図１】第１の実施の形態にかかる計算装置の機能的構成を例示する図である。
【図２】元ａのｑ乗であるａ＾ｑを視覚的に表現するために２次元の表形式で示した図である。
【図３】‘ｄ＝４’である場合の計算値記憶テーブル５３を視覚的に示した図である。
【図４】同実施の形態にかかるべき乗計算処理の手順を示すフローチャートである。
【図５】同実施の形態にかかるｐ進数展開の処理の詳細な手順を示すフローチャートである。
【図６】同実施の形態にかかるｒ進数展開の処理の詳細な手順を示すフローチャートである。
【図７】同実施の形態にかかるＳｊを計算する処理の詳細な手順を示すフローチャートである。
【図８】同実施の形態にかかるａ＾ｑを示した図２の表において、図３に示した計算値記憶テーブル５３に記憶されるＴ（ｋ）を用いて求められた各Ｓｊを模式的に示した図である。
【図９】同実施の形態にかかるａのｑ乗であるＳを計算する処理の詳細な手順を示すフローチャートである。
【図１０】同実施の形態にかかる計算値記憶テーブル５３に記憶されるＴ（ｋ）の値を事前計算する処理の手順を示すフローチャートである。
【図１１】第２の実施の形態にかかるべき乗計算処理の手順を示すフローチャートである。
【図１２】同実施の形態にかかるステップＳ３´の処理の詳細な手順を示すフローチャートである。
【図１３】第３の実施の形態にかかるＳｊを計算する処理の詳細な手順を示すフローチャートである。
【図１４】同実施の形態にかかるａ＾ｑを示した図２の表において、図３に示した計算値記憶テーブル５３に記憶されるＴ（ｋ）を用いて求められた各Ｓｊを模式的に示した図である。
【図１５】同実施の形態にかかる計算値記憶テーブル５３に記憶されるＴ（ｋ）の値を事前計算する処理の手順を示すフローチャートである。
【図１６】第４の実施の形態にかかるａ＾ｑを２次元の表形式で示した図である。
【図１７】同実施の形態にかかるａ＾ｑを２次元の表形式で示した図であり、係数の変換後の状態を示す図である。
【図１８】同実施の形態にかかる係数最適化処理の手順を示すフローチャートである。
【図１９】第５の実施の形態にかかる計算値記憶テーブルを作成する処理の手順を示すフローチャートである。
【符号の説明】
【００７６】
５１  ｐ進数展開部
５２  ｒ進数展開部
５３  計算値記憶テーブル
５４  第１計算部
５５  第２計算部
【図１】
2010078833.tif 000003
【図２】
2010078833.tif 000004
【図３】
2010078833.tif 000005
【図４】
2010078833.tif 000006
【図５】
2010078833.tif 000007
【図６】
2010078833.tif 000008
【図７】
2010078833.tif 000009
【図８】
2010078833.tif 000010
【図９】
2010078833.tif 000011
【図１０】
2010078833.tif 000012
【図１１】
2010078833.tif 000013
【図１２】
2010078833.tif 000014
【図１３】
2010078833.tif 000015
【図１４】
2010078833.tif 000016
【図１５】
2010078833.tif 000017
【図１６】
2010078833.tif 000018
【図１７】
2010078833.tif 000019
【図１８】
2010078833.tif 000020
【図１９】
2010078833.tif 000021