(57)【要約】【課題】ＧＦ（ｑm ）上の元の平方根をＧＦ（ｑm ）上で求める際に要する演算コストの削減を実現する新たな拡大体平方根算出技術の提供を目的とする。【解決手段】本発明では、ＧＦ（ｑm ）上の元ｙの平方根ｘをＧＦ（ｑm ）上で求める際に、ｑn 乗フロベニウス写像演算手法を用いて、その平方根ｘを求めるようにするという構成を採る。ｑn 乗フロベニウス写像演算手法では、ｘ∈ＧＦ（ｑm ）を表現するベクトル（ｘi ）に行列（ｃij）をかけるだけでｘq を表現するベクトルが得られる。この演算コストは一般にはＧＦ（ｑm ）上の乗算１回分の演算コストとほぼ等しい。したがって、本発明によれば、ＧＦ（ｑm ）上の元の平方根をＧＦ（ｑm ）上で求める際に要する演算コストを大幅に削減できるようになる。【選択図】図１
2005063349.tif 000002
【特許請求の範囲】
【請求項１】
有限体ＧＦ（ｑ）の拡大体であるＧＦ（ｑm ) 上の元ｙを入力する入力手段と、該入力手段の入力したｙのｖ乗となるｙv （ただし、ｖ＝（ｕ−１）／２，ｕ＝（ｑm −１）／２k ，ｋ：正整数）を算出する算出手段とを備えて、該算出手段の算出したｙv に基づいて、ｙ＝ｘ2 を満たすＧＦ（ｑm ) 上の元ｘが存在する場合に、そのｘを算出して出力する拡大体平方根算出装置において、
上記算出手段が、ｑn 乗フロベニウス写像演算手法を用いて、上記入力手段の入力したｙのｖ乗となるｙv を算出するように構成されることを、
特徴とする拡大体平方根算出装置。
【請求項２】
請求項１に記載の拡大体平方根算出装置において、
（ｍ−１）／２の加算連鎖に基づいて、上記ｙv の算出にあたって必要となる冪乗演算の計算手順を決定する決定手段を備えることを、
特徴とする拡大体平方根算出装置。
【請求項３】
請求項１又は２に記載の拡大体平方根算出装置において、
ＧＦ（ｑ）上のとり得る値に対応付けて、上記ｙv の算出にあたって必要となる冪乗演算の計算値を記憶する記憶手段を備え、
上記算出手段は、上記記憶手段の記憶データを検索することで、上記ｙv の算出にあたって必要となる冪乗演算の計算値を算出することを、
特徴とする拡大体平方根算出装置。
【請求項４】
有限体ＧＦ（ｑ）の拡大体であるＧＦ（ｑm ) 上の元ｙを入力として、ｙ＝ｘ2 を満たすＧＦ（ｑm ) 上の元ｘが存在する場合に、そのｘを算出して出力する拡大体平方根算出装置において、
ｑn 乗フロベニウス写像演算手法を用いて、上記ｙを起点にして第１の半ノルムＨ2 、第２の半ノルムＨ1 、ＧＦ（ｑ）ノルムＮという順序に従って算出演算を実行することでＧＦ（ｑ）ノルムＮを算出する第１の算出手段と、
上記第１の算出手段の算出したＮの１／Ｎ1/2 となる値を算出する第２の算出手段と、
上記第１の算出手段の算出したＨ1 のｖ0 乗となるＨ1 v0（ただし、ｖ0 ＝（ｑ＋１）／２）を算出する第３の算出手段と、
上記第２の算出手段の算出した１／Ｎ1/2 と上記第３の算出手段の算出したＨ1 v0とに基づいて、上記ｘを算出する第４の算出手段とを備えることを、
特徴とする拡大体平方根算出装置。
【請求項５】
請求項４に記載の拡大体平方根算出装置において、
（ｍ−１）／２の加算連鎖に基づいて、上記ｙから上記Ｈ2 への算出に到る計算手順を決定する決定手段を備えることを、
特徴とする拡大体平方根算出装置。
【請求項６】
請求項４又は５に記載の拡大体平方根算出装置において、
上記Ｎのとり得る値に対応付けて１／Ｎ1/2 の値を記憶する記憶手段を備え、
上記第２の算出手段は、上記記憶手段の記憶データを検索することで、上記第１の算出手段の算出したＮの１／Ｎ1/2 となる値を算出することを、
特徴とする拡大体平方根算出装置。
【請求項７】
有限体ＧＦ（ｑ）の拡大体であるＧＦ（ｑm ) 上の元ｙを入力し、その入力したｙのｖ乗となるｙv （ただし、ｖ＝（ｕ−１）／２，ｕ＝（ｑm −１）／２k ，ｋ：正整数）を算出して、その算出したｙv に基づいて、ｙ＝ｘ2 を満たすＧＦ（ｑm ) 上の元ｘが存在する場合に、そのｘを算出して出力する拡大体平方根算出方法において、
ｑn 乗フロベニウス写像演算手法を用いて、上記入力したｙのｖ乗となるｙv を算出することを、
特徴とする拡大体平方根算出方法。
【請求項８】
請求項７に記載の拡大体平方根算出方法において、
（ｍ−１）／２の加算連鎖に基づいて、上記ｙv の算出にあたって必要となる冪乗演算の計算手順を決定することを、
特徴とする拡大体平方根算出方法。
【請求項９】
請求項７又は８に記載の拡大体平方根算出方法において、
上記ｙv を算出するときに、ＧＦ（ｑ）上のとり得る値に対応付けて、上記ｙv の算出にあたって必要となる冪乗演算の計算値を記憶する記憶手段の記憶データを検索することで、その冪乗演算の計算値を算出することを、
特徴とする拡大体平方根算出方法。
【請求項１０】
有限体ＧＦ（ｑ）の拡大体であるＧＦ（ｑm ) 上の元ｙを入力として、ｙ＝ｘ2 を満たすＧＦ（ｑm ) 上の元ｘが存在する場合に、そのｘを算出して出力する拡大体平方根算出方法において、
ｑn 乗フロベニウス写像演算手法を用いて、上記ｙを起点にして第１の半ノルムＨ2 、第２の半ノルムＨ1 、ＧＦ（ｑ）ノルムＮという順序に従って算出演算を実行することでＧＦ（ｑ）ノルムＮを算出する過程と、
上記算出したＮの１／Ｎ1/2 となる値を算出する過程と、
上記算出したＨ1 のｖ0 乗となるＨ1 v0（ただし、ｖ0 ＝（ｑ＋１）／２）を算出する過程と、
上記算出した１／Ｎ1/2 と上記算出したＨ1 v0とに基づいて、上記ｘを算出する過程とを備えることを、
特徴とする拡大体平方根算出方法。
【請求項１１】
請求項１０に記載の拡大体平方根算出方法において、
（ｍ−１）／２の加算連鎖に基づいて、上記ｙから上記Ｈ2 への算出に到る計算手順を決定する過程を備えることを、
特徴とする拡大体平方根算出方法。
【請求項１２】
請求項１０又は１１に記載の拡大体平方根算出方法において、
上記１／Ｎ1/2 を算出する過程では、上記Ｎのとり得る値に対応付けて１／Ｎ1/2 の値を記憶する記憶手段の記憶データを検索することで、そのＮの１／Ｎ1/2 となる値を算出することを、
特徴とする拡大体平方根算出方法。
【請求項１３】
請求項７ないし１２のいずれか１項に記載の拡大体平方根算出方法の実現に用いられる処理をコンピュータに実行させるための拡大体平方根算出プログラム。
【請求項１４】
請求項７ないし１２のいずれか１項に記載の拡大体平方根算出方法の実現に用いられる処理をコンピュータに実行させるための拡大体平方根算出プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
有限体ＧＦ（ｑ）の拡大体であるＧＦ（ｑm ) 上の元ｙを入力として、ｙ＝ｘ2 を満たすＧＦ（ｑm ) 上の元ｘが存在する場合に、その元ｘを算出して出力する拡大体平方根算出装置及びその方法と、その拡大体平方根算出方法の実現に用いられる拡大体平方根算出プログラム及びそのプログラムを記録した記録媒体とに関する。
【背景技術】
【０００２】
近年、楕円曲線が情報セキュリティの分野で注目されている。一般に、体Ｋ上で定義された楕円曲線とは、ａ1,ａ2,ａ3,ａ4,ａ6 ∈Ｋとして、等式
ｙ2 ＋ａ1 ｘｙ＋ａ3 ｙ＝ｘ3 ＋ａ2 ｘ2 ＋ａ4 ｘ＋ａ6       式（１）
を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる特別の点を付加したものである。
【０００３】
楕円曲線上の任意の２点に対して楕円加算と呼ばれる演算が定義でき、演算結果の出力自体も同じ楕円曲線上の第３の点となる。楕円曲線は楕円加算に関して群をなし、特に有限体上で定義された楕円曲線上の有理点を用いて、暗号系や署名系に利用可能な有限巡回群を生成することが可能である。
【０００４】
体Ｋの標数が２でも３でもないとすると、式（１）は、
ｙ2 ＝ｘ3 ＋ａｘ＋ｂ                                      式（２）
と変形することができる。このとき、この式（２）を満たす点を暗号系や署名系に利用する場合に、（ｘ，ｙ）の組を使う代わりにｘのみ、あるいはｘ及び、ｙに関する１ビットの情報のみを使う場合がある。
【０００５】
この方法を用いれば、例えば点の値を通信する際には、（ｘ，ｙ）の組を使うより通信量をおよそ半分に減らすことが可能である。暗号系や署名系の利用者が楕円加算などの演算を実行するためには、通常はｙの値も必要であるが、その目的のためには式（２）をｙに関して解けばよい。すなわち、
ｙ＝±（ｘ3 ＋ａｘ＋ｂ）1/2                               式（３）
であることから、ｘ，ｙの定義体上で平方根を決定するアルゴリズムが存在すれば、ｘの値及び、符号を決定する１ビット分の情報から点（ｘ，ｙ）を求めることができる。
【０００６】
このようなことを背景にして、下記に示す非特許文献１で、ｑを奇素数またはその冪とし、ｍを正整数とし、ＧＦ（ｑm ）を位数ｑm の有限体とする場合に、ＧＦ（ｑm ）上の元ａの平方根をＧＦ（ｑm ）上で求める方法が提案されている。
【０００７】
この非特許文献１に記載される方法は、ｋを正整数、ｕを奇数、ｖを整数とし、ｋ，ｕ，ｖが
ｕ＝（ｑm −１）／２k ，ｖ＝（ｕ−１）／２
を満たすとすると、おおよそ図６に示すように記述される。
【非特許文献１】和田秀男著，『コンピュータと素因子分解』, pp.45-48, 発行  遊星社, 発売  星雲社，ISBN4-7952-6889-4
【発明の開示】
【発明が解決しようとする課題】
【０００８】
非特許文献１に記載される方法において、有限体の位数が極めて特殊な場合を除いてｋは小さな整数であるので、最も演算コストの大きいと考えられるのは、Step１.1で行うことになる「ａ-1←ａv 」という、入力ａに対しＧＦ（ｑm ）上の冪乗演算を行う部分である。
【０００９】
従来、この部分はバイナリ法などの一般的な冪乗計算法により実装されていた。楕円曲線暗号などでこの演算が必要となる場合、ｖは最低でも１６０ビット程度の整数であり、バイナリ法の場合には、最低１６０回のＧＦ（ｑm ）上自乗演算と、約８０回のＧＦ（ｑm ）上乗算とを実行しなくてはならない。
【００１０】
このように、従来技術に従っていると、ＧＦ（ｑm ）上の元の平方根をＧＦ（ｑm ）上で求めるのに、多大な演算コストを強いられるという問題があった。
【００１１】
本発明はかかる事情に鑑みてなされたものであって、ＧＦ（ｑm ）上の元の平方根をＧＦ（ｑm ）上で求める際に要する演算コストの削減を実現する新たな拡大体平方根算出技術の提供を目的とする。
【課題を解決するための手段】
【００１２】
（１）上記目的を達成するために、本発明の拡大体平方根算出装置は、有限体ＧＦ（ｑ）の拡大体であるＧＦ（ｑm ) 上の元ｙを入力する入力手段と、入力手段の入力したｙのｖ乗となるｙv （ただし、ｖ＝（ｕ−１）／２，ｕ＝（ｑm −１）／２k ，ｋ：正整数）を算出する算出手段とを備えて、算出手段の算出したｙv に基づいて、ｙ＝ｘ2 を満たすＧＦ（ｑm ) 上の元ｘが存在する場合に、そのｘを算出して出力する処理を行うときに、算出手段が、ｑn 乗フロベニウス写像演算手法を用いて、入力手段の入力したｙのｖ乗となるｙv を算出するように構成される。
【００１３】
この構成を採るときに、（ｍ−１）／２の加算連鎖に基づいて、ｙv の算出にあたって必要となる冪乗演算の計算手順を決定する決定手段を備えることがあり、この場合には、算出手段は、決定手段の決定した計算手順に従って、ｙv の算出にあたって必要となる冪乗演算を実行することになる。
【００１４】
また、この構成を採るときに、ＧＦ（ｑ）上のとり得る値に対応付けて、ｙv の算出にあたって必要となる冪乗演算の計算値を記憶する記憶手段を備えることがあり、この場合には、算出手段は、記憶手段の記憶データを検索することで、ｙv の算出にあたって必要となる冪乗演算の計算値を算出することになる。
【００１５】
以上の各処理手段が動作することで実現される本発明の拡大体平方根算出方法はコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどのような適当な記録媒体に記録して提供されたり、ネットワークを介して提供され、本発明を実施する際にインストールされてＣＰＵなどの制御手段上で動作することにより本発明を実現することになる。
【００１６】
（２）また、上記目的を達成するために、本発明の拡大体平方根算出装置は、有限体ＧＦ（ｑ）の拡大体であるＧＦ（ｑm ) 上の元ｙを入力として、ｙ＝ｘ2 を満たすＧＦ（ｑm ) 上の元ｘが存在する場合に、そのｘを算出して出力する処理を行うときに、（ｉ）ｑn 乗フロベニウス写像演算手法を用いて、ｙを起点にして第１の半ノルムＨ2 、第２の半ノルムＨ1 、ＧＦ（ｑ）ノルムＮという順序に従って算出演算を実行することでＧＦ（ｑ）ノルムＮを算出する第１の算出手段と、（ii）第１の算出手段の算出したＮの１／Ｎ1/2 となる値を算出する第２の算出手段と、（iii)第１の算出手段の算出したＨ1 のｖ0 乗となるＨ1 v0（ただし、ｖ0 ＝（ｑ＋１）／２）を算出する第３の算出手段と、（iv) 第２の算出手段の算出した１／Ｎ1/2 と第３の算出手段の算出したＨ1 v0とに基づいて、ｘを算出する第４の算出手段とを備えるように構成される。
【００１７】
この構成を採るときに、（ｍ−１）／２の加算連鎖に基づいて、ｙからＨ2 への算出に到る計算手順を決定する決定手段を備えることがあり、この場合には、第１の算出手段は、決定手段の決定した計算手順に従って、ｙを起点にしてＨ2 を算出することになる。
【００１８】
また、この構成を採るときに、Ｎのとり得る値に対応付けて１／Ｎ1/2 の値を記憶する記憶手段を備えることがあり、この場合には、第２の算出手段は、記憶手段の記憶データを検索することで、第１の算出手段の算出したＮの１／Ｎ1/2 となる値を算出することになる。
【００１９】
以上の各処理手段が動作することで実現される本発明の拡大体平方根算出方法はコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどのような適当な記録媒体に記録して提供されたり、ネットワークを介して提供され、本発明を実施する際にインストールされてＣＰＵなどの制御手段上で動作することにより本発明を実現することになる。
【発明の効果】
【００２０】
本発明では、ＧＦ（ｑm ）上の元ｙの平方根ｘをＧＦ（ｑm ）上で求める際に、ｑn 乗フロベニウス写像演算手法を用いて、その平方根ｘを求めるようにするという構成を採る。ｑn 乗フロベニウス写像演算手法では、ｘ∈ＧＦ（ｑm ）を表現するベクトル（ｘi ）に行列（ｃij）をかけるだけでｘq を表現するベクトルが得られる。この演算コストは一般にはＧＦ（ｑm ）上の乗算１回分の演算コストとほぼ等しい。
【００２１】
したがって、本発明によれば、ＧＦ（ｑm ）上の元の平方根をＧＦ（ｑm ）上で求める際に要する演算コストを大幅に削減できるようになる。
【発明を実施するための最良の形態】
【００２２】
〔第１の実施形態例〕
図１に、第１の実施形態例に従う本発明の拡大体平方根算出装置１の装置構成の一例を図示する。
【００２３】
この図に示すように、第１の実施形態例に従う場合、本発明の拡大体平方根算出装置１は、入力部１０と、ＧＦ（ｑ）ノルム算出部１１と、加算連鎖決定部１２と、（１／Ｎ1/2 ）テーブル１３と、（１／Ｎ1/2 ）算出部１４と、Ｈ算出部１５と、平方根算出部１６とを備える。
【００２４】
この入力部１０は、ＧＦ（ｑm ) 上の元ａを入力する。ＧＦ（ｑ）ノルム算出部１１は、ｑn 乗フロベニウス写像演算手法を用いて、入力部１０の入力したａを起点にして第１の半ノルムＨ2 、第２の半ノルムＨ1 、ＧＦ（ｑ）ノルムＮという順序に従って算出演算を実行することでＧＦ（ｑ）ノルムＮを算出する。加算連鎖決定部１２は、（ｍ−１）／２の加算連鎖に基づいて、入力部１０の入力したａから第１の半ノルムＨ2 への算出に到る計算手順を決定する。
【００２５】
（１／Ｎ1/2 ）テーブル１３は、ＧＦ（ｑ）ノルムＮのとり得る値に対応付けて１／Ｎ1/2 の値を記憶する。（１／Ｎ1/2 ）算出部１４は、ＧＦ（ｑ）ノルム算出部１１の算出したＮをキーにして（１／Ｎ1/2 ）テーブル１３を検索することで、そのＮの１／Ｎ1/2 となる値を算出する。
【００２６】
（１／Ｎ1/2 ）算出部１４は、（１／Ｎ1/2 ）テーブル１３が用意されない場合には、図２に示す計算手順に従ってＮ1/2 を算出して、拡張ユークリッドの互除法に従ってＧＦ（ｑ）上の割り算を実行することで、ＧＦ（ｑ）ノルム算出部１１の算出したＮの１／Ｎ1/2 となる値を算出することになる。
【００２７】
ここで、図２に示す計算手順は、図６に示す計算手順（非特許文献１に記載される計算手順）で「ｍ＝１」とおいたものであり、ＧＦ（ｑ）上の元ａの平方根をＧＦ（ｑ）上で求める方法を示している。
【００２８】
Ｈ算出部１５は、一般的な冪乗演算手法を用いて、ＧＦ（ｑ）ノルム算出部１１の算出したＨ1 のｖ0 乗となるＨ1 v0（ただし、ｖ0 ＝（ｑ＋１）／２）を算出する。平方根算出部１６は、（１／Ｎ1/2 ）算出部１４の算出した１／Ｎ1/2 （≡Ｔ1)と、Ｈ算出部１５の算出したＨ1 v0（≡Ｈ）とを乗算することで、入力部１０の入力したａの平方根を算出して出力する。
【００２９】
次に、このように構成される本発明の拡大体平方根算出装置１の実現のために用いられる数学的な理論的根拠について説明する。
【００３０】
（１）ｑn 乗フロベニス写像
通常、有限体ＧＦ（ｑm ) 上の元ｘを表現するのに、有限体ＧＦ（ｑ) 上のｍ個の元ｘi （０≦ｉ＜ｍ）が用いられる。ｍ個のｘi ∈ＧＦ（ｑ）,(０≦ｉ＜ｍ）の組をＧＦ（ｑm ) 上の元に対応させる代表的な方法は、ｍ個のαi ∈ＧＦ（ｑm ) ,(０≦ｉ＜ｍ）の組を使って、
ｘ＝Σｘi αi     ただし、Σはｉ＝０〜ｍ−１の総和
なる対応を取ることである。このとき、αi ,(０≦ｉ＜ｍ）はＧＦ（ｑ）m とＧＦ（ｑm ) とで１対１対応が取れるような特別の組合わせでなくてはならない。このαi ,(０≦ｉ＜ｍ）を基底と呼ぶ。
【００３１】
ところで、二項定理によれば、
（ａ＋ｂ）q ＝Σ qＣi ａq-i ｂi     ただし、Σはｉ＝０〜ｑの総和
である。右辺の各項の係数 qＣi は二項係数と呼ばれる定数で、ｉ≠０かつｉ≠ｑの場合必ずｑの倍数となる。ａ，ｂ∈ＧＦ（ｑm ) のときには、ｑの整数倍は０と同値であるから、
（ａ＋ｂ）q ＝ａq ＋ｂq 
が成立する。更に、ｃ∈ＧＦ（ｑ）なるｃに関してｃq ＝ｃが成立する。
【００３２】
これらのことから、一般に、ａi ∈ＧＦ（ｑm ) ,(０≦ｉ＜ｎ）、ｃi ∈ＧＦ（ｑ）,(０≦ｉ＜ｎ）とすると、次の式が成立する。
【００３３】
【数１】
2005063349.tif 000003
【００３４】
従って、αi ∈ＧＦ（ｑm ) 、ｘi ∈ＧＦ（ｑ）なるとき、「ｘ＝Σｘi αi （ただし、Σはｉ＝０〜ｍ−１の総和）」なるｘのｑ乗ｘq は、「ｘq ＝Σｘi αi q （ただし、Σはｉ＝０〜ｍ−１の総和）」である。
【００３５】
従って、事前に、「αi q ＝Σｃijαi （ただし、Σはｊ＝０〜ｍ−１の総和）」なるｃij∈ＧＦ（ｑ) が計算してあれば、次の式によって、元の基底αi を使ったｘq の表現である「Σｃijｘi （ただし、Σはｊ＝０〜ｍ−１の総和）」を求めることができる。
【００３６】
【数２】
2005063349.tif 000004
【００３７】
すなわち、ｘ∈ＧＦ（ｑm ) を表現するベクトル（ｘi ）に行列（ｃij）をかけるだけでｘq を表現するベクトルが得られる。この演算コストは一般にはＧＦ（ｑm ) 上の乗算１回分の演算コストとほぼ等しい。
【００３８】
また、行列（ｃij）n ,(ｎ＝２，３，・・・）を事前に求めておけば、行列（ｃij）n をかけるだけでｘ[qn]（ただし、[qn]≡ｑn ）を表現するベクトルが得られる。あるいは、（ｃij）-1を事前に求めておけば、（ｃij）-1をかけるだけでｘ1/q を表現するベクトルが得られる。従って、一般の整数ｎに対してｘ[qn]（ただし、[qn]≡ｑn ）の演算コストは一般にＧＦ（ｑm ) 上の乗算１回分の演算コストに等しい。
【００３９】
また、代表的な基底の選び方として、
正規基底による方法      αi ＝β[qi]（ただし、[qi]≡ｑi ）
多項式基底による方法    αi ＝γi 
という２つの方法がある。ただし、β，γは各々の方法でＧＦ（ｑ）m とＧＦ（ｑm ) とで１対１対応が取れるような特別なＧＦ（ｑm ) 上の元とする。
【００４０】
これらの基底を選択する場合には、演算コストをさらに低減できることがある。例えば正規基底の場合、
αi q ＝（β[qi]）q ＝（β[q(i+1)]）＝αi+1   （ただし、αm ≡α0 ）
であることから、行列（ｃij）は次のようになる。
【００４１】
【数３】
2005063349.tif 000005
【００４２】
すなわち、入力のｍ個のｘi ∈ＧＦ（ｑ）,(０≦ｉ＜ｍ）の順番を並び換えて出力するだけでｘq の演算が完了する。ｘ[qn]（ただし、[qn]≡ｑn ）の演算の場合も並び換えのみで完了する。この演算コストは、ＧＦ（ｑm ) 上の乗算の演算コストに対して無視できる。
【００４３】
一方、多項式基底の場合、一般にはｘ[qn]（ただし、[qn]≡ｑn ）の演算はＧＦ（ｑm ) 上の乗算の演算コストとほぼ等しいが、γとして特別なＧＦ（ｑm ) 上の元を選択することによって演算コストを低減できることがある。例えばγがω∈ＧＦ（ｑ）に対して「γm'−ω＝０」なる関係を持つ場合、次の式が成立する。
【００４４】
【数４】
2005063349.tif 000006
【００４５】
すなわち、入力のｍ個のｘi ∈ＧＦ（ｑ）,(０≦ｉ＜ｍ）の各々にωj をかけて順番を並び換えて出力するだけでｘ[qn]（ただし、[qn]≡ｑn ）の演算が完了する。この演算コストも、ＧＦ（ｑm ) 上の乗算の演算コストに対して無視できる。
【００４６】
（２）共役元ｘ[qn],(ｎ＝０，・・・，ｍ−１）の対称式
有限体ＧＦ（ｑm ) 上の任意の元ｘに対して、ｘを解に持つＧＦ（ｑ）係数のｍ次多項式が必ず存在する。
【００４７】
ｃi ∈ＧＦ（ｑ）とすると、
ｆ（ｚ）＝Σｃi ｚ        ただし、Σはｉ＝０〜ｍ−１の総和
に対して、ｘ∈ＧＦ（ｑm ) がｆ（ｘ）＝０を満たすなら、フロベニウス写像の性質により、
（ｆ（ｘ))q ＝Σｃi ｘq ＝ｆ（ｘq ）
であるから、ｘq もまたｆ（ｘq ）＝０を満たす。
【００４８】
ｘ[qn],(ｎ＝０，・・・，ｍ−１）がｆ（ｚ）＝０のｍ個の解になっているとき、解と係数の関係により、ｘ[qn],(ｎ＝０，・・・，ｍ−１）の基本対称式はｆ（ｚ）の係数ｃi ∈ＧＦ（ｑ）の±１倍である。従って、ｘ[qn],(ｎ＝０，・・・，ｍ−１）の基本対称式の任意のＧＦ（ｑ）係数多項式によって作られる対称式はＧＦ（ｑ）上の元である。ｑが十分小さければ、ＧＦ（ｑ）上の任意の関数を例えばテーブル演算等に置き換えることができる。
【００４９】
（３）３次以上の奇数次拡大
拡大次数ｍを３以上の奇数とし、ｍ’＝（ｍ−１）／２とする。ｑを奇素数またはその冪とする。整数ｕ0,ｕ1,ｕ2,ｖ0 を、
ｕ0 ＝Σｑi       ただし、Σはｉ＝０〜ｍ−１の総和
ｕ1 ＝Σｑ2i      ただし、Σはｉ＝０〜ｍ’の総和
ｕ2 ＝Σｑ2i      ただし、Σはｉ＝０〜ｍ’−１の総和
ｖ0 ＝（ｑ＋１）／２
とし、ａをａ≠０なるＧＦ（ｑm ) 上の任意の元とし、
Ｎ＝ａu0，    Ｈ＝（ａu1）v0
とする。
【００５０】
この定義に従い、
Ｎ＝ａ×ａq ×ａ[q2]×・・・・×ａ[q(m-1)]
となるが、このＮはａの共役元の対称式であるから、Ｎ∈ＧＦ（ｑ）としてよく、
Ｈ2 ＝Ｎ×ａ
であるから、ａの平方根がＧＦ（ｑm ) 上に存在することとＮの平方根がＧＦ（ｑ）上に存在することとは同値で、Ｎ≠０すなわちａ≠０なら
±（ａ）1/2 ＝±Ｈ／Ｎ1/2 
である。このＮを入力ａのＧＦ（ｑ）ノルムと呼ぶ。
【００５１】
非特許文献１に記載される計算手順（図６に示す計算手順）では、ｑを固定した場合、ＧＦ（ｑm ) 上の平方根を求めるのに必要な演算量はｍの３乗に比例すると考えてよい。従って、ｍ≧３のとき、ＧＦ（ｑ) 上の平方根を非特許文献１に記載される計算手順で求めるのに必要な演算量は、ＧＦ（ｑm ) 上の平方根を非特許文献１に記載される計算手順で求めるのに必要な演算量に比べて十分小さいと見なせる。さらに、ｑが十分小さければ、１／Ｎ1/2 は“解なし”も含めて∀Ｎ∈ＧＦ（ｑ）に対して予めテーブルとして用意しておくことができる。従って、一旦Ｎ，Ｈが求まってしまえば、１／Ｎ1/2 倍の演算量は無視してよい。
【００５２】
Ｈ1,Ｈ2 として、
Ｈ1 ＝ａu1，  Ｈ2 ＝ａu2
を定義すると、
Ｈ1 ＝ａ×（Ｈ2)[q2]，  Ｎ＝Ｈ1 ×（Ｈ2)q ,   Ｈ＝（Ｈ1)v0
である。
【００５３】
ｑ乗やｑ2 乗はフロベニウス写像によって高速に演算でき、冪ｖ0 は非特許文献１に記載される計算手順のStep１.1の冪ｖに対して十分小さいと見なせるので、結局ＧＦ（ｑm ) 上の平方根の律速段階はＨ2 ＝ａu2を演算する段階であると見なせる。
【００５４】
（４）加算連鎖
ここでは、Ｈ2 を効率よく計算する方法を与える。ｎを整数、ｐを奇素数またはその冪とする。Ｈ2 を計算する場合は、ｎ＝ｍ’，ｐ＝ｑ2 とすればよい。                        
【００５５】
Ｕとして、
Ｕ＝Σｐi     ただし、Σはｉ＝０〜ｎ−１の総和
を定義する。ａをＧＦ（ｑm ) 上の任意の元とし、ｐ＝ｑ2 とすれば、ａU は、
ａU ＝ａ×ａp ×ａ[p2]×・・・・×ａ[p(n-1)]
のように計算することができる。
【００５６】
このような計算を行う際、ｐi 乗はフロベニウス写像を使ってＧＦ（ｑm ) 上乗算に比べ高速に演算可能であるから、演算の律速段階となるのはｎ−１回実行されるＧＦ（ｑm ) 上乗算である。
【００５７】
ところで、例えばｎ＝２l だったとすると、
Ｕ＝（１＋ｐ)(１＋ｐ2)（１＋ｐ4)・・・（１＋ｐ[2(l-1)]）
と分解できるので、ａU を計算する方法として、例えば次のような演算方法を用いることができる。
【００５８】
【数５】
2005063349.tif 000007
【００５９】
この演算方法を用いると、ｌ回すなわちlog2ｎ回のＧＦ（ｑm ) 上乗算でａU を計算できる。このような計算法はたとえｎが２冪の数でなかったとしても一般に構成することが可能であり、例えば次のように構成する。
【００６０】
ｉ，ｊ，ｋを整数として、整数（１＝）ｎ0,・・・，ｎl ( ＝ｎ）を
ｎ0 ＝１，  ｎi ＝ｎj ＋ｎk ,(ｊ，ｋ＜ｉ）
とする。整数列ｎ0,・・・，ｎl をｎの加算連鎖と呼ぶ。ｎの加算連鎖を用いてｐ冪倍を含む加算連鎖
Ｎ0 ＝１，  Ｎi ＝ｐnkＮj ＋Ｎk ,(ｊ，ｋ＜ｉ）
を構成することができる。このとき、
Ｎi ＝Σｐi     ただし、Σはｉ＝０〜ｎi −１の総和
が成立している。
【００６１】
このｐ冪倍を含む加算連鎖を用いてａU の計算を次のように実行することができる。まずｎの加算連鎖ｎ0,・・・，ｎl を与える。加算連鎖のｎi ＝ｎj ＋ｎk ,(ｊ，ｋ＜ｉ）なるｉ，ｊ，ｋの対応に従って、ｉ＝０，・・・，ｌに対して、次に示す演算により、Ａ0,・・・，Ａl を求める。このとき、Ａi ＝ａNiが成立する。
【００６２】
【数６】
2005063349.tif 000008
【００６３】
Ｎl は、
Ｎl ＝Σｐi     ただし、Σはｉ＝０〜ｎ−１の総和
であるから、Ａl が求めるａU となる。ｎの最短の加算連鎖の長さｌは最悪でもｌ≦２log2ｎに抑えることができる。すなわち、Ａl も最悪２log2ｎ回程度のＧＦ（ｑm ) 上乗算で求めることができる。
【００６４】
一般にａU を効率良く求めたいなら、効率の良いｎの加算連鎖を与えればよい。以下の参考文献には、１以上１００以下の整数の加算回数に関する最適加算連鎖のＴree 図が掲載されている。そのような加算連鎖を用いることによってａU の計算を最適化できる。
参考文献：
Knuth 著, 『The Art of Computer Programming 』VOLUME2 Seminumerical Algorithms Third Edition,p.465, 出版 Addison Wesley,ISBN0-201-89684-2 
図３に、以上に説明した数学的な理論的根拠に基づいて本発明の拡大体平方根算出装置１が実行することになる処理フローの一例を図示する。ここで、この処理フローではｍ＝１７を想定している。
【００６５】
本発明の拡大体平方根算出装置１では、事前演算として、（ｍ−１）／２の加算連鎖に基づいて、入力されるＧＦ（ｑm ) 上の元ａから上述したＨ2 への算出に到る計算手順を決定するとともに、ＧＦ（ｑ）ノルムＮのとり得る値に対応付けて１／Ｎ1/2 の値を記憶する（１／Ｎ1/2 ）テーブル１３を作成する。
【００６６】
図３に示す処理フローでは、加算連鎖決定部１２は、整数列１→８（ｍ’）に到る加算連鎖として、
ｍ0 ＝１
ｍ1 ＝ｍ0 ＋ｍ0   （＝２）
ｍ2 ＝ｍ1 ＋ｍ1   （＝４）
ｍ3 ＝ｍ2 ＋ｍ2   （＝８）
を決定している。
【００６７】
この加算連鎖については、例えば、上述した参考文献に記載されるＴree 図をメモリに記録しておいて、それを参照することで決定することになる。
【００６８】
この加算連鎖の決定に従って、ＧＦ（ｑ）ノルム算出部１１は、図中の「Step１」に示す手順に従い、ｑn 乗フロベニウス写像演算手法を用いて、入力部１０の入力したａを起点にしてＨ2 を算出することになる。
【００６９】
一方、上述したように、ａの平方根がＧＦ（ｑm ) 上に存在することとＮの平方根がＧＦ（ｑ）上に存在することとは同値で、Ｎ≠０すなわちａ≠０なら
±（ａ）1/2 ＝±Ｈ／Ｎ1/2         ただし、Ｈ＝（Ｈ1)v0
が成立する。
【００７０】
この１／Ｎ1/2 については、上述したように、ｑが十分小さければ、“解なし”も含めて予めテーブルとして用意しておくことができ、これから（１／Ｎ1/2 ）テーブル１３を予め用意しておくことになる。
【００７１】
（１／Ｎ1/2 ）テーブル１３の作成については、（１／Ｎ1/2 ）算出部１４を利用することが可能である。（１／Ｎ1/2 ）算出部１４は、（１／Ｎ1/2 ）テーブル１３を作成する場合には、（１／Ｎ1/2 ）テーブル１３に登録するＮを順次選択して、図２に示す計算手順に従ってＮ1/2 を算出し、拡張ユークリッドの互除法に従ってＧＦ（ｑ）上の割り算を実行することで１／Ｎ1/2 を算出して、それを選択したＮと対応付ける形で（１／Ｎ1/2 ）テーブル１３に登録することで、（１／Ｎ1/2 ）テーブル１３を作成することになる。
【００７２】
この事前演算を実行すると、図１のように構成される本発明の拡大体平方根算出装置１では、先ず最初に、「Step０」で示すように、ＧＦ（ｑm ) 上の元ａを入力し、ａ＝０であるならば、解として０を出力して、処理を終了する。
【００７３】
一方、入力したａが０でない場合には、「Step１」に示す手順に従い、ｑn 乗フロベニウス写像演算手法を用いて、入力したａを起点にしてＨ2 を算出する。すなわち、
Ｈ2 ＝ａu2    ただし、ｕ2 ＝Σｑ2i（Σ：ｉ＝０〜ｍ’−１の総和）
で定義されるＨ2 を算出するのである。
【００７４】
続いて、「Step２」に示す手順に従い、ｑn 乗フロベニウス写像演算手法を用いて、算出したＨ2 からＧＦ（ｑ）ノルムＮを算出する。すなわち、
Ｈ1 ＝ａ×（Ｈ2)[q2]，  Ｎ＝Ｈ1 ×（Ｈ2)q 
という関係があるので、この関係式を使って、算出したＨ2 を用いてＮを算出するのである。
【００７５】
続いて、「Step３」で示すように、算出したＮをキーにして（１／Ｎ1/2 ）テーブル１３を検索することで、そのＮの１／Ｎ1/2 （≡Ｔ1)を検索する。このとき、“解なし”が検索される場合には、“解なし”を出力して、処理を終了する。
【００７６】
続いて、「Step４」で示すように、一般的な冪乗演算手法を用いて、算出したＨ1 のｖ0 乗となるＨ1 v0（ただし、ｖ0 ＝（ｑ＋１）／２）を算出する。
【００７７】
そして、最後に、「Step５」で示すように、検索した１／Ｎ1/2 （≡Ｔ1)と算出したＨ1 v0（≡Ｈ）とを乗算することで、入力したａの平方根を算出して出力することで、処理を終了する。すなわち、
±（ａ）1/2 ＝±Ｈ／Ｎ1/2 ＝±Ｈ×Ｔ1 
という関係があるので、この関係式を使って、入力したａの平方根を算出して出力するのである。
【００７８】
上述したように、平方根を求めるために必要だった冪乗演算は従来、約１６０ビットの有限体において、ＧＦ（ｑm ）上乗算８０回、ＧＦ（ｑm ）上自乗１６０回の合計約２４０回必要だったが、本実施形態例においては、ＧＦ（ｑm ）上乗算５回（Step１／Step２の乗算５回）、ＧＦ（ｑm ）上のｖ0 乗１回（Step４のｖ0 乗１回）、及びＧＦ（ｑ）×ＧＦ（ｑm ）の乗算１回（Step５の乗算１回）に削減されている。
【００７９】
ＧＦ（ｑm ）上のｖ0 乗は、約１６０ビット冪の冪乗のおよそ１／ｍのコストで実行可能だから、ｍ＝１７ならおよそＧＦ（ｑm ）上乗算５回、ＧＦ（ｑm ）上自乗１０回の合計約１５回と見積もってよい。従って、本発明により冪乗に必要な演算コストは合計２０回のＧＦ（ｑm ）上乗算または自乗となり、従来の合計約２４０回に比べ約１／１２にできるのである。
【００８０】
〔第２の実施形態例〕
第１の実施形態例では、ＧＦ（ｑ）ノルムＮを算出することで、ＧＦ（ｑm ）上の元の平方根をＧＦ（ｑm ）上で求める際に要する演算コストの削減を実現するという構成を採ったが、第２の実施形態例では、非特許文献１に記載される計算手順（図６に示す計算手順）における「ａ-1←ａv 」の演算の高速化を図ることで、ＧＦ（ｑm ）上の元の平方根をＧＦ（ｑm ）上で求める際に要する演算コストの削減を実現する構成を採る。
【００８１】
図４に、第２の実施形態例に従う本発明の拡大体平方根算出装置１の装置構成の一例を図示する。
【００８２】
この図に示すように、第２の実施形態例に従う場合、本発明の拡大体平方根算出装置１は、入力部２０と拡大体平方根算出部２１とを備え、さらに、この拡大体平方根算出部２１は、本発明を実現するために、ｑn 乗フロベニウス写像演算手法を用いて、入力部２０の入力したａのｖ乗となるａv を算出するａv 算出部２１０と、（ｍ−１）／２の加算連鎖に基づいて、ａv の算出にあたって必要となる冪乗演算の計算手順（後述するａU"への計算手順）を決定する加算連鎖決定部２１１と、ａv の算出にあたって必要となる冪乗演算の計算値（後述するｘv'の計算値）を記憶するｘv'テーブル２１２と、非特許文献１に記載される計算手順（図６に示す計算手順）を使って、ａv 算出部２１０の算出したａv から入力部２０の入力したａの平方根を導出する平方根導出部２１３とを備える。
【００８３】
次に、このように構成される本発明の拡大体平方根算出装置１の実現のために用いられる数学的な理論的根拠について説明する。
【００８４】
ここで、「ｑn 乗フロベニス写像」と「共役元ｘ[qn],(ｎ＝０，・・・，ｍ−１）の対称式」とについては第１の実施形態例で説明しているので、その説明を省略する。
【００８５】
（１）冪ｖのｑ進展開
拡大次数ｍを３以上の奇数とし、ｑを奇素数またはその冪とする。このとき、非特許文献１に記載される計算手順（図６に示す計算手順）のStep１.1のｖは次のように展開できる。
【００８６】
【数７】
2005063349.tif 000009
【００８７】
Ｕ',ｖ',Ｕ",ｖ" を、
Ｕ’＝Σｑi           ただし、Σはｉ＝０〜ｍ−１の総和
ｖ’＝((ｑ−１）／２k −１）／２
Ｕ”＝Σｑ2i-1        ただし、Σはｉ＝１〜（ｍ−１）／２の総和
ｖ”＝（ｑ＋１）／２
とおくと、Ｕ',ｖ',Ｕ",ｖ" は全て整数となる。
【００８８】
ｖは、
ｖ＝ｖ’Ｕ’＋ｖ”Ｕ”
であるから、ａv を計算するには、
ａv ＝ａv'U'+v"U" ＝（ａU'）v'×（ａU"）V"
を計算すればよい。ところで、Ｕ’＝（１＋ｑ）Ｕ”＋１であるから、
ａU'＝（ａU"）×（ａU"）q ×ａ
である。
【００８９】
従って、ａU"が計算できればａU'を求めることができる。また、ａU'は、ａの共役元の基本対称式
ａU'＝ａ×ａq ×ａ[q2]×・・・・×ａ[q(m-1)]
であるので、上述の通りａU'∈ＧＦ（ｑ）としてよい。
【００９０】
ｍが１より大きいとき、一般にＧＦ（ｑ）上の冪乗演算はＧＦ（ｑm ）上の冪乗演算に比べて効率的に実行することができる。また、ｑが十分小さいならば、一旦ａU'∈ＧＦ（ｑ）が求まれば、上述の通り（ａU'）v'をテーブル演算にて高速に求めることも可能である。
【００９１】
従って、ａv の演算の大部分はａU"を求める演算と、ａU"の冪乗演算（ａU"）V"とすることができる。ａU"の冪乗演算（ａU"）V"は一般的な冪乗演算法（例えばバイナリ法）を用いれば十分で、ｖ”はｖなどに比べて十分小さい冪（およそ１／ｍ）であるので冪乗演算も十分高速に（およそｍ倍の速度）実行できる。
【００９２】
（２）ｑ冪倍加算連鎖
ｍ’＝（ｍ−１）／２，ｑ2 ＝ｑ2 とすると、
ａv ＝ａv'U'+v"U" ＝（ａU'）v'×（ａU"）V"
のａU"の計算を行う際
Ｕ”＝（１＋ｑ2 ＋ｑ22＋・・・・＋ｑ2 m'-1）ｑ
であるから、次のように計算することができる。
【００９３】
【数８】
2005063349.tif 000010
【００９４】
このような計算を行う際、ｑ乗やｑ2 n 乗はフロベニウス写像を使ってＧＦ（ｑm ）上乗算に比べ高速に演算可能であるから、演算の律速段階となるのはｍ’−１回実行されるＧＦ（ｑm ）上乗算である。
【００９５】
ところで、例えばｍ’＝２n だったとすると、次のように分解できる。
【００９６】
【数９】
2005063349.tif 000011
【００９７】
これから、ａU"を計算する方法として、例えば次のような演算方法を用いることができる。
【００９８】
【数１０】
2005063349.tif 000012
【００９９】
この演算方法を用いると、ｎ回すなわちlog2ｍ’回のＧＦ（ｑm ) 上乗算でａU"を計算できる。このような計算法はたとえｍ’が２冪の数でなかったとしても一般に構成することが可能であり、例えば次のように構成する。
【０１００】
ｉ，ｊ，ｋを整数として、整数（１＝）ｍ0,・・・，ｍn ( ＝ｍ')を
ｍ0 ＝１，  ｍi ＝ｍj ＋ｍk ,(ｊ，ｋ＜ｉ）
とする。整数列ｍ0,・・・，ｍn をｍ’の加算連鎖と呼ぶ。ｍ’の加算連鎖を用いてｑ2 冪倍を含む加算連鎖
Ｍ0 ＝１，  Ｍi ＝ｑ2 mkＭj ＋Ｍk ,(ｊ，ｋ＜ｉ）
を構成することができる。このとき、
Ｍi ＝Σｑ2 i     ただし、Σはｉ＝０〜ｍi −１の総和
が成立している。
【０１０１】
このｑ2 冪倍を含む加算連鎖を用いてａU"の計算を次のように実行することができる。まずｍ’の加算連鎖ｍ0,・・・，ｍn を与える。次に示す演算によりＡn を求める。
【０１０２】
【数１１】
2005063349.tif 000013
【０１０３】
そして、この求めたＡn をｑ乗することにより
ａU"＝Ａn q 
というようにａU"を求める。
【０１０４】
ｍ’の加算連鎖の長さｎはバイナリ法などにより、最悪でもｎ≦２log2ｍ’に抑えることができる。すなわち、Ａn も最悪２log2ｍ’回程度のＧＦ（ｑm ) 上乗算で求めることができる。
【０１０５】
一般にａU"を効率良く求めたいなら、効率の良いｍ’の加算連鎖を与えればよい。上述した参考文献には、１以上１００以下の整数の加算回数に関する最適加算連鎖のＴree 図が掲載されている。そのような加算連鎖を用いることによってａU"の計算を最適化できる。
【０１０６】
図５に、以上に説明した数学的な理論的根拠に基づいて本発明の拡大体平方根算出装置１のａv 算出部２１０が実行することになる処理フローの一例を図示する。ここで、この処理フローではｍ＝１７を想定している。
【０１０７】
本発明の拡大体平方根算出装置１では、事前演算として、（ｍ−１）／２の加算連鎖に基づいて、入力されるＧＦ（ｑm ) 上の元ａから上述したａU"への算出に到る計算手順を決定するとともに、ＧＦ（ｑ）のとり得る値ｘに対応付けてｘv'の値を記憶するｘv'テーブル２１２を作成する。
【０１０８】
図５に示す処理フローでは、加算連鎖決定部２１１は、整数列１→８（ｍ’）に到る加算連鎖として、
ｍ0 ＝１
ｍ1 ＝ｍ0 ＋ｍ0   （＝２）
ｍ2 ＝ｍ1 ＋ｍ1   （＝４）
ｍ3 ＝ｍ2 ＋ｍ2   （＝８）
を決定している。
【０１０９】
この加算連鎖については、例えば、上述した参考文献に記載されるＴree 図をメモリに記録しておいて、それを参照することで決定することになる。
【０１１０】
この加算連鎖の決定に従って、ａv 算出部２１０は、図中の「Step１」に示す手順に従い、ｑn 乗フロベニウス写像演算手法を用いて、入力部２０の入力したａを起点にしてａU"（≡Ｔ1)を算出することになる。
【０１１１】
一方、第１の実施形態例の『（２）共役元ｘ[qn],(ｎ＝０，・・・，ｍ−１）の対称式』で説明したように、ｑが十分小さければ、ＧＦ（ｑ）上の任意の関数をテーブル演算等に置き換えることができる。これから、ｘv'テーブル２１２を予め用意しておくことができる。
【０１１２】
ｘv'テーブル２１２の作成については、図示しないテーブル作成機構がｘv'テーブル２１２に登録するｘ（∀ｘ∈ＧＦ（ｑ))を順次選択して、一般的な冪乗演算法（例えばバイナリ法）を使ってｘv'を算出し、それを選択したｘと対応付ける形でｘv'テーブル２１２に登録することで、ｘv'テーブル２１２を作成することになる。
【０１１３】
この事前演算を実行すると、図４のように構成される本発明の拡大体平方根算出装置１では、入力部２０がＧＦ（ｑm ) 上の元ａを入力すると、ａv 算出部２１０が処理を開始して、先ず最初に、「Step１」に示す手順に従い、ｑn 乗フロベニウス写像演算手法を用いて、入力したａを起点にしてａU"（≡Ｔ1)を算出する。すなわち、ａのＵ”乗で定義されるａU"（ただし、Ｕ”＝Σｑ2i-1（Σ：ｉ＝１〜（ｍ−１）／２の総和))を算出するのである。
【０１１４】
続いて、「Step２」に示す手順に従い、ｑn 乗フロベニウス写像演算手法を用いて、算出したａU"からａU'（≡Ｔ2)を算出する。すなわち、
ａU'＝（ａU"）×（ａU"）q ×ａ
という関係があるので、この関係式を使って、算出したａU"を用いてａU'（≡Ｔ2)を算出するのである。
【０１１５】
続いて、「Step３」で示すように、算出したａU'をキーにしてｘv'テーブル２１２を検索することで、そのａU'のｖ’乗となる値（ａU'）v'（≡Ｔ3 ）を検索する。
【０１１６】
続いて、「Step４」に示す手順に従い、一般的な冪乗演算法を用いて、算出したａU"のｖ”乗となる（ａU"）v"（≡Ｔ4 ）を算出する。
【０１１７】
そして、最後に、「Step５」で示すように、検索した（ａU'）v'と算出した（ａU"）v"とを乗算することで、入力したａのｖ乗となるａv を算出する。すなわち、
ａv ＝ａv'U'+v"U" ＝（ａU'）v'×（ａU"）V"
という関係があるので、この関係式を使って、入力したａのｖ乗となるａv を算出するのである。
【０１１８】
このようにして、ａv 算出部２１０がｑn 乗フロベニウス写像演算手法を用いて、入力部２０の入力したａのｖ乗となるａv を算出すると、平方根導出部２１３は、非特許文献１に記載される計算手順（図６に示す計算手順）を使って、ａv 算出部２１０の算出したａv から入力部２０の入力したａの平方根を導出して出力する。
【０１１９】
上述したように、平方根を求めるために必要だった冪乗演算は従来、約１６０ビットの有限体において、ＧＦ（ｑm ）上乗算８０回、ＧＦ（ｑm ）上自乗１６０回の合計約２４０回必要だったが、本実施形態例においては、ＧＦ（ｑm ）上乗算５回（Step１／Step２の乗算５回）、ＧＦ（ｑm ）上のｖ”乗１回（Step４のｖ”乗１回）、及びＧＦ（ｑ）×ＧＦ（ｑm ）の乗算１回（Step５の乗算１回）に削減されている。
【０１２０】
ＧＦ（ｑm ）上のｖ”乗は、約１６０ビット冪の冪乗のおよそ１／ｍのコストで実行可能だから、ｍ＝１７ならおよそＧＦ（ｑm ）上乗算５回、ＧＦ（ｑm ）上自乗１０回の合計約１５回と見積もってよい。従って、本発明により冪乗に必要な演算コストは合計２０回のＧＦ（ｑm ）上乗算または自乗となり、従来の合計約２４０回に比べ約１／１２にできるのである。
【産業上の利用可能性】
【０１２１】
本発明は、楕円加算などの演算を実行する際に利用できることで、情報セキュリティの分野に利用可能である。
【図面の簡単な説明】
【０１２２】
【図１】第１の実施形態例の装置構成の一例である。
【図２】（１／Ｎ1/2 ）算出部の実行する処理フローの一例である。
【図３】第１の実施形態例の処理フローの一例である。
【図４】第２の実施形態例の装置構成の一例である。
【図５】第２の実施形態例の処理フローの一例である。
【図６】従来技術の説明図である。
【符号の説明】
【０１２３】
１      拡大体平方根算出装置
１０    入力部
１１    ＧＦ（ｑ）ノルム算出部
１２    加算連鎖決定部
１３    （１／Ｎ1/2 ）テーブル
１４    （１／Ｎ1/2 ）算出部
１５    Ｈ算出部
１６    平方根算出部
２０    入力部
２１    拡大体平方根算出部
２１０  ａv 算出部
２１１  加算連鎖決定部
２１２  ｘv'テーブル
２１３  平方根導出部
【図１】
2005063349.tif 000014
【図２】
2005063349.tif 000015
【図３】
2005063349.tif 000016
【図４】
2005063349.tif 000017
【図５】
2005063349.tif 000018
【図６】
2005063349.tif 000019