poj 2417 Discrete Logging(bsgs算法,baby-step giant-step)

Time Limit: 5000MS Memory Limit: 65536K

Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that
B^L == N (mod P)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print “no solution”.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 2 1
5 2 2
5 2 3
5 2 4
5 3 1
5 3 2
5 3 3
5 3 4
5 4 1
5 4 2
5 4 3
5 4 4
12345701 2 1111111
1111111121 65537 1111111111

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587

Hint

The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat’s theorem that states
B(P-1) == 1 (mod P)

for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat’s theorem is that for any m
B(-m) == B(P-1-m) (mod P) .

Source

Waterloo Local 2002.01.26


题意:

给定b,n,p,求最小的非负整数l,满足b^l ≡ n(mod p)

题解:

学个新东西,bsgs算法(baby step giant step大步小步算法)其实我觉得它的别名北上广深算法拔山盖世算法更好听一点╮( ̄▽ ̄””)╭

不晓得这个算法是怎么被想出来的,大致做法如下:

l=i*m-j,m=ceil(√p),ceil()是向上取整

代入原式得

1
2
b^(i*m-j) ≡ n(mod p)
b^(i*m) ≡ n*b^j(mod p)

枚举j[0,m],将n*b^j(mod p)存入hash表,枚举i[1,m],在hash表中寻找第一个满足b^(i*m) ≡ n*b^j(mod p)的,l=i*m-j即为答案

看完这个做法还是懵逼的,所以接下来来证明为什么m=ceil(sqrt(p))范围内就可以找到

l=i*m-j=i*ceil(√p)-j<p,所以实际上是要证明l<=p的范围内就能找到合法的l

再把这个问题转化为用费马小定理证明这个式子:b^(k mod (p-1)) ≡ b^k(mod p)

证明:

k mod (p-1)等价于k-m(p-1),则有b^(k-m(p-1)) ≡ b^k(mod p),化简得b^(m(p-1)) ≡ 1(mod p)

由费马小定理,已知:当p为质数且(a,p)=1时,a^(p-1) ≡ 1(mod p)

所以当(b,p)!=1b^(m(p-1)) ≡ b^(p-1)(mod p),即证b^(k mod (p-1)) ≡ b^k(mod p)

m=ceil(sqrt(p))可行

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;

#define LL long long
LL p,b,l,n,m,ans;
map<LL,int>mp;
LL qpow(LL a,LL b){
LL anss=1;
while(b){
if(b&1){
anss=(anss*a)%p;
b--;
}
b/=2;
a=a*a%p;
}
return anss;
}
int main(){
while(scanf("%lld%lld%lld",&p,&b,&n)!=EOF){
if(b%p==0){
puts("no solution");
continue;
}
mp.clear();
ans=-1;
m=ceil(sqrt(p));
LL tmp=n%p;
mp[tmp]=0;
for(int i=1;i<=m;i++){
tmp=(tmp*b)%p;
mp[tmp]=i;
}
tmp=1;
LL num=qpow(b,m);
for(int i=1;i<=m;i++){
tmp=(tmp*num)%p;
if(mp[tmp]){
ans=i*m-mp[tmp];
ans=(ans%p+p)%p;
printf("%lld\n",ans);
break;
}
}
if(ans==-1)puts("no solution");;
}
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信