Baby-Step-Gaint-Step算法详解

末蓝、 2022-07-17 03:19 141阅读 0赞

**Baby-Step-Gaint-Step**

Baby-Step-Gaint-Step用来求解高次同余方程 A^x ≡ B (mod C) 中已知A B C求较大x的情况。  
按wiki百科所言：  
①令x=i\*n+j，其中n=ceil(sqrt(C))，原式变为A^(i\*n+j) = B (mod C)，两边同时乘上A^(-n\*i)，可以得到A^j=B\*A^(-n\*i) (mod C)；  
②处理等号左边A^j：循环i=\[0,C-1\]，求出（A^i,i)插入hash表；  
③处理等号右边B\*A^(-n\*i) (mod C)：由于B\*A^(-n\*i) =B/A^(n\*i) ，则用拓展欧几里得算法求A^(n\*i)关于模C的乘法逆元x（即满足(A^(n\*i))^x ≡ 1 (mod C)），此时B\*A^(-n\*i) = B\*x(mod C)；  
④枚举，求出左右式子相等的情况即为方程的解。

（POJ3243模板裸题AC代码）

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<malloc.h>
    using namespace std;
    typedef long long ll;
    #define maxn 100000
    
    struct Hash
    {
        int a,b,next;
    } hash[2*maxn];
    int flag[maxn];
    int top,idx;
    
    void Insert(int a,int b)
    {
        int k=b&maxn;
        if(flag[k]!=idx)
        {
            flag[k]=idx;
            hash[k].next=-1;
            hash[k].a=a;
            hash[k].b=b;
            return;
        }
        while(hash[k].next!=-1)
        {
            if(hash[k].b==b) return;
            k=hash[k].next;
        }
        hash[k].next=++top;
        hash[top].next=-1;
        hash[top].a=a;
        hash[top].b=b;
    }
    
    int Find(int b)
    {
        int k=b&maxn;
        if(flag[k]!=idx) return -1;
        while(k!=-1)
        {
            if(hash[k].b==b) return hash[k].a;
            k=hash[k].next;
        }
        return -1;
    }
    
    int gcd(int a,int b)
    {
        return b==0?a:gcd(b,a%b);
    }
    
    int exgcd(int a,int b,int &x,int &y)//拓展欧几里得求逆元
    {
        int t,d;
        if(!b)
        {
            x=1,y=0;
            return a;
        }
        d=exgcd(b,a%b,x,y);
        t=x,x=y,y=t-a/b*y;
        return d;
    }
    
    int inval(int a,int b,int n)
    {
        int x,y,e;
        exgcd(a,n,x,y);
        e=(long long)x*b%n;
        return e<0?e+n:e;
    }
    
    int pow_mod(long long a,int b,int c)//矩阵快速幂
    {
        long long ret=1%c;
        a%=c;
        while(b)
        {
            if(b&1) ret=ret*a%c;
            a=a*a%c;
            b>>=1;
        }
        return ret;
    }
    
    int BabyStep(int A,int B,int C)
    {
        top=maxn;
        ++idx;
        long long buf=1%C,D=buf,K;
        int i,d=0,tmp;
        for(i=0; i<=100; buf=buf*A%C,++i)//从0到100循环验证：A^i≡B(mod C)
            if(buf==B) return i;//找到满足等式的i
        while((tmp=gcd(A,C))!=1)
        {
            if(B%tmp) return -1;//因为A^x=B+k*C，所以B%tmp==0，即非零情况无解
            ++d;
            C/=tmp;
            B/=tmp;
            D=D*A/tmp%C;
        }
        int M=(int)ceil(sqrt((double)C));//向上取整
        for(buf=1%C,i=0; i<=M; buf=buf*A%C,++i)//从0到M循环，将(i,A^i%C)插入hash表
            Insert(i,buf);
        for(i=0,K=pow_mod((long long)A,M,C); i<=M; D=D*K%C,++i)//求D*X=B(mod C)在[0,C-1]上的解
        {
            tmp=inval((int)D,B,C);
            int w;
            if(tmp>=0&&(w=Find(tmp))!=-1)//在hash表中查找到
                return i*M+w+d;
        }
        return -1;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int A,B,C;
        while(cin>>A>>C>>B,A||B||C)
        {
            B%=C;
            int tmp=BabyStep(A,B,C);
            if(tmp<0) puts("No Solution");
            else cout<<tmp<<endl;
        }
        return 0;
    }
    /**
    5 58 33
    2 4 3
    0 0 0
    **/

[POJ2417&&POJ3243][POJ2417_POJ3243]：http://blog.csdn.net/MIKASA3/article/details/52101588?locationNum=1

[POJ2417_POJ3243]: http://blog.csdn.net/MIKASA3/article/details/52101588?locationNum=1