拡張ユークリッドアルゴリズム(exgcd)学習ノート

定義＃テイギ＃

まず貝祖定理というものを導入します
∀a,b∈Nに対しては,常に∃x,y∈Zであり,ax+by=(a,b)
a,b,ax+by=(a,b)の実行可能な解のセットを求めるアルゴリズムは拡張ユークリッドアルゴリズムであることが知られている.

アルゴリズムフロー

まず,最大公因数を求めるためのユークリッドアルゴリズムを知った.

int gcd(int a,int b)
{
    if (!b) return a;
    else return gcd(b,a/b)
}

拡張ユークリッドは実際にユークリッドアルゴリズムに基づいて実行され、時間の複雑さもlogレベルにある.現在ax+by=(a,b)であると仮定すると、(b,a%b)=(a,b)であるので、bx+(a%b)y=(a,b)はまたa%b=a−(a/b)=a−(a/b)=bx+(a−(a/b)∗b)y=bx+ay−(a/b)∗b)y=bx+ay−(a/b)∗y=ay+b(x−(a/b)=ay+b(x−(a/b)∗y)であるため、次の条件を満たす解がx′==x′=x’=(a,b)であることが分かるy,y’=x−(a/b)∗y b=0のとき、すなわちaは最大公因数である.この場合、aの係数であるx=1を保証するだけでよく、yは任意の値を取っても影響しないので、y=0としてもよい.これが拡張ユークリッドアルゴリズム全体の過程である.

int exgcd(int a,int b,int &x,int &y)
{
    if (!b)
    {
        x=1,y=0;
        return a;
    }
    int ans=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-(a/b)*y;
    return ans;
}

実は拡張ユークリッドにはもっと簡単な書き方があります(from fye)

void exgcd(int a,int b,int &x,int &y,int &d)
{
    if (!b) x=0,y=1,d=a;
    else exgcd(b,a%b,y,x),y-=(a/b)*x;
}

じつもんだい

実際、exgcdで問題を解決する際にはいくつかの問題があります.

いっぱんがたとうしき

例えばax+by=cの値を要求すると、まず等式を2回同時に(a,b)で割ることができ、cはabの倍数ではないので、除去できないと解がない.では、現在、等式はa’x+b’y=c’,(a’,b’)=1となり、拡張欧州の条件を満たすためにa’x+b’y=(a’,b’)=1となり、等式を2回同時にcで割ってaxc+byc=1とすることができる.これによりexgcdを直接利用してxcとycの値を求めてから乗せればよい.また,exgcdで求めたx,yはこのような性質{|x|+|y|}minを満たしていることを証明し,ここを突き刺して実行可能な解を求めた後にxを絶えず-b/(a,b),yを絶えず+a/(a,b)とし,解は依然として成立する.

ぎゃくげん

ax≡1(modp),(a,p)=1の場合,xはaの逆元である.等式化を簡略化するとax−py=1,すなわちexgcdの古典モデルが得られる.