Poj 2417 Discrete Logging (Baby Step Giant Step 解 a^x = b (mod n) n为素数)

川长思鸟来 2022-09-17 10:21 13阅读 0赞

Baby Step Giant Step 解 a^x = b (mod n) n为素数

这类问题用Hash表查找，速度明显比二分数组的方式快

Hash表inset函数加入判重会更快一些

以下内容节选自：[AekdyCoin的空间][AekdyCoin]

【普通Baby Step Giant Step】  
  
【问题模型】  
求解  
A^x = B (mod C) 中 0 <= x < C 的解,C 为素数  
  
【思路】  
我们可以做一个等价  
x = i \* m + j ( 0 <= i < m, 0 <=j < m) m = Ceil ( sqrt( C) )  
而这么分解的目的无非是为了转化为:  
(A^i)^m \* A^j = B ( mod C)  
  
之后做少许暴力的工作就可以解决问题：  
(1) for i = 0 -> m, 插入Hash (i, A^i mod C)  
(2) 枚举 i ,对于每一个枚举到的i,令 AA = (A^m)^i mod C  
我们有  
AA \* A^j = B (mod C)  
显然AA,B,C均已知，而由于C为素数,那么(AA,C)无条件为1  
于是对于这个模方程解的个数唯一(可以利用扩展欧几里得或 欧拉定理来求解)  
那么对于得到的唯一解X,在Hash表中寻找,如果找到，则返回 *i \* m + j*   
注意:由于i从小到大的枚举,而Hash表中存在的j必然是对于某个剩余系内的元素X 是最小的(就是指标)  
所以显然此时就可以得到最小解  
  
如果需要得到 x > 0的解，那么只需要在上面的步骤中判断 当 i \* m + j > 0 的时候才返回

代码参考自：http://www.cnblogs.com/kuangbin/archive/2013/08/24/3278852.html

另一种实现：http://blog.csdn.net/acm\_cxlove/article/details/7831793

#include <cstdio>
    #include <cstring>
    #include <cmath>
    
    #define i64 long long
    
    
    //Baby Step Giant Step 离散对数
    // a^x = b (mod n) n为素数，a,b < n
    // 求解上式 0<=x < n的解
    
    const int MOD=65535;
    int hash[MOD],head[MOD],next[MOD],id[MOD],e;
    
    void insert (int x,int y)
    {
        int k = x%MOD;
        for (int i=head[k] ; i!=-1 ; i=next[i])
            if (hash[i] == x)
    			return ;
        hash[e]=x;
        id[e]=y;
        next[e]=head[k];
        head[k]=e++;
    }
    
    int find (int x)
    {
        int k = x%MOD;
        for (int i=head[k] ; i!=-1 ; i=next[i])
            if (hash[i] == x)
                return id[i];
        return -1;
    }
    
    int BSGS (int a,int b,int n)
    {
    	memset(head,-1,sizeof(head));
    	e=1;
    	if (b==1) return 0;
    	int m = sqrt(1.0*n), j;
    	i64 x=1,p=1,i;
    	for (i=0;i<m;i++, p = p*a%n )  //p对应a^i
    		insert(p*b%n,i);
    	for (i=m; ;i+=m)
    	{
    		if ( (j = find(x = x*p%n)) != -1 ) return i-j;
    		if (i>n) break;
    	}
    	return -1;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int p,b,n;
    	while (~scanf("%d%d%d",&p,&b,&n))
    	{
    		int ans=BSGS(b,n,p);
    		if (ans==-1)
    			printf("no solution\n");
    		else
    			printf("%d\n",ans);
    	}
    	return 0;
    }

[AekdyCoin]: http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4