有限ドメイン上の逆演算
有限ドメイン上の逆演算には2つの求めアルゴリズムがあり,1つは指数法,1つは拡張ユークリッドアルゴリズムである.
1、指数法
有限ドメインGF(p)に対してpは素数であり、このドメイン上の非ゼロ要素gに対して{g}の逆元はc=g−1=gp−2であり、整数p−1はe=p−2=erer−1としてバイナリ表現できる…e 1 e 0のうち最高位er=1では、求逆過程は有限ドメイン上の指数を求める過程に変換され、有限ドメイン上の指数を求めるアルゴリズム過程は:
出力xは要求の逆である.
2、拡張ユークリッドアルゴリズム
ユークリッドアルゴリズムは転がり相除算法とも呼ばれ、2つの整数a,bについて、a>bであれば、その最大公約数gcd(a,b)を求め、gcd(a,b)=gcd(b,amodb)があり、このように転がり除算すれば最大公約数を得ることができる.拡張ユークリッドアルゴリズムとは、不完全が0の整数a,bに対して、整数x,yが存在し、ax+by=gcd(a,b)にxを求める過程であり、yの過程は、ユークリッドアルゴリズムによれば、ax+by=gcd(a,b)=gcd(b,amodb)=bx 2+(amodb)y 2が恒等定理を利用するとx 1=y 2;y 1=x 2−[a/b]∗y 2は,転がり相除去が停止するとx,yを再帰的に求めることができることを示した.この定理を用いて,有限領域GF(p)において,いずれかの非ゼロ元gに対してgx+py=gcd(g,p)=1があり,等式化されたxがgの逆元となり,逆元を解く過程がxを解く過程に変換される.
1、指数法
有限ドメインGF(p)に対してpは素数であり、このドメイン上の非ゼロ要素gに対して{g}の逆元はc=g−1=gp−2であり、整数p−1はe=p−2=erer−1としてバイナリ表現できる…e 1 e 0のうち最高位er=1では、求逆過程は有限ドメイン上の指数を求める過程に変換され、有限ドメイン上の指数を求めるアルゴリズム過程は:
x=g
for i=r-1:0
x=x*x
if ei==1
x=x*g
end
end出力xは要求の逆である.
2、拡張ユークリッドアルゴリズム
ユークリッドアルゴリズムは転がり相除算法とも呼ばれ、2つの整数a,bについて、a>bであれば、その最大公約数gcd(a,b)を求め、gcd(a,b)=gcd(b,amodb)があり、このように転がり除算すれば最大公約数を得ることができる.拡張ユークリッドアルゴリズムとは、不完全が0の整数a,bに対して、整数x,yが存在し、ax+by=gcd(a,b)にxを求める過程であり、yの過程は、ユークリッドアルゴリズムによれば、ax+by=gcd(a,b)=gcd(b,amodb)=bx 2+(amodb)y 2が恒等定理を利用するとx 1=y 2;y 1=x 2−[a/b]∗y 2は,転がり相除去が停止するとx,yを再帰的に求めることができることを示した.この定理を用いて,有限領域GF(p)において,いずれかの非ゼロ元gに対してgx+py=gcd(g,p)=1があり,等式化されたxがgの逆元となり,逆元を解く過程がxを解く過程に変換される.