[BSGS]-白红宇

[BSGS]

阅读量：6888 次

发布时间：2019-06-27

本文共 1911 字，大约阅读时间需要 6 分钟。

[模板] 大步小步算法——BSGS算法

这个算法叫做B(拔)S(山)G(盖)S(世)，或B(北)S(上)G(广)S(深)。就是这么个骚东西。

大步小步算法用于解决：已知A, B, C，求X使得

A^x = B (mod C)

成立。

先令 x = i*m-j，其中 m=ceil(sqrt(p))，ceil是向上取整。

这样原式就变为 a^i*m-j= b (mod p)，

移项就变成了 a^i*m = b*a^j(mod p)

枚举j (范围0-m) ,将 b*a^j存入hash表。

枚举i (范围1-m) ,从hash表中寻找第一个满足a^i*m= b*a^j(mod p)。

此时 x = i*m-j 就是所要求的。

那么为什么只计算到 m=ceil(sqrt(q)) 就可以确定答案呢？

因为 x = i*m-j , 所以x 的最大值不会超过p

由费马小定理知: 当

所以：如果枚举

还有我不保证我写的不会出错（逃

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
         5 #include 
         
           6  7 using namespace std; 8  9 map
          
            kkk;10 11 int a,b,p,res;12 13 bool flag;14 15 long long GCD(long long a,long long b)16 {17 return !b ? a : GCD(b,a % b); 18 } 19 20 long long quickpower(long long a,long long b,long long p)21 {22 long long ans = 1;23 24 while(b)25 {26 if(b & 1) ans = ans * a % p;27 28 a *= a;29 b >>= 1; 30 }31 32 return ans % p;33 }34 35 int main()36 {37 while(scanf("%d%d%d",&a,&p,&b) && a != 0 && b != 0 && p != 0)38 {39 flag = 0;// 判断的 40 41 if(a == b)// 特判 42 {43 printf("1\n");44 45 flag = 1;46 }47 48 kkk.clear();//清空 49 50 if(GCD(a,p) != 1)// 不互质 51 {52 printf("No Solution\n");53 54 continue;55 }56 57 int sq = ceil(sqrt(p));// 分块 58 59 int now = b % p;// j == 0;60 61 kkk[now] = 0;62 63 for(int j=1;j<=sq;j++)64 {65 now = now * a % p;66 67 kkk[now] = j;68 }69 70 now = 1;71 72 int power = quickpower(a,sq,p);//求 a^sq 73 74 for(int i=1;i<=sq;i++)75 {76 now = now * power % p;// 枚举 a^(i*sq) 77 78 if(kkk[now] && !flag)// flag 防止 多输出 , 如果找到了重复的 说明已经找到了 79 {80 res = i * sq - kkk[now];81 82 printf("%d\n",(res + p) % p);// 保证不为负数 83 84 flag = 1;85 86 }87 }88 89 if(!flag)90 printf("No Solution\n");91 }92 93 return 0;94 }