Pat
J-GLOBAL ID：200903042477072356
ペアリング演算装置、ペアリング演算方法、およびペアリング演算プログラム
Inventor：
,
Applicant, Patent owner：
Agent (1)：
草野 卓
Gazette classification：公開公報
Application number (International application number)：2005146556
Publication number (International publication number)：2006323160
Application date： May. 19, 2005
Publication date： Nov. 30, 2006
Summary：
【課題】ペアリングの演算に必要な演算量は通常の楕円演算にくらべると非常に大きいため、その演算速度が遅い。【解決手段】本発明では、有限体の性質を用いて高速化を行う。rを有限体GF(pk/2)上の元、fをMillerのアルゴリズムで求められる有限体GF(pk)上の元とすると、f’=rfを満足する有限体GF(pk)上の元f’へ写像するMillerアルゴリズムよりも計算量が少ないアルゴリズム用いて計算する。逆元を求める代わりに、乗算する元のpk乗を擬似逆元として求める。擬似逆元を用いることで、演算量の多いGF(pk)の元どうしの乗算を多項式展開できる。多項式展開によって演算量の多い項を繰り返し計算の共通の項としてあらかじめ求めておくことで高速化を行う。【選択図】図7
Claim (excerpt)：
pは素数または素数のべき乗、kは偶数であって、有限体GF(p)上の楕円曲線上の点Pと有限体GF(pk)上の楕円曲線上の点Qを入力とし、入力された点から有限体GF(pk)上の元f’を求める擬似Miller演算部と、求めた有限体上の元を有限体GF(pk)上の元e(P,Q)に写像し、出力するべき乗演算部とを備えるペアリング演算装置において、
XとYをGF(pk)上の元、X^をXの共役元、c、d、e、g、hをGF(p)上の元とする場合に、
PとQから有限体GF(pk)上の元fを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体GF(pk)上の元Lの逆元の代わりに
IPC (1)：
FI (1)：
F-Term (4)：
5J104AA18
, 5J104AA25
, 5J104NA16
, 5J104PA07
