(57)【要約】【課題】ペアリングの演算に必要な演算量は通常の楕円演算にくらべると非常に大きいため、その演算速度が遅い。【解決手段】本発明では、有限体の性質を用いて高速化を行う。ｒを有限体ＧＦ（ｐｋ／２）上の元、ｆをMillerのアルゴリズムで求められる有限体ＧＦ（ｐｋ）上の元とすると、ｆ’＝ｒｆを満足する有限体ＧＦ（ｐｋ）上の元ｆ’へ写像するMillerアルゴリズムよりも計算量が少ないアルゴリズム用いて計算する。逆元を求める代わりに、乗算する元のｐｋ乗を擬似逆元として求める。擬似逆元を用いることで、演算量の多いＧＦ（ｐｋ）の元どうしの乗算を多項式展開できる。多項式展開によって演算量の多い項を繰り返し計算の共通の項としてあらかじめ求めておくことで高速化を行う。【選択図】図７
2006323160.tif 000002
【特許請求の範囲】
【請求項１】
ｐは素数または素数のべき乗、ｋは偶数であって、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元ｆ’を求める擬似Miller演算部と、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するべき乗演算部とを備えるペアリング演算装置において、
ＸとＹをＧＦ（ｐｋ）上の元、Ｘ＾をＸの共役元、ｃ、ｄ、ｅ、ｇ、ｈをＧＦ（ｐ）上の元とする場合に、
ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌの逆元の代わりに
【数１】
2006323160.tif 000017
を用いること、
（ｃＸ＋ｄＹ＋ｅ）・（ｇＸ＾＋ｈ）の計算を、あらかじめＡ＝ＸＸ＾、Ｂ＝ＹＸ＾を求めて記録手段に記録しておき、ｃｇＡ＋ｄｇＢ＋ｅｇＸ＾＋ｃｈＸ＋ｄｈＹ＋ｅｈにより求めること
を特徴とする前記擬似Miller演算部と、
前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像することを特徴とする前記べき乗演算部と、
を備えるペアリング演算装置。
【請求項２】
ｐは素数または素数のべき乗、ｋは偶数であって、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元ｆ’を求める擬似Miller演算部と、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するべき乗演算部とを備えるペアリング演算装置において、
ＸとＹをＧＦ（ｐｋ）上の元、Ｘ＾をＸの共役元、ｘ、ｙ、ｃ、ｄ、ｇ、ｈをＧＦ（ｐ）上の元とする場合に、
ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌの逆元の代わりに
【数２】
2006323160.tif 000018
を用いること、
（ｃ（Ｘ−ｘ）＋ｄ（Ｙ−ｙ））・（ｇＸ＾＋ｈ）の計算を、あらかじめＣ＝（Ｘ−ｘ）Ｘ＾、Ｄ＝（Ｙ−ｙ）Ｘ＾を求めて記録手段に記録しておき、ｃｇＣ＋ｄｇＤ＋ｃｈ（Ｘ−ｘ）＋ｄｈ（Ｙ−ｙ）により求めること
を特徴とする前記擬似Miller演算部と、
前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像することを特徴とする前記べき乗演算部と、
を備えるペアリング演算装置。
【請求項３】
ｐは素数または素数のべき乗、ｋは偶数であって、擬似Miller演算部で、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元ｆ’を求め、べき乗演算部で、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するペアリング演算方法において、
ＸとＹをＧＦ（ｐｋ）上の元、Ｘ＾をＸの共役元、ｃ、ｄ、ｅ、ｇ、ｈをＧＦ（ｐ）上の元とする場合に、
前記擬似Miller演算部で、ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌの逆元の代わりに
【数３】
2006323160.tif 000019
を用いる過程と、
前記擬似Miller演算部で、（ｃＸ＋ｄＹ＋ｅ）・（ｇＸ＾＋ｈ）の計算を、あらかじめＡ＝ＸＸ＾、Ｂ＝ＹＸ＾を求めて記録手段に記録しておき、ｃｇＡ＋ｄｇＢ＋ｅｇＸ＾＋ｃｈＸ＋ｄｈＹ＋ｅｈにより求める過程と、
前記べき乗演算部で、前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像する過程と、
を有することを特徴とするペアリング演算方法。
【請求項４】
ｐは素数または素数のべき乗、ｋは偶数であって、擬似Miller演算部で、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元ｆ’を求め、べき乗演算部で、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するペアリング演算方法において、
ＸとＹをＧＦ（ｐｋ）上の元、Ｘ＾をＸの共役元、ｘ、ｙ、ｃ、ｄ、ｇ、ｈをＧＦ（ｐ）上の元とする場合に、
前記擬似Miller演算部で、ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌの逆元の代わりに
【数４】
2006323160.tif 000020
を用いる過程と、
前記擬似Miller演算部で、（ｃ（Ｘ−ｘ）＋ｄ（Ｙ−ｙ））・（ｇＸ＾＋ｈ）の計算を、あらかじめＣ＝（Ｘ−ｘ）Ｘ＾、Ｄ＝（Ｙ−ｙ）Ｘ＾を求めて記録手段に記録しておき、ｃｇＣ＋ｄｇＤ＋ｃｈ（Ｘ−ｘ）＋ｄｈ（Ｙ−ｙ）により求める過程と、
前記べき乗演算部で、前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像する過程と、
を有することを特徴とするペアリング演算方法。
【請求項５】
請求項３または４記載のペアリング演算方法の各過程をコンピュータにより実現するペアリング演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上の演算、特にセキュリティ技術を実現するための演算を利用した装置、方法、およびプログラムに関する。
【背景技術】
【０００２】
楕円曲線のペアリングを用いたＩＤ−ｂａｓｅ暗号や短署名長デジタル署名を実現する方法が提案されている（特許文献１）。
Tateペアリングによる暗号や署名の概要を図１に示す。有限体ＧＦ（ｐ）上で定義される楕円をＥ／ＧＦ（ｐ）とする。楕円Ｅ／ＧＦ（ｐ）上のＧＦ（ｐ）有理点をＰ（ｘ、ｙ）、楕円Ｅ／ＧＦ（ｐ）上のＧＦ（ｐｋ）有理点をＱ（ｘＱ、ｙＱ）とする。Tateペアリングでは、ＰとＱを入力とし、Millerアルゴリズムによって有限体ＧＦ（ｐｋ）上の元ｆを出力し、さらにべき乗演算によってｆを（ｐｋ−１）／ｍ乗することで有限体ＧＦ（ｐｋ）上の元ｅへ写像し、出力する。ここで、ｐは素数または素数のべき乗、ｍは素数かつＰ、Ｑ、ｅの位数、ｋはｍ｜（ｐｋ−１）を満足する最小の整数、ｍは（ｐ−１）の約数ではない、かつｐとｍの最大公約数は１である。
【０００３】
図２はTateペアリングを用いたペアリング演算装置１０００の機能構成例を示している。図１に示した処理を行うため、Millerアルゴリズムを用いて入力ＰとＱを有限体ＧＦ（ｐｋ）上の元ｆに変換して出力するMiller演算装置３０と、べき乗演算によって入力ｆを有限体ＧＦ（ｐｋ）上の元ｅに写像して出力するべき乗演算装置２０から構成されている。
Tateペアリングで９０％の計算量を占めるMiller演算装置３０の内部構成例を図３に、処理フロー例を図４に示す。Miller演算装置３０は、制御部１００、代入部２００、楕円上点生成部４００、楕円加算部５００、入出力部６００、ＧＦ（ｐｋ）乗算部７００、ＧＦ（ｐｋ）逆元部８５０、および記録部１９０から構成される。制御部１００は、以下に示す処理フローに沿った処理を実行するために他の構成部を制御する。また、記録部１９０はハードディスク等の不揮発性のメモリでもよいし、一連の計算を行う間だけ一時的に記録する揮発性のメモリでもよい。また、組み合わせてもよい。
【０００４】
入出力部６００にｍ、Ｐ、Ｑが入力されると、ｍ、Ｐ、Ｑを記録部１９０に記録する（Ｓ７００）。次に代入部２００で、ＴにＰを、Ｆに１を代入し、記録部１９０に記録する（Ｓ７１０）。楕円上点生成部４００で、Ｓ≠ＰかつＳ≠Ｑの条件を満足する有限体ＧＦ（ｐｋ）上で定義される楕円上の点Ｓ（∈Ｅ／ＧＦ（ｐｋ））を生成し、記録部１９０に記録する（Ｓ７２０）。Ｓは条件を満足する点であれば、あらかじめ定めてもいいし、ランダムに生成してもよい。楕円加算部５００で、記録部１９０からＱとＳを読み取り、Ｑ’（＝Ｑ＋Ｓ）を計算し、記録部１９０に記録する（Ｓ７３０）。代入部２００で、ｌｏｇ（ｍ）−１の小数点以下を切り上げた整数をｎに代入し、記録部１９０に記録する（Ｓ７４０）。制御部１００は、記録部１９０からｎを読み取り、ｎ＜０か否かを確認し、Ｙｅｓの場合にはステップＳ９１０に進み、Ｎｏの場合にはステップＳ７６０に進む（Ｓ７５０）。Ｙｅｓの場合、入出力部６００は、記録部１９０からＦを読み取り、出力し（Ｓ９１０）、Millerアルゴリズムによる演算が終了する。Ｎｏの場合、楕円加算部５００は、記録部１９０からＴを読み取り、２Ｔを計算し、記録部１９０に記録する（Ｓ７６０）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、２Ｔを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと２Ｔとを結ぶ直線、ｌ２（ｘ，ｙ）＝０を２ＴとＯとを結ぶ直線として、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算し、記録部１９０に記録する（Ｓ７７０）。ただし、ｌ１（Ｑ’）とは、Ｑ’のｘ座標とｙ座標とを、ｌ１（ｘ，ｙ）に代入した値である。なお、Ｓを有限体ＧＦ（ｐ）の元から選定すると（この場合、残りのｋ−１個の有限体ＧＦ（ｐ）の元は０である。）、ｌ１（Ｓ）、ｌ２（Ｓ）の計算は省略でき、以降のステップでｌ１（Ｓ）、ｌ２（Ｓ）を省略できる。次に、代入部２００は、記録部１９０から２Ｔを読み取り、Ｔに２Ｔの値を代入し、Ｔを記録部１９０に記録する（Ｓ７８０）。ＧＦ（ｐｋ）逆元部８５０で、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ７９０）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【０００５】
【数５】
2006323160.tif 000003
を計算し、Ｆの値として記録部１９０に記録する（Ｓ８１０）。制御部１００は、記録部１９０からｍとｎを読み取り、ｍのｎ番目のビットが１かを確認し、Ｙｅｓの場合にはステップＳ８３０へ進み、Ｎｏの場合にはステップＳ９００へ進む（Ｓ８２０）。Ｙｅｓの場合、楕円加算部５００で、記録部１９０からＴ、Ｐを読み取り、Ｔ＋Ｐを計算し、記録部１９０に記録する（Ｓ８３０）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、Ｐ，Ｔ＋Ｐを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴとＰとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ＋ＰとＯとを結ぶ直線とし、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算して、記録部１９０に記録する（Ｓ８４０）。代入部２００は、記録部１９０からＴ＋Ｐを読み取り、ＴにＴ＋Ｐを代入し、Ｔを記録部１９０に記録する（Ｓ８５０）。ＧＦ（ｐｋ）逆元部８５０は、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ８６０）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【０００６】
【数６】
2006323160.tif 000004
を計算し、Ｆの値として記録部１９０に記録する（Ｓ８８０）。ステップＳ８２０でＮｏと判断した場合とステップＳ８８０が終了した場合、代入部２００は、記録部１９０からｎを読み取り、ｎ−１をｎに代入し、ｎを記録部１９０に記録する（Ｓ９００）。次にステップＳ７５０に戻り、ステップＳ７５０の判断がＹｅｓとなるまで処理が繰り返される。
【特許文献１】特開2004-177673号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ペアリングの演算に必要な演算量は、通常の楕円演算にくらべると非常に大きいため、その演算速度が遅いことが問題となっている。Tateペアリングの場合、Millerのアルゴリズムというdevisor有理式の評価を行う演算に費やされる。本発明が解決しようとする課題は、Millerのアルゴリズムの演算速度の高速化である。
【課題を解決するための手段】
【０００８】
本発明では、有限体の性質を用いて高速化を行う。図５に本発明による演算の高速化の原理を示す。Tateペアリングでは、有限体ＧＦ（ｐｋ）上の元ｆをべき乗演算により有限体ＧＦ（ｐｋ）上の元ｅに写像するが、次の条件を満足する有限体ＧＦ（ｐｋ）上の元ｆ’も、べき乗演算により有限体ＧＦ（ｐｋ）上の元ｅに写像する。
ｆ’＝ｒｆ  ただし、ｒは有限体ＧＦ（ｐｋ／２）上の元                （１）
そこで、本発明ではｋが偶数の場合に、この有限体の性質を利用し、Millerアルゴリズムよりも計算量が少ないアルゴリズム（以下、「擬似Millerアルゴリズム」という。）で、元ｆ’を求め、元ｆ’をべき乗演算することで元ｅを求める。
【０００９】
擬似Millerアルゴリズムでは、Millerアルゴリズムで逆元を求める処理を、少ない計算量で求められる逆元のｒ倍の元（以下、「擬似逆元」という。）を求める処理に置き換える。具体的には、ｋが偶数であり、Ｌが有限体ＧＦ（ｐｋ）上の元の場合、
【００１０】
【数７】
2006323160.tif 000005
を満足する有限体ＧＦ（ｐｋ／２）上の元ｎが存在する。したがって、
【数８】
2006323160.tif 000006
であり、式（１）の関係を満足する。そこで、
【数９】
2006323160.tif 000007
を擬似逆元として使用する。
また、前記のMillerのアルゴリズムの多項式の乗算では、多項式を展開して計算する。具体的には、ステップＳ８１０とＳ８８０の多項式の乗算には、
【００１１】
【数１０】
2006323160.tif 000008
が含まれるが、前記の擬似逆元を用いると、
【数１１】
2006323160.tif 000009
に置き換えることができる。また、Ｑ’＝（ＸＱ’，ＹＱ’）とすると、
ｌ１（Ｑ’）＝ｃＸＱ’＋ｄＹＱ’＋ｅ、ｌ２（Ｑ’）＝ｇＸＱ’＋ｈ         （７）
と表すことができる。ここで、ｃ、ｄ、ｅ、ｇ、ｈはＧＦ（ｐ）上の元である。さらに、フェルマーの小定理から、
【００１２】
【数１２】
2006323160.tif 000010
と変形することができる。ここでＸ＾Ｑ’はＸＱ’の共役元である。
したがって、式（６）は、
（ｃＸＱ’＋ｄＹＱ’＋ｅ）・（ｇＸ＾Ｑ’＋ｈ）                           （９）
と表現できる。
そこで、あらかじめＡ＝ＸＱ’Ｘ＾Ｑ’、Ｂ＝ＹＱ’Ｘ＾Ｑ’を求めておき、
ｃｇＡ＋ｄｇＢ＋ｅｇＸ＾Ｑ’＋ｃｈＸＱ’＋ｄｈＹＱ’＋ｅｈ             （１０）
により計算する。
【発明の効果】
【００１３】
本発明によれば、楕円曲線上のTateペアリング演算において、ｋが偶数である場合に、有限体の性質を用いて、Ｅ／ＧＦ（ｐｋ）からＧＦ（ｐｋ）への写像を高速に行うことができる。また、本発明では、特殊な楕円曲線の性質を用いず高速化できる。さらに、任意の標数の楕円曲線に適用することが可能であり、応用範囲が広い。
【発明を実施するための最良の形態】
【００１４】
以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。
［第１実施形態］
図６に本発明のペアリング演算装置の機能構成例を示す。図２との違いはMiller演算装置３０の代わりに、擬似Miller演算装置１０が備えられていることである。擬似Miller演算装置１０は、前記の擬似逆元を用い、多項式を展開した乗算を行うことで、擬似Millerアルゴリズムを実現する装置である。擬似Miller演算装置１０の内部構成例を図７に、擬似Miller演算装置１０の処理フローを図８に示す。図７と図３との違いは、図７の記録部１５０に記録するデータの種類が、図３の記録部１９０に記録するデータの種類と異なるものがあること、擬似逆元を計算するためにＧＦ（ｐｋ）逆元部８５０が擬似ＧＦ（ｐｋ）逆元部８００に置き換えられたことである。まず、図４の説明中での「記録部１９０への記録」または「記録部１９０からの読み取り」は、図８では「記録部１５０への記録」または「記録部１５０からの読み取り」と読み替える。その他の図８の処理フローと図４の処理フローとの違いは、以下のとおりである。
【００１５】
ステップＳ７３０とステップＳ７４０との間に、ステップＳ１１０を追加している。ステップＳ１１０では、Ｑ’のｘ座標とｙ座標であるＸＱ’とＹＱ’（∈ＧＦ（ｐｋ））、およびＰのｘ座標とｙ座標であるｘＰとｙＰ（∈ＧＦ（ｐ））とを記録部１５０から読み取り、Ｘ＾Ｑ’、Ａ＝ＸＱ’Ｘ＾Ｑ’、Ｂ＝ＹＱ’Ｘ＾Ｑ’、Ｃ＝（ＸＱ’−ｘＰ）Ｘ＾Ｑ’、Ｄ＝（ＹＱ’ −ｙＰ）Ｘ＾Ｑ’を計算し、Ｘ＾Ｑ’、Ａ、Ｂ、Ｃ、Ｄを記録部１５０に記録する。
ステップＳ７７０はステップＳ１２０に置き換える。ステップＳ１２０では、ＧＦ（ｐｋ）乗算部７００が、Ｑ’、Ｓ、Ｔ、２Ｔを記録部１５０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと２Ｔとを結ぶ直線、ｌ２（ｘ，ｙ）＝０を２ＴとＯとを結ぶ直線として、ｌ１（Ｓ）、ｌ２（Ｓ）を計算し、記録部１５０に記録する。また、多項式ｌ１（ｘ，ｙ）＝ｃｘ＋ｄｙ＋ｅとｌ２（ｘ，ｙ）＝ｇｘ＋ｈの係数であるｃ、ｄ、ｅ、ｇ、ｈとを求め、記録部１５０に記録する。
【００１６】
ステップＳ７９０とステップＳ８１０は、ステップＳ１３０〜Ｓ１５０に置き換える。ステップＳ１３０では、擬似ＧＦ（ｐｋ）逆元部８００が、記録部１５０からｌ１（Ｓ）を読み取り、ｌ１（Ｓ）の擬似逆元を計算し、記録部１５０に記録する。ステップＳ１４０では、ＧＦ（ｐｋ）乗算部７００が、記録部１５０からＡ、Ｂ、ｃ、ｄ、ｅ、ｇ、ｈ、Ｑ’のｘ座標ＸＱ’とｙ座標ＹＱ’、ＸＱ’の共役元Ｘ＾Ｑ’を読み取り、（ｃＸＱ’＋ｄＹＱ’＋ｅ）・（ｇＸ＾Ｑ’＋ｈ）をｃｇＡ＋ｄｇＢ＋ｅｇＸ＾Ｑ’＋ｃｈＸＱ’＋ｄｈＹＱ’＋ｅｈのように計算し、
【００１７】
【数１３】
2006323160.tif 000011
として記録部１５０に記録する。ステップＳ１５０では、ＧＦ（ｐｋ）乗算部７００が、記録部１５０からＦ、ｌ２（Ｓ）、ｌ１（Ｓ）の擬似逆元、および
【数１４】
2006323160.tif 000012
を読み取り、
【数１５】
2006323160.tif 000013
【００１８】
を計算し、Ｆの値として記録部１５０に記録する。
ステップＳ８４０は、ステップＳ１６０に置き換えられる。ステップＳ１６０では、ＧＦ（ｐｋ）乗算部７００が、Ｑ’、Ｓ、Ｔ、Ｐ，Ｔ＋Ｐを記録部１５０から読み取り、ｌ１（ｘ，ｙ）＝０をＴとＰとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ＋ＰとＯとを結ぶ直線とし、ｌ１（Ｓ）、ｌ２（Ｓ）を計算して、記録部１５０に記録する。また、多項式ｌ１（ｘ，ｙ）＝ｃｘ＋ｄｙとｌ２（ｘ，ｙ）＝ｇｘ＋ｈの係数であるｃ、ｄ、ｇ、ｈとを求め、記録部１５０に記録する。なお、ステップＳ１６０とＳ１２０とを比べてみると、ステップＳ１６０には多項式ｌ１（ｘ，ｙ）の係数ｅがない。これは、ステップＳ１６０では、ｅ＝０となるので、省略できるからである。
【００１９】
ステップＳ８６０とステップＳ８８０は、ステップＳ１７０〜Ｓ１９０に置き換える。ステップＳ１７０では、擬似ＧＦ（ｐｋ）逆元部８００が、記録部１５０からｌ１（Ｓ）を読み取り、ｌ１（Ｓ）の擬似逆元を計算し、記録部１５０に記録する。ステップＳ１８０では、ＧＦ（ｐｋ）乗算部７００が、記録部１５０からＣ、Ｄ、ｃ、ｄ、ｇ、ｈ、Ｑ’のｘ座標ＸＱ’とｙ座標ＹＱ’、ＸＱ’の共役元Ｘ＾Ｑ’、 Ｐのｘ座標とｙ座標であるｘＰとｙＰを読み取り、（ｃＸ’＋ｄＹ’）・（ｇＸ＾Ｑ’＋ｈ）をｃｇＣ＋ｄｇＤ＋ｃｈＸ’＋ｄｈＹ’のように計算し、
【００２０】
【数１６】
2006323160.tif 000014
として記録部１５０に記録する。ただし、Ｘ’＝ＸＱ’ −ｘＰ、Ｙ’＝ＹＱ’ −ｙＰである。ステップＳ１９０では、ＧＦ（ｐｋ）乗算部７００が、Ｆ、ｌ２（Ｓ）、ｌ１（Ｓ）の擬似逆元、および
【数１７】
2006323160.tif 000015
を記録部１５０から読み取り、
【数１８】
2006323160.tif 000016
【００２１】
を計算し、Ｆの値として記録部１５０に記録する。
なお、本発明でもＳを有限体ＧＦ（ｐ）の元から選定すると（この場合、残りのｋ−１個の有限体ＧＦ（ｐ）の元は０である。）、ｌ１（Ｓ）、ｌ２（Ｓ）の計算や演算を省略できる。
このように変更した処理フローによって、Millerアルゴリズムよりも計算量を少なくし、有限体ＧＦ（ｐｋ）上の元ｆ’を求めることができる。
本発明によれば、擬似逆元を用いることで、演算量の多いＧＦ（ｐｋ）の元どうしの乗算を多項式展開できる。また、多項式展開できるため、演算量の多いＧＦ（ｐｋ）の元どうしの乗算を、多項式展開した上で、繰り返し計算に共通の項をあらかじめ計算しておくことができる。ＧＦ（ｐ）の元どうしの乗算の演算量をＯ（ｋ）と表現すると、通常ＧＦ（ｐｋ）の元どうしの乗算の演算量はＯ（ｋ２）となり、Karatsuba法などを用いた場合でもＯ（ｋ１．５）の演算量となる。一方、ＧＦ（ｐｋ）の元とＧＦ（ｐ）の元との乗算の演算量は、Ｏ（ｋ）となるため、演算量を削減することができる。特に、ｋが大きくなると本発明の効果も大きくなる。
【００２２】
なお、本発明は、コンピュータ本体とコンピュータプログラムとして実行することが可能であるし、デジタルシグナルプロセッサや専用LSIに実装して実現することも可能である。
【図面の簡単な説明】
【００２３】
【図１】Tateペアリング演算の概要を示す図。
【図２】Tateペアリングを用いたペアリング演算装置の機能構成例を示す図。
【図３】Miller演算装置の内部構成例を示す図。
【図４】Millerアルゴリズムの処理フローを示す図。
【図５】擬似Millerのアルゴリズムを用いた演算の高速化の原理を示す図。
【図６】擬似Millerアルゴリズムを用いたペアリング演算装置の機能構成例を示す図。
【図７】擬似Miller演算装置の機能構成例を示す図。
【図８】擬似Millerアルゴリズムの処理フローを示す図。
【図１】
2006323160.tif 000021
【図２】
2006323160.tif 000022
【図３】
2006323160.tif 000023
【図４】
2006323160.tif 000024
【図５】
2006323160.tif 000025
【図６】
2006323160.tif 000026
【図７】
2006323160.tif 000027
【図８】
2006323160.tif 000028