数論のユークリッドアルゴリズム(三)

概要:この編はユークリッドアルゴリズムの古典的な応用を討論する.モデル線形方程式は、例えばax≡b(mod n)の方程式を指し、RSA公開鍵暗号化システムにおける鍵検索のような現実にいくつかの応用がある.この方程式は拡張ユークリッドアルゴリズムで解くことができ,解の大きさ範囲は[0,n)である.
アルゴリズム:拡張ユークリッドアルゴリズムを用いてモード線形方程式を解くのは実は群論に基づいているが,ここでは後述しないが,解の区間を整数の範囲に制限すると,方程式には無限解または無解がある.無限解は実際にはあまり役に立たないので、したがって,区間[0,n)を一般的に考慮する.方程式ax≡b(mod n)を解くためには,ax+ny=d,d=gcd(a,n)dがbを除去すると,方程式にd個の解が存在し,そうでなければ解がない形式に変換する必要がある.方程式ax+ny=d,d=gcd(a,n)拡張ユークリッドアルゴリズムを用いて解くことができ、拡張ユークリッドアルゴリズムを用いることで、最大公約数dおよび方程式の解(x,y)のセットを求めることができ、dがbを除去すれば、この解のセットから区間[0,n)内のd個の解を求めることができる.まず、最小解x 0を要求する必要がある.

x%=n,x+=n,x%=n;
ans[0]=x*(b/d)%(n/d);

その後、x 0に基づいてn/dを増やして型を取ればよい.
コード:

vector<long long> modular_linear_equation(long long a,long long b,long long n)
{
    long long x,y;
    long long d=extend_gcd(a,n,x,y);
    vector<long long> ans;
    ans.clear();
    if(b%d==0)
    {
        x%=n,x+=n,x%=n;
        ans.push_back(x*(b/d)%(n/d));
        for(long long i=1;i<d;i++)
            ans.push_back((ans[0]+i*n/d)%n);
    }
    return ans;
}

extend_gcd関数のインタフェースはここです!