拡張ユークリッドアルゴリズム

最近の暗号学実験では、モジュール逆が要求され、以前は拡張されたユークリッドアルゴリズムを真剣に研究したことがなく、この機会に拡張されたユークリッドアルゴリズムをよく研究した.
拡張ユークリッドアルゴリズムの応用範囲も広い:1.不定方程式の解を解くのに用いることができる.2.モーダル線形方程式(線形同余方程式)を解くために用いることができる.型の逆元を解く.
この名称から,このアルゴリズムはユークリッドアルゴリズムの拡張であり,ユークリッドアルゴリズムは2つの数を求める最大公約数であり,拡張アルゴリズムは上記式のx,yを解くことであることが分かる.
基本アルゴリズム:完全に0ではない非負の整数a,b,gcd(a,b)はa,bの最大公約数を表し、必然的に整数対x,yが存在し、gcd(a,b)=ax+byとなる.
このアルゴリズムの証明を次に示します.
推理1:b=0の場合、gcd(a,b)=a;この場合、x=1、y=0;//推理1;
推理2:当a*b!=0の場合:
a 0*x 0+b 0*y 0=gcd(a 0,b 0)とする.ここでのa 0,b 0,x 0,y 0はいずれも1つの状態である.
ユークリッドアルゴリズムがあります.
次の状態:a 1=b 0、b 1=a 0%b 0=a 0-(a 0/b 0)*b 0;
a1*x1+b1*y1=gcd(a1,b1);前に得られた式を代入する.
得:b 0*x 1+a 0*y 1-(a 0/b 0)*b 0*y 1=gad(a 1,b 1)=gcd(a 0,b 0);
上記の手順から、次のことがわかります.
x 0=y 1、y 0=x 1-(a 0/b 0)b 0*y 1//推理2;
これにより、x 0,y 0を解く方法が得られ、x 0,y 0はx 1,y 1に基づいている.
上で利用した思想は再帰に基づいており、すべての私たちは再帰のプログラムを得ることができ、b=0は再帰の出口である.
再帰コードは次のとおりです.

#include <iostream>
#include <cstdio>
int ext_gcd(int a,int b,int &x,int &y)
{
    if(b==0)//    1
    {
        x=1;
        y=0;
        return a;
    }
    int r=ext_gcd(b,a%b,x,y);
    int t=y;//  2
    y=x-(a/b)*y;
    x=t;
    return r;
}
int main()
{
    int a,b,x,y;
    scanf("%d%d",&a,&b);
    ext_gcd(a,b,x,y);
    printf("%d %d
",x,y);
    return 0;
}

再帰的なユークリッドアルゴリズムと照らし合わせることができます.

int gcd(int a,int b)
{
    if(b==0)
    return a;
 
    else return gcd(b,a%b);
 }

は、x,yを求めるプロセスを中間に追加したものに相当する.
非再帰的に実現することもできる:(モード逆を求める過程)しかし、この方法で求めたモード逆には負の数が現れる可能性があり、モード逆の定義は最小正の整数である.

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int gcd(int a,int b)//euclid
{
    int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void extend_euclid(int f,int d)//    
{
    int x1,x2,x3;
    int y1,y2,y3;
    int q,t1,t2,t3,flag=0;
    x1=1,x2=0,x3=f;
    y1=0,y2=1,y3=d;
    while(1)
    {
        if(flag==1) break;
        if(y3==0)  x3=gcd(f,d);
        else if(y3==1)
        {
            y3=gcd(f,d);
            printf("%d
",y2);
            flag=1;
        }
        q=x3/y3;
        t1=x1-q*y1;
        t2=x2-q*y2;
        t3=x3-q*y3;
        x1=y1,x2=y2,x3=y3;
        y1=t1,y2=t2,y3=t3;
    }
}
int main()
{
    int a,b;
    printf("             :
");
    scanf("%d%d",&a,&b);
    extend_euclid(a,b);
    return 0;
}

他人が書いた非再帰プログラム:(比較的簡素)

int exgcd(int m,int n,int &x,int &y)
{
    int x1,y1,x0,y0;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=m%n;
    int q=(m-r)/n;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        m=n; n=r; r=m%n;
        q=(m-r)/n;
    }
    return n;
}

参考になりましたhttp://www.acmerblog.com/extend-gcd-5610.html