(57)【要約】【課題】  楕円曲線上のペアリング演算の高速化を図る。【解決手段】  倍算値設定手段１３において、ｗビット（ｗは２以上の自然数）で表現可能なすべての自然数ｉについて、Ｐｉ←ｉ・Ｐ（∈Ｅ（Ｆｑ））を設定し、直線設定手段１４において、各自然数ｉに対し、‐ＰｉとＰを結ぶ直線Ａi１と、ＰｉとＯ（無限遠点）を結ぶ直線Ａi２とを設定し、有理式算出手段１５において、ｆ’１＝１、ｆ’i＝ｆ’i-1・Ａi１(Ｑ＋Ｓ)・Ａi２(Ｓ)／Ａi１(Ｓ)／Ａi２(Ｑ＋Ｓ)の演算によって、各自然数ｉに対するｆ’iを算出する。そして、倍算値設定手段１３において設定されたＰｉと、有理式算出手段１５において算出されたｆ’iとを、ｉに対応付けてテーブルメモリ１６に格納しておく。そして、このテーブルメモリ１６に格納されたＰｉとｆ’iを用いることにより、それ以降のペアリング演算処理の一部をｗビット単位で実行し、処理の高速化を図る。【選択図】  図１
2005308956.tif 000002
【特許請求の範囲】
【請求項１】
ｍを素数とし、Ｅ（Ｆｑ）［ｍ］を有限体Ｆｑ上（ただしｑは有限体Ｆｑの位数を意味する。）で定義される楕円曲線Ｅ（Ｆｑ）のｍ‐等分点とし、Ｅ（Ｆｑｋ）［ｍ］を有限体乗法群Ｆｑｋ上（ただし、ｋは自然数であり、Ｆｑｋの下付添え字ｑｋはｑｋを意味する。）で定義される楕円曲線Ｅ（Ｆｑｋ）のｍ‐等分点とし、Ｐ∈Ｅ（Ｆｑ）［ｍ］とし、Ｑ∈Ｅ（Ｆｑｋ）［ｍ］とし、Ｓ∈Ｅ（Ｆｑｋ）とし、ｆｐを有限体Ｆｑの拡大体上で定義される有理式とした場合における、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの演算を行うペアリング演算装置であって、
ｍ、Ｐ、Ｑ及びＳの入力を受け付ける入力手段と、
ｗビット（ｗは２以上の自然数）で表現可能なすべての自然数ｉについて、Ｐｉ←ｉ・Ｐ（∈Ｅ（Ｆｑ））を設定する倍算値設定手段と、
上記各自然数ｉに対し、‐ＰｉとＰを結ぶ直線Ａi１と、ＰｉとＯ（無限遠点）を結ぶ直線Ａi２と、を設定する第１の直線設定手段と、
ｆ’１＝1、ｆ’i＝ｆ’i-1・Ａi１(Ｑ＋Ｓ)・Ａi２(Ｓ)／Ａi１(Ｓ)／Ａi２(Ｑ＋Ｓ)の演算によって、上記各自然数ｉに対するｆ’iを算出する第１の有理式算出手段と、
上記倍算値設定手段において設定されたＰｉと、上記第１の有理式算出手段において算出されたｆ’iとを、上記ｉに対応付けて格納するテーブルメモリと、
を有することを特徴とするペアリング演算装置。
【請求項２】
請求項１記載のペアリング演算装置であって、
Ｔ←Ｐとｆ←１の演算を行う代入手段と、
Ｔと‐２Ｔを結ぶ直線Ｂ１と、２ＴとＯ（無限遠点）を結ぶ直線Ｂ２とを、順次求める第２の直線設定手段と、
Ｔ←２Ｔ（∈Ｅ（Ｆｑ））の演算を順次行う２倍算手段と、
ｆ←ｆ２・Ｂ１(Ｑ＋Ｓ)・Ｂ２(Ｓ)／Ｂ１(Ｓ)／Ｂ２(Ｑ＋Ｓ)の演算を順次行う第２の有理式算出手段と、
ｗビットごとに区分された上記ｍのビット列から、ｗビットの区分Ｄｕ（ｕはｎ／ｗ以下の自然数）を順次抽出し、当該区分Ｄｕの値ｍ’ｕが０でなかった場合にのみ、上記テーブルメモリから、当該ｍ’ｕに対応するＰｍ’ｕ及びｆ’ｍ’ｕを抽出する抽出手段と、
上記抽出手段において抽出されたＰｍ’ｕを用い、ＴとＰｍ’ｕを結ぶ直線Ｃ１と、（Ｔ＋Ｐｍ’ｕ）とＯ（無限遠点）を結ぶ直線Ｃ２とを求める第３の直線設定手段と、
上記抽出手段において抽出されたＰｍ’ｕを用い、Ｔ←Ｔ＋Ｐｍ’ｕ（∈Ｅ（Ｆｑ））の演算を行う加算手段と、
上記抽出手段において抽出されたｆ’ｍ’ｕを用い、ｆ←ｆ・ｆ’ｍ’ｕ・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う第３の有理式算出手段と、
を有することを特徴とするペアリング演算装置。
【請求項３】
ｍを素数とし、ｎをｍのビット数とし、Ｅ（Ｆｑ）［ｍ］を有限体Ｆｑ上（ただしｑは有限体Ｆｑの位数を意味する。）で定義される楕円曲線Ｅ（Ｆｑ）のｍ‐等分点とし、Ｅ（Ｆｑｋ）［ｍ］を有限体乗法群Ｆｑｋ上（ただし、ｋは自然数であり、Ｆｑｋの下付添え字ｑｋはｑｋを意味する。）で定義される楕円曲線Ｅ（Ｆｑｋ）のｍ‐等分点とし、Ｐ∈Ｅ（Ｆｑ）［ｍ］とし、Ｑ∈Ｅ（Ｆｑｋ）［ｍ］とし、Ｓ∈Ｅ（Ｆｑｋ）とし、ｆＰを有限体Ｆｑの拡大体上で定義される有理式とした場合における、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの演算を行うペアリング演算方法であって、
入力手段において、ｍ、Ｐ、Ｑ及びＳの入力を受け付けるステップと、
第１の代入手段において、Ｐ１←Ｐとｆ’１←１とを行い、当該当該Ｐ１とｆ’１を１に対応付けてテーブルメモリに格納するステップと、
ｗビット（ｗは２以上の自然数）で表現可能なすべての自然数ｉのうち、２以上のｉについて行われる、
（ａ）倍算値設定手段において、Ｐｉ＝ｉＰ（∈Ｅ（Ｆｑ））を算出し、当該Ｐｉを上記自然数ｉに対応付けてテーブルメモリに格納し、
（ｂ）第１の直線設定手段において、上記各自然数ｉに対し、‐ＰｉとＰを結ぶ直線Ａi１と、ＰｉとＯ（無限遠点）を結ぶ直線Ａi２と、を設定し、
（ｃ）上記第１の有理式算出手段において、ｆ’i＝ｆ’i-1・Ａi１(Ｑ＋Ｓ)・Ａi２(Ｓ)／Ａi１(Ｓ)Ａi２(Ｑ＋Ｓ)の演算によって、上記各自然数ｉに対するｆ’iを算出し、当該ｆ’iを上記自然数ｉに対応付けてテーブルメモリに格納する、
ステップと、
第2の代入手段において、Ｔ←Ｐとｆ←１とを行うステップと、
ｎ／ｗ以下の最大の自然数回繰り返される、
（ｅ）第２の直線設定手段において、Ｔと‐２Ｔを結ぶ直線Ｂ１と、２ＴとＯ（無限遠点）を結ぶ直線Ｂ２とを求め、２倍算手段において、上記Ｔの２倍値２Ｔ（∈Ｅ（Ｆｑ））をＴに代入し、第２の有理式算出手段において、ｆ←ｆ２・Ｂ１(Ｑ＋Ｓ)・Ｂ２(Ｓ)／Ｂ１(Ｓ)／Ｂ２(Ｑ＋Ｓ)の演算を行う処理を、ｗ回繰り返し、
（ｆ）ｗビットごとに区分された上記ｍのビット列から、当該ｗビットの区分Ｄｕ（ｕはｎ／ｗ以下の自然数）を抽出し、
（ｇ）抽出した区分Ｄｕの値ｍ’ｕが０でなかった場合にのみ、抽出手段において、上記テーブルメモリから当該ｍ’ｕに対応するＰｍ’ｕ及びｆ’ｍ’ｕを抽出し、第３の直線設定手段において、上記抽出手段において抽出されたＰｍ’ｕを用い、ＴとＰｍ’ｕを結ぶ直線Ｃ１と、（Ｔ＋Ｐｍ’ｕ）とＯ（無限遠点）を結ぶ直線Ｃ２とを求め、加算手段において、加算値Ｔ＋Ｐｍ’ｕ（∈Ｅ（Ｆｑ））をＴに代入し、第３の有理式算出手段において、上記抽出手段において抽出されたｆ’ｍ’ｕを用い、ｆ←ｆ・ｆ’ｍ’ｕ・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う、
ステップと、
を有することを特徴とするペアリング演算方法。
【請求項４】
ｍを素数とし、Ｅ（Ｆｑ）［ｍ］を有限体Ｆｑ上（ただしｑは有限体Ｆｑの位数を意味する。）で定義される楕円曲線Ｅ（Ｆｑ）のｍ‐等分点とし、Ｅ（Ｆｑｋ）［ｍ］を有限体乗法群Ｆｑｋ上（ただし、ｋは自然数であり、Ｆｑｋの下付添え字ｑｋはｑｋを意味する。）で定義される楕円曲線Ｅ（Ｆｑｋ）のｍ‐等分点とし、Ｐ∈Ｅ（Ｆｑ）［ｍ］とし、Ｑ∈Ｅ（Ｆｑｋ）［ｍ］とし、Ｓ∈Ｅ（Ｆｑｋ）とし、ｆＰを有限体Ｆｑの拡大体上で定義される有理式とした場合における、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの演算を行うペアリング演算装置であって、
Ｐ、Ｑ、Ｓ、（√ｍ）オーダ以上の自然数ｊ、事前計算されたｊ（Ｐ）‐ｊ（Ｏ）＝（ｊＰ）‐（Ｏ）＋ｄｉｖ（ｆｊ）を満たす（Ｏは無限遠点）有理式ｆｊに対するｆ’＝ｆｊ（Ｑ＋Ｓ）／ｆｊ（Ｓ）（∈Ｆｑｋ）及び事前計算されたＰ’＝ｊＰ（∈Ｅ（Ｆｑ））を格納する第１のメモリと、
ｍ＝ｍ０＋ｍ１ｊを満たす整数ｍ０及びｍ１、Ｐ’’←Ｐ＋Ｐ’（∈Ｅ（Ｆｑ））、ｆ’’←ｆ’・Ａ１(Ｑ＋Ｓ)・Ａ２(Ｓ)／Ａ１(Ｓ)／Ａ２(Ｑ＋Ｓ)（Ａ１はＰとＰ’を結ぶ直線、Ａ２はＰ’’とＯ（無限遠点）を結ぶ直線）、Ｔ←Ｐｘ及びｆ←ｆｘ（ただし、ｍ０及びｍ１が同じビット数である場合Ｐｘ＝Ｐ’’及びｆｘ＝ｆ’’であり、 ｍ０のビット数がｍ１のビット数より大きい場合Ｐｘ=Ｐ及びｆｘ＝１であり、ｍ１のビット数がｍ０のビット数より大きい場合Ｐｘ＝Ｐ’及びｆｘ＝ｆ’である。）の値を格納する第２のメモリと、
Ｔと‐２Ｔを結ぶ直線Ｂ１と、２ＴとＯ（無限遠点）を結ぶ直線Ｂ２とを、順次求める第２の直線設定手段と、
Ｔ←２Ｔ（∈Ｅ（Ｆｑ））の演算を順次行う２倍算手段と、
ｆ←ｆ２・Ｂ１(Ｑ＋Ｓ)・Ｂ２(Ｓ)／Ｂ１(Ｓ)／Ｂ２(Ｑ＋Ｓ)の演算を順次行う第２の有理式算出手段と、
ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であった場合（ｍ０(ｉ)は上記ｍ０のｉ＋１ビット目の値、ｍ１(ｉ)は上記ｍ１のｉ＋１ビット目の値、ｉは０以上ｎ−１以下の整数、ｎはｍ０，ｍ１のうち値が大きい方のビット長）、直線Ｃ１としてＴとＰを結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ）とＯ（無限遠点）を結ぶ直線を求め、ｍ０(ｉ)＝０かつｍ１(ｉ)＝１であった場合、直線Ｃ１としてＴとＰ’を結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ’）とＯを結ぶ直線を求め、ｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合、直線Ｃ１としてＴとＰ’’を結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ’’）とＯを結ぶ直線を求める処理を、順次実行する第３の直線設定手段と、
ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であった場合、Ｔ←Ｔ＋Ｐ（∈Ｅ（Ｆｑ））の演算を行い、ｍ０(ｉ)＝０かつｍ１(ｉ)＝１であった場合、Ｔ←Ｔ＋Ｐ’（∈Ｅ（Ｆｑ））の演算を行い、ｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合、Ｔ←Ｔ＋Ｐ’’（∈Ｅ（Ｆｑ））の演算を行う処理を、順次実行する加算手段と、
ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であった場合、ｆ←ｆ・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行い、ｍ０(ｉ)＝０かつｍ１(ｉ)＝１であった場合、ｆ←ｆ・ｆ’・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行い、ｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合、ｆ←ｆ・ｆ’’・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う処理を、順次実行する第３の有理式算出手段と、
を有することを特徴とするペアリング演算装置。
【請求項５】
請求項４記載のペアリング演算装置であって、
上記第２のメモリに格納されたＰ’’、Ａ１、Ａ２、ｆ、ｆ’’及びＴは、
事前計算されたデータである、
ことを特徴とするペアリング演算装置。
【請求項６】
ｍを素数とし、Ｅ（Ｆｑ）［ｍ］を有限体Ｆｑ上（ただしｑは有限体Ｆｑの位数を意味する。）で定義される楕円曲線Ｅ（Ｆｑ）のｍ‐等分点とし、Ｅ（Ｆｑｋ）［ｍ］を有限体乗法群Ｆｑｋ上（ただし、ｋは自然数であり、Ｆｑｋの下付添え字ｑｋはｑｋを意味する。）で定義される楕円曲線Ｅ（Ｆｑｋ）のｍ‐等分点とし、Ｐ∈Ｅ（Ｆｑ）［ｍ］とし、Ｑ∈Ｅ（Ｆｑｋ）［ｍ］とし、Ｓ∈Ｅ（Ｆｑｋ）とし、ｆＰを有限体Ｆｑの拡大体上で定義される有理式とした場合における、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの演算を行うペアリング演算方法であって、
Ｐ、Ｑ、Ｓ、（√ｍ）オーダ以上の自然数ｊ、事前計算されたｊ（Ｐ）‐ｊ（Ｏ）＝（ｊＰ）‐（Ｏ）＋ｄｉｖ（ｆｊ）を満たす（Ｏは無限遠点）有理式ｆｊに対するｆ’＝ｆｊ（Ｑ＋Ｓ）／ｆｊ（Ｓ）（∈Ｆｑｋ）、及び事前計算されたＰ’＝ｊＰ（∈Ｅ（Ｆｑ））を第１のメモリに格納するステップと、
ｍ＝ｍ０＋ｍ１ｊを満たす整数ｍ０及びｍ１、Ｐ’’←Ｐ＋Ｐ’（∈Ｅ（Ｆｑ））、ｆ’’←ｆ’・Ａ１(Ｑ＋Ｓ)・Ａ２(Ｓ)／Ａ１(Ｓ)／Ａ２(Ｑ＋Ｓ)（Ａ１はＰとＰ’を結ぶ直線、Ａ２はＰ’’とＯ（無限遠点）を結ぶ直線）、Ｔ←Ｐｘ及びｆ←ｆｘ（ただし、ｍ０及びｍ１が同じビット数である場合Ｐｘ＝Ｐ’’及びｆｘ＝ｆ’’であり、 ｍ０のビット数がｍ１のビット数より大きい場合Ｐｘ=Ｐ及びｆｘ＝１であり、ｍ１のビット数がｍ０のビット数より大きい場合Ｐｘ＝Ｐ’及びｆｘ＝ｆ’である。）の値を第２のメモリに格納するステップと、
０以上ｎ−１以下（ｎはｍ０，ｍ１のうち値が大きい方のビット長）のすべての整数ｉについて、
（ａ）第２の直線設定手段において、Ｔと‐２Ｔを結ぶ直線Ｂ１と、２ＴとＯ（無限遠点）を結ぶ直線Ｂ２とを求め、
（ｂ）２倍算手段において、Ｔ←２Ｔ（∈Ｅ（Ｆｑ））の演算を行い、
（ｃ）第２の有理式算出手段において、ｆ←ｆ２・Ｂ１(Ｑ＋Ｓ)・Ｂ２(Ｓ)／Ｂ１(Ｓ)／Ｂ２(Ｑ＋Ｓ)の演算を行い、
（ｄ）ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であった場合に（ｍ０(ｉ)は上記ｍ０のｉ＋１ビット目の値、ｍ１(ｉ)は上記ｍ１のｉ＋１ビット目の値）、第３の直線設定手段において、直線Ｃ１としてＴとＰを結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ）とＯ（無限遠点）を結ぶ直線を求め、加算手段において、Ｔ←Ｔ＋Ｐ（∈Ｅ（Ｆｑ））の演算を行い、第３の有理式算出手段において、ｆ←ｆ・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行い、
（ｅ）ｍ０(ｉ)＝０かつｍ１(ｉ)＝１であった場合に、上記第３の直線設定手段において、直線Ｃ１としてＴとＰ’を結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ’）とＯを結ぶ直線を求め、上記加算手段において、Ｔ←Ｔ＋Ｐ’（∈Ｅ（Ｆｑ））の演算を行い、上記第３の有理式算出手段において、ｆ←ｆ・ｆ’・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行い、
（ｆ）ｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合に、上記第３の直線設定手段において、直線Ｃ１としてＴとＰ’’を結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ’’）とＯを結ぶ直線を求める処理を行い、上記加算手段において、Ｔ←Ｔ＋Ｐ’’（∈Ｅ（Ｆｑ））の演算を行い、上記第３の有理式算出手段において、ｆ←ｆ・ｆ’’・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う、
ステップと、
を有することを特徴とするペアリング演算方法。
【請求項７】
請求項１、２、４、５の何れかに記載のペアリング演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上の演算に関し、特に、ペアリング（Pairing）演算を行うペアリング演算装置、ペアリング演算方法、及びそのプログラムに関する。
【背景技術】
【０００２】
楕円曲線上でＩＤベース暗号方式等の公開鍵暗号やＳhort signature方式等のデジタル署名を実現する場合、Weil PairingやTate Pairingと呼ばれる写像が用いられる場合がある。
＜Weil Pairing＞
Weil Pairing（em）は、有限体Ｆｑ（ただしｑは有限体Ｆｑの位数を意味する。）上で定義される楕円曲線Ｅの２つのｍ‐等分点Ｅ［ｍ］×Ｅ［ｍ］から、有限体乗法群Ｆｑｋ（ただし、ｋは自然数であり、Ｆｑｋの下付添え字ｑｋはｑｋを意味する。）への双線形写像であり、以下のように定義される（例えば、非特許文献１、２参照。）。
【０００３】
【数１】
2005308956.tif 000003
ここで、ｍは素数であり、Ｐ∈Ｅ（Ｆｑ）［ｍ］であり、Ｑ∈Ｅ（Ｆｑｋ）［ｍ］であり、Ｓ，Ｓ’∈Ｅ（Ｆｑｋ）である。また、ＤＰ及びＤＱは、ＤＰ〜（Ｐ）‐（Ｏ），ＤＱ〜（Ｑ）‐（Ｏ）を満たし（「Ｏ」は無限遠点を示す）、不連続（disjoint）なサポート（support）を持つものを意味する（例えば、非特許文献３参照。）。さらに、ｆＰ及びｆＱは、有限体Ｆｑの拡大体上で定義される有理式であり、ｄｉｖ（ｆＰ）＝ｍＤＰ、ｄｉｖ（ｆＱ）＝ｍＤＱを満たすものとする。なお、ｄｉｖ（ｆ）とは、ｆのDivisorを意味する（例えば、非特許文献３参照。）。また有利式とは、式を整理したとき、根号のなかに文字が含まれないような代数式をいう。なお、ここでは２変数の有理式を取り扱う。さらに、ｆＰ（α）（α∈Ｅ（Ｆｑｋ）［ｍ］）とは、αの楕円曲線上の座標（ｘα，ｙα）を、有理式ｆＰの２変数（Ｘ，Ｙ）に代入することを意味する。有理式ｆＱ（α）についても同様である。
【０００４】
＜Tate Pairing＞
また、Tate Pairing（φｍ）は、以下のように定義される。
【数２】
2005308956.tif 000004
【０００５】
＜Pairingの計算法＞
Tate Pairingのうち、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）の演算を行う代表的なアルゴリズムがMillerのアルゴリズムである（例えば、非特許文献４）。そして、このMillerのアルゴリズムの出力値ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）を有限体乗法群Ｆｑｋ上で（ｑｋ‐１）／ｍ乗することで、容易にTate Pairingの演算結果を求めることができる。つまり、Tate Pairingの演算量は、ほぼMillerのアルゴリズムの演算量と等しくなる。
また、Millerのアルゴリズムを２回用いれば、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）とｆＰ（Ｐ＋Ｓ’）／ｆＰ（Ｓ’）をそれぞれ求めることができる。そのため、Millerのアルゴリズム２回と、ｆＰ（Ｐ＋Ｓ’）／ｆＰ（Ｓ’）についての有限体乗法群Ｆｑｋ上での除算１回とを行うことにより、Weil Pairingの演算結果も求めることができる。したがって、Weil Pairingの場合も、Millerのアルゴリズムの演算が演算量のほとんどを占める。
【０００６】
＜Millerのアルゴリズム＞
以下、このMillerのアルゴリズムを示す。
［Ｓｔｅｐ０］  ｍ、Ｐ∈Ｅ（Ｆｑ）［ｍ］、Ｑ∈Ｅ（Ｆｑｋ）［ｍ］、Ｓ∈Ｅ（Ｆｑｋ）を入力する。
［Ｓｔｅｐ１］  Ｔ←Ｐ，ｆ←１の代入処理を行う。
［Ｓｔｅｐ２］  For i=n-1 downto 0（ただし、ｎはｍのビット数）
［Ｓｔｅｐ２−１］  Ｔと‐２Ｔを結ぶ直Ｌ１と、２ＴとＯ（無限遠点）を結ぶ直線Ｌ２とを求める。
［Ｓｔｅｐ２−２］  Ｔ←２Ｔ（∈Ｅ（Ｆｑ）［ｍ］）の代入処理を行う。
［Ｓｔｅｐ２−３］  ｆ←ｆ２Ｌ１(Ｑ＋Ｓ)Ｌ２(Ｓ)／Ｌ１(Ｓ)／Ｌ２(Ｑ＋Ｓ)の演算を行う。
［Ｓｔｅｐ２−４］  ｍのi+1ビット目の値が１である場合にのみ、以下の処理を行う。
［Ｓｔｅｐ２−４−１］  ＴとＰを結ぶ直線Ｌ１と、（Ｔ＋Ｐ）とＯ（無限遠点）を結ぶ直線Ｌ２とを求める。
［Ｓｔｅｐ２−４−２］  Ｔ←Ｔ＋Ｐ（∈Ｅ（Ｆｑ）［ｍ］）の代入処理を行う。
［Ｓｔｅｐ２−４−３］  ｆ←ｆＬ１(Ｑ＋Ｓ)Ｌ２(Ｓ)／L１(Ｓ)／L２(Ｑ＋Ｓ) の演算を行う。
［Ｓｔｅｐ３］  ｆをｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）の演算結果として出力する。
【０００７】
図９は、このアルゴリズムの処理を概念的に説明するための図である。
図９に例示するように、この例のｍはｎビットのデータである。Ｓｔｅｐ２の処理は、このｍの最上位ビット（i=n-1）から最下位ビット（i=0）まで１ビットずつ下がりながら、各ｉについて、Ｓｔｅｐ２−１からＳｔｅｐ２−４までの処理を実行する。ここで、Ｓｔｅｐ２−１からＳｔｅｐ２−３までの処理は、各ｉすなわち各ビットについて必ず実行される処理である。これに対し、Ｓｔｅｐ２−４の処理は、対応するビットが１である場合にのみ実行される処理である。例えば、i=n-1（nビット目）の値は１であるため、Ｓｔｅｐ２−４−１からＳｔｅｐ２−４−３までの処理が実行されるが、次のi=n-2（n-1ビット目）の値は０であるため、Ｓｔｅｐ２−４−１からＳｔｅｐ２−４−３までの処理は実行されない。
【０００８】
つまり、このアルゴリズムでは、ｎ回の楕円２倍演算（Ｓｔｅｐ２−２）と、それに関連する直線Ｌ１，Ｌ２の計算（Ｓｔｅｐ２−３）、ｍのハミング重みｗＨ（ｍ）回の楕円加算（Ｓｔｅｐ２−４−２）と、それに関連する直線Ｌ１，Ｌ２の計算（Ｓｔｅｐ２−４−３）の計算を行う。
【非特許文献１】A. Menezes, Elliptic Curue Public Key Cryptosys-tem, Kluwer Academic Publishers, 1993.
【非特許文献２】J. H. Silverman, The Arithmetic of Elliptic Curves, GTM 106, Springer-Verlag, 1986.
【非特許文献３】Alfred Menezes, "Elliptic curve public key cryptosystems," Kluwer Academic Publishiers, ISBN 0-7923-9368-6, pp.28-31, pp.66-67, Third Printing 1996.
【非特許文献４】S. D. Galbraith, K. Harrison, and D. Soldera, “Implementing the Tate pairing”, ANTSV, LNCS 2369, pp.324-337, Springer-Verlag,2002.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかし、Millerのアルゴリズムは、通常の楕円演算（スカラー倍）に比較して演算量が多く、演算速度が遅いという問題点がある。
本発明はこのような点に鑑みてなされたものであり、Pairingの演算を高速に行うことが可能なペアリング演算装置を提供することを目的とする。
また、本発明の他の目的は、Pairingの演算を高速に行うことが可能なペアリング演算方法を提供することである。
【課題を解決するための手段】
【００１０】
第１の本発明では、上記課題を解決するために、
ｍを素数とし、Ｅ（Ｆｑ）［ｍ］を有限体Ｆｑ上（ただしｑは有限体Ｆｑの位数を意味する。）で定義される楕円曲線Ｅ（Ｆｑ）のｍ‐等分点とし、Ｅ（Ｆｑｋ）［ｍ］を有限体乗法群Ｆｑｋ上（ただし、ｋは自然数であり、Ｆｑｋの下付添え字ｑｋはｑｋを意味する。）で定義される楕円曲線Ｅ（Ｆｑｋ）のｍ‐等分点とし、Ｐ∈Ｅ（Ｆｑ）［ｍ］とし、Ｑ∈Ｅ（Ｆｑｋ）［ｍ］とし、Ｓ∈Ｅ（Ｆｑｋ）とし、ｆｐを有限体Ｆｑの拡大体上で定義される有理式とした場合における、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの演算を行うペアリング演算装置であって、
ｍ、Ｐ、Ｑ及びＳの入力を受け付ける入力手段と、
ｗビット（ｗは２以上の自然数）で表現可能なすべての自然数ｉについて、Ｐｉ←ｉ・Ｐ（∈Ｅ（Ｆｑ））を設定する倍算値設定手段と、
各自然数ｉに対し、‐ＰｉとＰを結ぶ直線Ａi１と、ＰｉとＯ（無限遠点）を結ぶ直線Ａi２と、を設定する第１の直線設定手段と、
ｆ’１＝１、ｆ’i＝ｆ’i-1・Ａi１(Ｑ＋Ｓ)・Ａi２(Ｓ)／Ａi１(Ｓ)／Ａi２(Ｑ＋Ｓ)の演算によって、各自然数ｉに対するｆ’iを算出する第１の有理式算出手段と、
倍算値設定手段において設定されたＰｉと、第１の有理式算出手段において算出されたｆ’iとを、ｉに対応付けて格納するテーブルメモリと、
を有するペアリング演算装置が提供される。
【００１１】
ここで、テーブルメモリに格納されたＰｉとｆ’iは、ｗビット（ｗは２以上の自然数）で表現可能なすべての自然数ｉについて設定されたものである。従って、このテーブルメモリに格納されたＰｉとｆ’iを用いることにより、それ以降のペアリング演算処理の一部をｗビット単位で実行することができる。
また、第２の本発明では、Ｐ、Ｑ、Ｓ、（√ｍ）オーダ以上の自然数ｊ、事前計算されたｊ（Ｐ）‐ｊ（Ｏ）＝（ｊＰ）‐（Ｏ）＋ｄｉｖ（ｆｊ）を満たす（Ｏは無限遠点）有理式ｆｊに対するｆ’＝ｆｊ（Ｑ＋Ｓ）／ｆｊ（Ｓ）（∈Ｆｑｋ）及び事前計算されたＰ’＝ｊＰ（∈Ｅ（Ｆｑ））を格納する第１のメモリと、
ｍ＝ｍ０＋ｍ１ｊを満たす整数ｍ０及びｍ１、Ｐ’’←Ｐ＋Ｐ’（∈Ｅ（Ｆｑ））、ｆ’’←ｆ’・Ａ１(Ｑ＋Ｓ)・Ａ２(Ｓ)／Ａ１(Ｓ)／Ａ２(Ｑ＋Ｓ)（Ａ１はＰとＰ’を結ぶ直線、Ａ２はＰ’’とＯ（無限遠点）を結ぶ直線）、Ｔ←Ｐｘ及びｆ←ｆｘ（ただし、ｍ０及びｍ１が同じビット数である場合Ｐｘ＝Ｐ’’及びｆｘ＝ｆ’’であり、ｍ０のビット数がｍ１のビット数より大きい場合Ｐｘ=Ｐ及びｆｘ＝１であり、ｍ１のビット数がｍ０のビット数より大きい場合Ｐｘ＝Ｐ’及びｆｘ＝ｆ’である。）の値を格納する第２のメモリと、
Ｔと‐２Ｔを結ぶ直線Ｂ１と、２ＴとＯ（無限遠点）を結ぶ直線Ｂ２とを、順次求める第２の直線設定手段と、
Ｔ←２Ｔ（∈Ｅ（Ｆｑ））の演算を順次行う２倍算手段と、
ｆ←ｆ２・Ｂ１(Ｑ＋Ｓ)・Ｂ２(Ｓ)／Ｂ１(Ｓ)／Ｂ２(Ｑ＋Ｓ)の演算を順次行う第２の有理式算出手段と、
ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であった場合（ｍ０(ｉ)は上記ｍ０のｉ＋１ビット目の値、ｍ１(ｉ)は上記ｍ１のｉ＋１ビット目の値、ｉは０以上ｎ−１以下の整数、ｎはｍ０，ｍ１のうち値が大きい方のビット長）、直線Ｃ１としてＴとＰを結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ）とＯ（無限遠点）を結ぶ直線を求め、ｍ０(ｉ)＝０かつｍ１(ｉ)＝１であった場合、直線Ｃ１としてＴとＰ’を結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ’）とＯを結ぶ直線を求め、ｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合、直線Ｃ１としてＴとＰ’’を結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ’’）とＯを結ぶ直線を求める処理を、順次実行する第３の直線設定手段と、
ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であった場合、Ｔ←Ｔ＋Ｐ（∈Ｅ（Ｆｑ））の演算を行い、ｍ０(ｉ)＝０かつｍ１(ｉ)＝１であった場合、Ｔ←Ｔ＋Ｐ’（∈Ｅ（Ｆｑ））の演算を行い、ｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合、Ｔ←Ｔ＋Ｐ’’（∈Ｅ（Ｆｑ））の演算を行う処理を、順次実行する加算手段と、
ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であった場合、ｆ←ｆ・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行い、ｍ０(ｉ)＝０かつｍ１(ｉ)＝１であった場合、ｆ←ｆ・ｆ’・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行い、ｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合、ｆ←ｆ・ｆ’’・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う処理を、順次実行する第３の有理式算出手段と、
を有するペアリング演算装置が提供される。
【００１２】
ここで、Ｔは、ｍのｊビット以上のビット列の処理及びｊビット未満のビット列の処理双方に対応する。そして、２倍算手段におけるＴ←２Ｔ（∈Ｅ（Ｆｑ））の演算は、ｍのｊビット以上のビット列に対応する楕円２倍算と、ｊビット未満のビット列に対応する楕円２倍算とを同時に並列的に行う演算となる。そして、それに対応する第２の直線設定手段及び第２の有理式算出手段の処理も、ｊビット以上のビット列に対応する処理と、ｊビット未満のビット列に対応する処理との並列処理に相当する。
またｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合に第３の直線設定手段、加算手段及び第３の有理式算出手段において行われる処理も、ｊビット以上のビット列に対応する処理と、ｊビット未満のビット列に対応する処理とを並列的に行う処理となる。
【発明の効果】
【００１３】
以上のように第１の本発明では、ペアリング演算処理の一部をｗビット単位で実行することが可能となるため、Pairingの演算を高速に行うことができる。
また、第２の本発明では、ｍのｊビット以上のビット列に対応する処理と、ｊビット未満のビット列に対応する処理とを並列的に行うため、Pairingの演算を高速に行うことができる。
【発明を実施するための最良の形態】
【００１４】
以下、この発明の実施の形態を図面を参照して説明する。
〔第１の実施の形態〕
まず、本発明における第１の実施の形態について説明する。
＜定義＞
まず、本形態で用いる用語を定義する。
ｍ：素数
ｎ：ｍのビット数
整数δのビット数：整数δの絶対値を２進数表記する場合の最小の桁数を意味する。例えば、整数５の絶対値５を２進表記すると（１０１）２となり、それを表記する最小の桁数は３であるため、整数５のビット数は３となる。
【００１５】
Ｅ（Ｆｑ）［ｍ］：有限体Ｆｑ上（ただしｑは有限体Ｆｑの位数を意味する。）で定義される楕円曲線Ｅ（Ｆｑ）のｍ‐等分点。
Ｅ（Ｆｑｋ）［ｍ］：有限体乗法群Ｆｑｋ上（ただし、ｋは自然数であり、Ｆｑｋの下付添え字ｑｋはｑｋを意味する。）で定義される楕円曲線Ｅ（Ｆｑｋ）のｍ‐等分点。
Ｐ：Ｐ∈Ｅ（Ｆｑ）［ｍ］
Ｑ：Ｑ∈Ｅ（Ｆｑｋ）［ｍ］
Ｓ：Ｓ∈Ｅ（Ｆｑｋ）
Ｏ：無限遠点
ｆＰ：有限体Ｆｑの拡大体上で定義される有理式であり、ｄｉｖ（ｆＰ）＝ｍＤＰを満たすもの。
【００１６】
ｆＱ：有限体Ｆｑの拡大体上で定義される有理式であり、ｄｉｖ（ｆＱ）＝ｍＤＱを満たすもの。
ｄｉｖ（ｆ）：ｆのDivisor
有理式：式を整理したとき、根号のなかに文字が含まれないような代数式。ここでは２変数の有理式を取り扱う。
ｆＰ（α）（α∈Ｅ（Ｆｑｋ）［ｍ］）：αの楕円曲線上の座標（ｘα，ｙα）を、有理式ｆＰの２変数（Ｘ，Ｙ）に代入する演算。
ｆＱ（α）（α∈Ｅ（Ｆｑｋ）［ｍ］）：αの楕円曲線上の座標（ｘα，ｙα）を、有理式ｆＱの２変数（Ｘ，Ｙ）に代入する演算。
【００１７】
＜構成＞
図１は、本形態におけるペアリング装置１の機能構成を例示したブロック図である。
図１に例示するように、本形態のペアリング装置１は、入力手段１０、メモリ１１、代入手段１２（「第１の代入手段」「倍算値設定手段」「第１の有理式算出手段」に相当）、倍算値設定手段１３、直線設定手段１４（「第１の直線設定手段」に相当）、有理式算出手段１５（「第１の有理式算出手段」に相当）、テーブルメモリ１６、代入手段１７（「第２の代入手段」に相当）、メモリ１８、２倍算手段１９、直線設定手段２０（「第２の直線設定手段」に相当）、有理式算出手段２１（「第２の有理式算出手段」に相当）、区分値算出手段２２、抽出手段２３、直線設定手段２４（「第３の直線設定手段」に相当）、加算手段２５、有理式算出手段２６（「第３の有理式算出手段」）、メモリ２７及び制御手段２８を有している。
【００１８】
なお、本形態におけるペアリング装置１は、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）等から構成される公知のコンピュータに、所定のプログラムを実行させることにより構築されるものである。また、図１における矢印は情報の流れを例示している。さらに、制御手段２８はペアリング装置１全体の制御を行うものであるが、図１では、この制御手段２８に係る情報の流れの記載を省略してある。
【００１９】
＜処理＞
次に、本形態におけるペアリング装置１の処理方法について説明する。
図２及び図３は、本形態におけるペアリング装置１の処理方法を説明するためのフローチャートである。
本形態におけるペアリング装置１は、ｍ、Ｐ、Ｑ、Ｓの入力に対し、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの演算を行う。以下、図２及び図３のフローチャートに沿って、ペアリング装置１の処理方法を説明する。
［ステップＳ１］
入力手段１０において、ｍ、Ｐ、Ｑ及びＳの入力を受け付け、それらをメモリ１１に格納する。そして、ステップＳ２に進む。
【００２０】
［ステップＳ２］
代入手段１２において、メモリ１１からＰを抽出し、Ｐ１←Ｐとｆ’１←１の代入演算を行う。その後、代入手段１２は、Ｐ１及びｆ’１をテーブルメモリ１６に送り、これらをｉ＝１に対応付けて、このテーブルメモリ１６に格納する。また、ｆ’１は、有理式算出手段１５にも送られる。そして、次のステップＳ３に進む。
［ステップＳ３］
制御手段２８において、ｉに２を代入し、次のステップＳ４に進む。
【００２１】
［ステップＳ４］
倍算値設定手段１３において、メモリ１１からＰを抽出し、Ｐｉ＝ｉＰ（∈Ｅ（Ｆｑ））を算出する。算出されたＰｉは、テーブルメモリ１６に送られ、そこでｉに対応つけられて格納される。また、算出されたＰｉは、直線設定手段１４にも送られ、次のステップＳ５の処理に進む。
［ステップＳ５］
直線設定手段１４において、メモリ１１からＰを抽出し、‐ＰｉとＰを結ぶ直線Ａi１とＰｉとＯ（無限遠点）を結ぶ直線Ａi２とを設定し、設定された直線Ａi１，Ａi２を有理式算出手段１５に送る。そして、ステップＳ６の処理に移る。
【００２２】
［ステップＳ６］
有理式算出手段１５において、メモリ１１からＱ，Ｓを抽出し、ｆ’i＝ｆ’i-1・Ａi１(Ｑ＋Ｓ)・Ａi２(Ｓ)／Ａi１(Ｓ)Ａi２(Ｑ＋Ｓ)（ｆ’1=1）の演算によって、ｉに対するｆ’iを算出する。このように設定されたｆ’iは、テーブルメモリ１６に送られ、そこでｉに対応つけられて格納される。そして、次のステップＳ７に進む。
［ステップＳ７］
制御手段２８において、ｉ＝２ｗ−１であるか否か判断する。ここでｗは２以上の自然数であり、予め設定された定数である。また、本実施例ではｗがｎを割り切るものとする（ｗ｜ｎ）。ここで、ｉ＝２ｗ−１であると判断された場合には、ステップＳ９に進み、ｉ＝２ｗ−１でないと判断された場合には、ステップＳ８に進む。すなわち、ステップＳ４からＳ６までの処理は、ｗビットで表現可能なすべての自然数ｉのうち、２以上の自然数ｉについて行われる。
【００２３】
［ステップＳ８］
制御手段２８において、ｉ←ｉ＋１の演算を行い、ステップＳ４に戻る。
［ステップＳ９］
ここまでの処理により、代入手段１２及び倍算値設定手段１３において、ｗビットで表現可能なすべての自然数ｉについて、Ｐｉ←ｉ・Ｐ（∈Ｅ（Ｆｑ））が設定され、代入手段１２及び有理式算出手段１５において、ｗビットで表現可能なすべての自然数ｉについてのｆ’iが設定されたことになる。また、テーブルメモリ１６には、ｗビットで表現可能なすべての自然数ｉについて、代入手段１２或いは倍算値設定手段１３において設定されたＰｉと、代入手段１２或いは有理式算出手段１５において設定されたｆ’iとが、当該ｉに対応付けられて格納されていることになる。
【００２４】
本ステップでは、代入手段１７において、メモリ１１からＰを抽出し、Ｔ←Ｐとｆ←１の代入演算を行う。この代入結果Ｔはメモリ１８に送られ、そこに格納され、代入結果ｆは有理式算出手段２１に送られる。そして、次のステップＳ１０に進む。
［ステップＳ１０］
制御手段２８において、ｊにｎ−１を代入し、ステップＳ１１に進む。
［ステップＳ１１］
制御手段２８において、ｚに１を代入し、ステップＳ１２に進む。
【００２５】
［ステップＳ１２］
直線設定手段２０において、メモリ１８からＴを抽出し、Ｔと‐２Ｔを結ぶ直線Ｂ１と、２ＴとＯ（無限遠点）を結ぶ直線Ｂ２とを求める。求められた直線Ｂ１及び直線Ｂ２は有理式算出手段２１に送られ、次のステップＳ１３に進む。
［ステップＳ１３］
２倍算手段１９において、メモリ１８からＴを抽出し、このＴの２倍値２Ｔ（∈Ｅ（Ｆｑ））をＴに代入し、代入値Ｔをメモリ１８に上書き（メモリ１８に記憶されたＴの値を代入値Ｔによって更新）する。そして、ステップＳ１４に進む。
【００２６】
［ステップＳ１４］
有理式算出手段２１において、ｆ←ｆ２・Ｂ１(Ｑ＋Ｓ)・Ｂ２(Ｓ)／Ｂ１(Ｓ)／Ｂ２(Ｑ＋Ｓ)の演算を行い、その演算結果ｆをメモリ２７に格納する。そして、ステップＳ１５に進む。
［ステップＳ１５］
制御手段２８において、ｚ＝ｗであるか否かを判断する。ここで、ｚ＝ｗであった場合、ステップＳ１７に進む。一方、ｚ＝ｗでなかった場合には、ステップＳ１６に進む。すなわち、ステップＳ１２からＳ１４までの処理が、各ｊごとにｗ回繰り返される。
【００２７】
［ステップＳ１６］
制御手段２８において、ｚ←ｚ＋１の演算を行い、ステップＳ１２に進む。
［ステップＳ１７］
区分値算出手段２２において、メモリ１１からｍを抽出し、m’u←Σjg=j-w+1 m(g)・2g-j+w-1の演算を行う。ここで、m(g)は、ｍのビット列の下位から数えてｇ＋１ビット目の値を示す。すなわち、この演算は、ｗビットごとに区分されたｍのビット列から、当該ｗビットの区分Ｄｕ（ｕはｎ／ｗ以下の自然数）を抽出し、その区分Ｄｕの値m’uを求める処理に相当する。求められたm’uは抽出手段２３に送られ、次のステップＳ１８の処理に進む。
【００２８】
［ステップＳ１８］
抽出手段２３において、区分値算出手段２２から送られたm’uが０であるか否かを判断する。ここで、区分Ｄｕの値ｍ’ｕが０でなかった場合にはステップＳ１９に進み、ｍ’ｕが０であった場合にはステップＳ２２に進む。
［ステップＳ１９］
抽出手段２３において、テーブルメモリ１６から当該ｍ’ｕに対応するＰｍ’ｕ及びｆ’ｍ’ｕを抽出する。すなわち、当該ｍ’ｕをキーとしてテーブルメモリ１６のｉ値を検索し、当該ｍ’ｕに一致したｉに関連付けられているＰｉをＰｍ’ｕとして抽出し、このｉに関連付けられているｆ’ｉをｆ’ｍ’ｕとして抽出する。抽出されたＰｍ’ｕは、直線設定手段２４及び加算手段２５に送られ、ｆ’ｍ’ｕは、有理式算出手段１５に送られる。そして、ステップＳ２０に進む。
【００２９】
［ステップＳ２０］
直線設定手段２４において、メモリ１８からＴを抽出し、このＴと、抽出手段２３において抽出されたＰｍ’ｕを用い、ＴとＰｍ’ｕを結ぶ直線Ｃ１と、（Ｔ＋Ｐｍ’ｕ）とＯ（無限遠点）を結ぶ直線Ｃ２とを求める。求められた直線Ｃ１と直線Ｃ２は、有理式算出手段２６に送られ、次のステップＳ２１の処理に進む。
［ステップＳ２１］
加算手段２５において、メモリ１８からＴを抽出し、Ｔ＋Ｐｍ’ｕ（∈Ｅ（Ｆｑ））の演算
を行い、この加算値Ｔ＋Ｐｍ’ｕ（∈Ｅ（Ｆｑ））をＴに代入する。そして、加算手段２５は、この代入結果Ｔによってメモリ１８を上書きする。そして、次のステップＳ２２に進む。
【００３０】
［ステップＳ２２］
有理式算出手段２６において、メモリ２７からｆを抽出し、このｆと、抽出手段２３において抽出されたｆ’ｍ’ｕと、直線設定手段２４から送られた直線Ｃ１,Ｃ２を用い、ｆ←ｆ・ｆ’ｍ’ｕ・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う。この演算結果ｆはメモリ２７に送られ、そこに上書きされる。そしてステップＳ２３に進む。
［ステップＳ２３］
制御手段２８において、ｊ←ｊ‐ｗの演算を行い、ステップＳ２４に進む。
【００３１】
［ステップＳ２４］
制御手段２８において、ｊ＜０であるか否かを判断する。ここで、ｊ＜０でなければステップＳ１１に戻り、ｊ＜０であればステップＳ２５に進む。すなわち、ステップＳ１１からＳ２４までの処理は、ｎ／ｗ以下の最大の自然数回繰り返される。
［ステップＳ２５］
有理式算出手段２６において、メモリ２７からｆを抽出して出力する。本実施例では、ｗがｎを割り切ることとしていたため、このｆがｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの値となる。
【００３２】
＜概念的説明＞
次に、ステップＳ１０からＳ２４までの処理を概念的に説明する。
図４は、本形態のｗ＝３の場合におけるｍのビット列１００の例示である。
図４に例示するように、この例のｍはｎビットのビット列１００で表現される。また、本形態ではｗがｎを割り切るため、このビット列１００はｗ（＝ｗ）ビットごとの区分（Ｄｕ）１０１−ｕ（ｕ＝１,２,...,β：βはｎ／ｗ以下の最大の自然数）に区分けできる。
【００３３】
ステップＳ１０、Ｓ２３、Ｓ２４で用いたｊは、このビット列１００のビット位置に対応する。具体的には、ｊは、ビット列１００の最下位ビットからｊ＋１ビット目のビットに対応する。そして、ステップＳ２３に示すように、ｊの値はｗステップ減少するため、各ｊは各区分（Ｄｕ）１０１−ｕの最上位ビットに対応し、ステップＳ１１からＳ２２の処理は、各ｊに対応するビットを最上位ビットに持つ区分（Ｄｕ）１０１−ｕについての処理に相当する。
また、ステップＳ１１、Ｓ１５、Ｓ１６で用いたｚは、各区分（Ｄｕ）１０１−ｕ内の各ビットに対応する。そして、ステップＳ１１、Ｓ１５、Ｓ１６が示すように、ステップＳ１２からＳ１４の処理は、ｗ回、即ち各区分（Ｄｕ）１０１−ｕ内のビット数分だけ繰り返される。そして、ステップＳ１１からＳ１６の処理が、各区分（Ｄｕ）１０１−ｕについて行われるのであるから、ステップＳ１２からＳ１４の処理は、ｗ×ｕ回、即ちｎ回（ｍの全ビットに対し）行われる。
【００３４】
さらに、ステップＳ１７で求められる値m’uは、各区分（Ｄｕ）１０１−ｕのビット列が示す値m’uを求める。例えば、区分（Ｄ１）１０１−１のビット列「（１０１）２」が示す値m’１は、１・２２＋０・２１＋１・２０＝４＋１＝５となる。
そして、ステップＳ１９の処理は、各区分（Ｄｕ）１０１−ｕのビット列が示す値m’uが０でない場合に限り、このm’uに対応する（オンライン事前計算された）Ｐｍ’ｕ及びｆ’ｍ’ｕをテーブルメモリ１６から抽出する処理である。例えば、区分（Ｄ１）１０１−１の場合、このビット列が示す値m’１＝５に対応するＰ５,ｆ’５が、それぞれＰｍ’１及びｆ’ｍ’１として抽出される。そして、ステップＳ２０からＳ２２では、これらの抽出値を用いて各種処理を行う。一方、区分（Ｄ３）１０１−３のように区分（Ｄｕ）１０１−ｕのビット列が示す値m’uが０であった場合には、ステップＳ１９からＳ２２の処理は行われない。
つまり、本形態の処理により、従来のMillerのアルゴリズムと同等の演算が実行されたことになる。
【００３５】
＜本形態の特徴＞
以上説明した通り、本形態では、まず、ｗビットで表現可能なすべての自然数ｉ、すなわち各区分（Ｄｕ）１０１−ｕが採り得るすべての値に対応するＰｉとｆ’iを求め、これらをｉに関連つけてテーブルメモリ１６に格納しておく（ステップＳ１からＳ６）。そして、このテーブルメモリ１６に格納されたＰｉとｆ’iを用い、従来のMillerのアルゴリズム（〔技術背景〕＜Millerのアルゴリズム＞の欄参照。）の［Ｓｔｅｐ２−４］の処理を、ｗビットごとまとめて実行する（ステップＳ１７からＳ２４）。その結果、従来ビットごとに行われていたビット値判定、楕円加算及びそれに関係する直線を求める演算の回数を大幅に低減させることができる。
【００３６】
以下、従来のMillerのアルゴリズムと本形態のアルゴリズムとの計算量の違いを示す。
なお、以下では、楕円加算演算量をＴＡＤＤとし、楕円２倍演算量をＴＤＢＬとする。また、ｍがｎビットのランダムな数であると仮定した場合における、従来のMillerのアルゴリズムの演算量をＭＩＬＬＥＲとし、本形態のアルゴリズムの演算量をｗＭＩＬＬＥＲとする。さらに、Ｆｑ上の乗算、自乗の演算量を、それぞれＭ,Ｓと示し、Ｆｑｋ上の乗算、自乗の演算量を、それぞれＭｋ,Ｓｋと示す。
［従来のMillerのアルゴリズムの計算量］
ＴＡＤＤ＝４Ｍｋ＋（６ｋ＋１０）Ｍ＋４Ｓ
ＴＤＢＬ＝４Ｍｋ＋２Ｓｋ＋（６ｋ＋７）Ｍ＋７Ｓ
ＭＩＬＬＥＲ＝ｎＴＤＢＬ＋（ｎ／２）ＴＡＤＤ
［本形態のアルゴリズムの計算量］
ＴＡＤＤ≒（４ｋ２＋６ｋ＋１４）Ｍ
ＴＤＢＬ≒（６ｋ２＋６ｋ＋１４）Ｍ
ｗＭＩＬＬＥＲ＝ｎＴＤＢＬ＋（（（２ｗ‐１）／２ｗ）・（ｎ／ｗ）＋２ｗ‐２）ＴＡＤＤ
ただし、ここではｋが比較的小さい値である（supersingularな楕円曲線の場合、ｋ＝２,３,６）ことを考慮し、Ｍｋ≒ｋ２Ｍと近似し、Ｓ＝Ｍしている。
【００３７】
また、一例として、ｋ＝６、ｎ＝１７０、ｗ＝４の場合を想定すると、
ＭＩＬＬＥＲ＝６１７１０Ｍ
ｗＭＩＬＬＥＲ＝５５６６６Ｍ
となり、本形態のアルゴリズムでは９．８％の演算量が削減できることが分かる。
なお、本形態では、ｗがｎを割り切る場合について説明したが、ｗがｎを割り切らない場合には、本形態の処理と従来のMillerのアルゴリズムとを組み合わせてｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの演算を行う。すなわち、ｎ／ｗの剰余がγであった場合、ｎ‐γビット分の処理に本形態のアルゴリズムを適用し、残りのγビット分の処理に従来のMillerのアルゴリズムを適用することになる。
【００３８】
また、ステップＳ１１からＳ１６に示したように、本形態のアルゴリズムでは、楕円２倍演算（ステップＳ１３）を必ずｗ回ずつ連続して行うことになる。また、文献「T. Izu and T. Takagi, “Efficient Computations of the Tate Pairing for the Large MOV     Degrees” ICISC 2002, LNCS 2587, pp283-297, Springer-Verlag,2003.」には、連続する楕円２倍算の高速化が提案されている。よって、この文献の連続する楕円２倍算の高速化手法を本形態の楕円２倍演算に適用することにより、さらなる演算の効率化を図ることができる。
【００３９】
〔第２の実施の形態〕
次に、本発明における第２の実施の形態について説明する。なお、本形態において第１の実施の形態と共通する事項については説明を省略する。
＜定義＞
第１の実施の形態と異なるのは、ｎの定義である。すなわち、本形態では、ｍ＝ｍ０＋ｍ１ｊを満たす整数ｍ０及びｍ１のうち、値が大きいほうのビット数をｎとする。
＜構成＞
図５は、本形態におけるペアリング装置２００の機能構成を例示したブロック図である。
【００４０】
図５に例示するように、本形態のペアリング装置２００は、メモリ２１１（「第１のメモリ」に相当）、加算手段２１２、直線設定手段２１３、有理式算出手段２１４、代入手段２１５、メモリ２１６（「第２のメモリ」に相当）、入力手段２１７、分割手段２１８、直線設定手段２１９（「第２の直線設定手段」に相当）、２倍算手段２２０、有理式算出手段２２１（「第２の有理式算出手段」に相当）、加算手段２２２（「第２の加算手段」に相当）、直線設定手段２２３（「第３の直線設定手段」に相当）、有理式算出手段２２４（「第３の有理式算出手段」に相当）及び制御手段２２５を有している。
【００４１】
なお、本形態におけるペアリング装置２００は、ＣＰＵ、ＲＡＭ、ＲＯＭ等から構成される公知のコンピュータに、所定のプログラムを実行させることにより構築されるものである。また、図５における矢印は情報の流れを例示している。さらに、制御手段２２５はペアリング装置２００全体の制御を行うものであるが、図５では、この制御手段２２５に係る情報の流れの記載を省略してある。
【００４２】
＜処理＞
次に、本形態におけるペアリング装置２００の処理方法について説明する。
図６及び図７は、本形態におけるペアリング装置２００の処理方法を説明するためのフローチャートである。
本形態におけるペアリング装置２００は、ｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの演算を行う。以下、図６及び図７のフローチャートに沿って、ペアリング装置２００の処理方法を説明する。
［ステップＳ３０］
例えば前処理として、Ｐ、Ｑ、Ｓ、（√ｍ）オーダ以上の自然数ｊ、（オフライン）事前計算されたｊ（Ｐ）‐ｊ（Ｏ）＝（ｊＰ）‐（Ｏ）＋ｄｉｖ（ｆｊ）を満たす（Ｏは無限遠点）有理式ｆｊに対するｆ’＝ｆｊ（Ｑ＋Ｓ）／ｆｊ（Ｓ）（∈Ｆｑｋ）、及び事前計算されたＰ’＝ｊＰ（∈Ｅ（Ｆｑ））をメモリ２１１に格納する。なお、ｆ’＝ｆｊ（Ｑ＋Ｓ）／ｆｊ（Ｓ）（∈Ｆｑｋ）は、例えば、従来のMillerのアルゴリズム或いは第１の実施の形態のアルゴリズムによって算出する（ｎをｊと置き換えたアルゴリズム）。そして、次のステップＳ３２に進む。
【００４３】
［ステップＳ３１］
入力手段２１７においてｍの入力を受け付ける。入力されたｍは分割手段２１８に送られ、次のステップＳ３２に進む。
［ステップＳ３２］
分割手段２１８において、メモリ２１１からｊを抽出し、ｍ＝ｍ０＋ｍ１ｊを満たす整数ｍ０,ｍ１を算出する。算出された整数ｍ０,ｍ１はメモリ２１６に送られて格納され、次のステップＳ３３に進む。
【００４４】
［ステップＳ３３］
加算手段２１２においてメモリ２１１からＰ,Ｐ’を抽出し、Ｐ’’←Ｐ＋Ｐ’の演算を行う。算出されたＰ’’は直線設定手段２１３に送られるとともに、メモリ２１６にも送られ、メモリ２１６内に格納される。そして、ステップＳ３４に進む。
［ステップＳ３４］
直線設定手段２１３において、メモリ２１１からＰ及びＰ’を抽出し、ＰとＰ’を結ぶ直線Ａ１、及びＰ’’とＯ（無限遠点）を結ぶ直線Ａ２を設定する。設定された直線Ａ１及びＡ２は、有理式算出手段２１４に送られ、次のステップＳ３５に進む。
【００４５】
［ステップＳ３５］
有理式算出手段２１４において、メモリ２１１からＱ,Ｓ,ｆ’を抽出し、ｆ’’←ｆ’・Ａ１(Ｑ＋Ｓ)・Ａ２(Ｓ)／Ａ１(Ｓ)／Ａ２(Ｑ＋Ｓ)の演算を行う。算出されたｆ’’はメモリ２１６に送られて格納され、次のステップＳ３６に進む。
［ステップＳ３６］
代入手段２１５において、Ｔ←Ｐｘ及びｆ←ｆｘ（ただし、ｍ０及びｍ１が同じビット数である場合Ｐｘ＝Ｐ’’及びｆｘ＝ｆ’’であり、 ｍ０のビット数がｍ１のビット数より大きい場合Ｐｘ=Ｐ及びｆｘ＝１であり、ｍ１のビット数がｍ０のビット数より大きい場合Ｐｘ＝Ｐ’及びｆｘ＝ｆ’である。）の演算を行う。
【００４６】
つまり、例えばまず、代入手段２１５は、メモリ２１６から整数ｍ０及びｍ１を抽出する。そして、抽出したｍ０及びｍ１が同じビット数である場合には、メモリ２１６からＰ’’及びｆ’’を抽出し、Ｐ’’をＴに、ｆ’’をｆに代入する。また、抽出した ｍ０のビット数がｍ１のビット数より大きい場合、代入手段２１５は、メモリ２１１からＰを抽出し、ＰをＴに、ｆに１を代入する。また、抽出したｍ１のビット数がｍ０のビット数より大きい場合、代入手段２１５は、メモリ２１１からＰ’及びｆ’を抽出し、Ｐ’をＴに、ｆ’をｆに代入する。なお、「ビット数」の意味は、第１の実施の形態の＜定義＞の欄で説明した通りである。
【００４７】
ここまでのステップにより、ｍ＝ｍ０＋ｍ１ｊを満たす整数ｍ０及びｍ１、Ｐ’’←Ｐ＋Ｐ’（∈Ｅ（Ｆｑ））、ｆ’’←ｆ’・Ａ１(Ｑ＋Ｓ)・Ａ２(Ｓ)／Ａ１(Ｓ)／Ａ２(Ｑ＋Ｓ)、Ｔ←Ｐｘ及びｆ←ｆｘの値がメモリ２１６に格納されたことになる。そして、次のステップＳ３７に進む。
［ステップＳ３７］
制御手段２２５において、ｉ←ｎ‐１の演算行い、次のステップＳ３８に進む。
［ステップＳ３８］
直線設定手段２１９において、メモリ２１６からＴを抽出し、Ｔと‐２Ｔを結ぶ直線Ｂ１と、２ＴとＯ（無限遠点）を結ぶ直線Ｂ２とを求める。算出された直線Ｂ１及びＢ２は、有理式算出手段２２１に送られ、次のステップＳ３９の処理に進む。
【００４８】
［ステップＳ３９］
２倍算手段２２０において、メモリ２１６からＴを通出し、Ｔ←２Ｔ（∈Ｅ（Ｆｑ））の演算を行う。この演算結果Ｔは、再び、メモリ２１６に送られ、そこに格納されているＴに上書きされる。そして、ステップＳ４０に進む。
［ステップＳ４０］
有理式算出手段２２１において、メモリ２１６からｆを抽出し、ｆ←ｆ２・Ｂ１(Ｑ＋Ｓ)・Ｂ２(Ｓ)／Ｂ１(Ｓ)／Ｂ２(Ｑ＋Ｓ)の演算を行う。算出されたｆは、再びメモリ２１６に送られ、そこに格納されているｆに上書きされる。そして、ステップＳ４１に進む。
【００４９】
［ステップＳ４１］
制御手段２２５において、メモリ２１６からｍ０及びｍ１を抽出し、ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であるか否かを判断する。ここで、ｍ０(ｉ)はｍ０のｉ＋１ビット目の値を意味し、ｍ１(ｉ)はｍ１のｉ＋１ビット目の値を意味する。また、この例におけるｉ＋１ビット目とは、ビット列の最下位ビット（１桁目のビット）から数えたｉ＋１桁目を意味する。またｉ＋１桁目が存在しない場合、ｍ０(ｉ)やｍ１(ｉ)の値は０として扱う。
この判断において、ｍ０(ｉ)＝１かつｍ１(ｉ)＝０であった場合には、ステップＳ４２に進み、そうでなかった場合にはステップＳ４５に進む。
【００５０】
［ステップＳ４２］
直線設定手段２２３において、メモリ２１１からＰを抽出し、メモリ２１６からＴを抽出し、直線Ｃ１としてＴとＰを結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ）とＯ（無限遠点）を結ぶ直線を求める。求められた直線Ｃ１及びＣ２は、有理式算出手段２２４に送られ、次のステップＳ４３に進む。
［ステップＳ４３］
加算手段２２２において、メモリ２１１からＰを抽出し、メモリ２１６からＴを抽出し、Ｔ←Ｔ＋Ｐ（∈Ｅ（Ｆｑ））の演算を行い、その演算結果Ｔをメモリ２１６に送り、そこに格納されているＴに上書きする。そして、ステップＳ４４に進む。
【００５１】
［ステップＳ４４］
有理式算出手段２４４において、メモリ２１１からＱ及びＳを抽出し、メモリ２１６からｆを抽出し、ｆ←ｆ・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う。この演算結果ｆはメモリ２１１に送られ、そこに格納されているｆに上書きされる。そして、ステップＳ５３に進む。
［ステップＳ４５］
制御手段２２５において、メモリ２１６からｍ０及びｍ１を抽出し、ｍ０(ｉ)＝０かつｍ１(ｉ)＝１であるか否かを判断する。ここでｍ０(ｉ)＝０かつｍ１(ｉ)＝１であった場合には、ステップＳ４６に進み、そうでなかった場合にはステップＳ４９に進む。
【００５２】
［ステップＳ４６］
直線設定手段２２３において、メモリ２１１からＰ’を抽出し、メモリ２１６からＴを抽出し、直線Ｃ１としてＴとＰ’を結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ’）とＯを結ぶ直線を求める。求められた直線Ｃ１及びＣ２は、有理式算出手段２２４に送られ、次のステップＳ４７に進む。
［ステップＳ４７］
加算手段２２２において、メモリ２１１からＰ’を抽出し、メモリ２１６からＴを抽出し、Ｔ←Ｔ＋Ｐ（∈Ｅ（Ｆｑ））の演算を行い、その演算結果Ｔをメモリ２１６に送り、そこに格納されているＴに上書きする。そして、ステップＳ４８進む。
【００５３】
［ステップＳ４８］
有理式算出手段２４４において、メモリ２１１からＱ、Ｓ及びｆ’を抽出し、メモリ２１６からｆを抽出し、ｆ←ｆ・ｆ’・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う。この演算結果ｆはメモリ２１１に送られ、そこに格納されているｆに上書きされる。そして、ステップＳ５３に進む。
［ステップＳ４９］
制御手段２２５において、メモリ２１６からｍ０及びｍ１を抽出し、ｍ０(ｉ)＝１かつｍ１(ｉ)＝１であるか否かを判断する。ここでｍ０(ｉ)＝１かつｍ１(ｉ)＝１であった場合には、ステップＳ５０に進み、そうでなかった場合にはステップＳ５３に進む。
【００５４】
［ステップＳ５０］
直線設定手段２２３において、メモリ２１６からＴ及びＰ’’抽出し、直線Ｃ１としてＴとＰ’’を結ぶ直線を求め、直線Ｃ２として（Ｔ＋Ｐ’’）とＯを結ぶ直線を求める。求められた直線Ｃ１及びＣ２は、有理式算出手段２２４に送られ、次のステップＳ５１に進む。
［ステップＳ５１］
加算手段２２２において、メモリ２１６からＴ及びＰ’’を抽出し、Ｔ←Ｔ＋Ｐ’’（∈Ｅ（Ｆｑ））の演算を行い、その演算結果Ｔをメモリ２１６に送り、そこに格納されているＴに上書きする。そして、ステップＳ５２進む。
【００５５】
［ステップＳ５２］
有理式算出手段２４４において、メモリ２１１からＱ及びＳを抽出し、メモリ２１６からｆ及びｆ’’を抽出し、ｆ←ｆ・ｆ’’・Ｃ１(Ｑ＋Ｓ)・Ｃ２(Ｓ)／Ｃ１(Ｓ)／Ｃ２(Ｑ＋Ｓ)の演算を行う。この演算結果ｆはメモリ２１１に送られ、そこに格納されているｆに上書きされる。そして、ステップＳ５３に進む。
［ステップＳ５３］
制御手段２２５において、ｉ＝０であるか否かを検討する。ここで、ｉ＝０であった場合には、ステップＳ５４に進み、そうでなかった場合には、ステップＳ５５に進む。
【００５６】
［ステップＳ５４］
制御手段２２５において、ｉ←ｉ‐１の演算を行い、ステップＳ３８に戻る。
［ステップＳ５５］
この時点までに、０以上ｎ−１以下のすべての整数ｉについて、ステップＳ３８からステップＳ５２までの処理が実行されたことになる。その後、有理式算出手段２２４は、メモリ２１６からｆを抽出し、このｆを出力する。このｆがｆＰ（Ｑ＋Ｓ）／ｆＰ（Ｓ）∈Ｆｑｋの値となる。
【００５７】
＜概念的説明＞
次にステップＳ３６からＳ５５までの処理を概念的に説明する。
図８は、本形態におけるｍのビット列３００の例示である。
図８に例示するように、この例のｍは、ｍ＝ｍ０＋ｍ１・２１０であり、ｍ１＝（１０１１１１１０１）２、ｍ０＝（１１１１００１０１１）２である。そして、ｍ１のビット数は９ビットであり、ｍ０のビット数は１０ビットであり、ｍ０のビット長の方が大きいため、ｍ０のビット数（１０）がｎとなる。また、この例の場合、ｍ０のビット数がｍ１のビット数より大きいため、ステップＳ３６の処理においてＴに代入されるＰｘはＰである。
【００５８】
また、Ｔはｍの全ビットの処理に対応するものであり、ステップＳ３９の楕円２倍算処理は、ｍ１のビット及びｍ０のビット双方に対応する楕円２倍算処理を同時に行っていることに相当する。同様に、ステップＳ４０の直線設定処理は、ｍ１のビット及びｍ０のビット双方に対応する直線設定処理を同時に行っていることに相当する。これらは、従来のMillerのアルゴリズム（〔技術背景〕＜Millerのアルゴリズム＞参照。）におけるＳｔｅｐ２−１から３の処理を、ｍ１のビット及びｍ０のビット双方について並行して行っていることに相当する。
【００５９】
図８の例の場合、ｉ＝９に対応するｍ０の１０桁目のビット値ｍ０（９）は１であるが、ｍ１には１０桁目のビットが存在しない。よって、ｍ１（９）＝０となり、ｉ＝９のときには、ステップＳ４２からＳ４４の処理が実行される。また、ｉ＝４に対応するｍ０の５桁目のビット値ｍ０（４）は０であり、ｍ１の５桁目のビット値ｍ１（４）は１である。よって、ｉ＝４のときには、ステップＳ４６からＳ４８の処理が実行される。また、ｉ＝０に対応するｍ０の１桁目のビット値ｍ０（０）は１であり、ｍ１の１桁目のビット値ｍ１（０）は１である。よって、ｉ＝０のときには、ステップＳ５０からＳ５１の処理が実行される。ここで、ステップＳ５０からＳ５１の処理は、ビット値が１であるｍ０、ｍ１の双方のビットについて、従来のMillerのアルゴリズムにおけるＳｔｅｐ２−４の処理を並行に実行していることに相当する。
【００６０】
＜本形態の特徴＞
以上説明した通り、本形態では、２倍算手段２２０において、ｍのｊビット以上のビット列に対応する楕円２倍算と、ｊビット未満のビット列に対応する楕円２倍算とを並列的に実行する（ステップＳ３９）。そして、それに対応する直線設定手段２１９及び有理式算出手段２２１の処理も、ｊビット以上のビット列に対応する処理と、ｊビット未満のビット列に対応する処理の並列処理に相当する。またステップＳ５０からＳ５１の処理も、ビット値が１であるｍ０、ｍ１の双方のビットについての並列処理に相当する。
【００６１】
このように本形態では、ｍの上位ビット列に対応する処理と下位ビット列に対応する処理とを並列的に行い、処理の効率化・高速化を図っている。
以下、従来のMillerのアルゴリズムと本形態のアルゴリズムとの計算量の違いを示す。なお、本形態のアルゴリズムの演算量をｃＭＩＬＬＥＲとする。
［従来のMillerのアルゴリズムの計算量］
ＭＩＬＬＥＲ＝ｎＴＤＢＬ＋（ｎ／２）ＴＡＤＤ
［本形態のアルゴリズムの計算量］
ｃＭＩＬＬＥＲ＝（ｎ／２）ＴＤＢＬ＋（３／８）ＴＡＤＤ
また、一例として、ｋ＝６、ｎ＝１７０、ｗ＝４の場合を想定すると、
ＭＩＬＬＥＲ＝６１７１０Ｍ
ｃＭＩＬＬＥＲ＝３４９７８Ｍ
となり、本形態のアルゴリズムでは４３.３％の演算量が削減できることが分かる。
【００６２】
なお、本形態では、ステップＳ３１からＳ３６の処理によって、メモリ２１６に格納するデータを求め、このメモリ２１６に格納することとしたが、メモリ２１６に格納するＰ’’、Ａ１、Ａ２、ｆ、ｆ’’及びＴをオフラインで事前計算しておいてもよい。
なお、この発明は上述の各実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００６６】
本発明を適用することにより、楕円曲線上でのＩＤベース暗号方式等の公開鍵暗号や、Ｓhort signature方式等のデジタル署名を高速に実装することが可能となる。
【図面の簡単な説明】
【００６７】
【図１】第１の実施の形態におけるペアリング装置の機能構成を例示したブロック図。
【図２】第１の実施の形態におけるペアリング装置の処理方法を説明するためのフローチャート。
【図３】第１の実施の形態におけるペアリング装置の処理方法を説明するためのフローチャート。
【図４】第１の実施の形態におけるｗ＝３の場合におけるｍのビット列の例示。
【図５】第２の実施の形態におけるペアリング装置の機能構成を例示したブロック図。
【図６】第２の実施の形態におけるペアリング装置の処理方法を説明するためのフローチャート。
【図７】第２の実施の形態におけるペアリング装置の処理方法を説明するためのフローチャート。
【図８】第２の実施の形態におけるｍのビット列の例示。
【図９】従来のMillerのアルゴリズムの処理を概念的に説明するための図。
【符号の説明】
【００６８】
１,２００  ペアリング装置
【図１】
2005308956.tif 000005
【図２】
2005308956.tif 000006
【図３】
2005308956.tif 000007
【図４】
2005308956.tif 000008
【図５】
2005308956.tif 000009
【図６】
2005308956.tif 000010
【図７】
2005308956.tif 000011
【図８】
2005308956.tif 000012
【図９】
2005308956.tif 000013