首页 > 代码库 > Discrete Logging

Discrete Logging

2024-09-23 10:32:03   214人阅读

Discrete Logging
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 5865 Accepted: 2618

Description

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

5 2 15 2 25 2 35 2 45 3 15 3 25 3 35 3 45 4 15 4 25 4 35 4 412345701 2 11111111111111121 65537 1111111111

Sample Output

013203120no solutionno solution19584351462803587

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
BSGS模板题
 
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<map> 6 #define LL long long  7 using namespace std; 8 LL a,b,c; 9 map<LL,LL>mp;10 LL fastpow(LL a,LL p,LL c)11 {12     LL base=a;LL ans=1;13     while(p!=0)14     {15         if(p%2==1)ans=(ans*base)%c;16         base=(base*base)%c;17         p=p/2;18     }19     return ans;20 }21 int main()22 {23     // a^x = b (mod c)24     while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF)25     {26         LL m=ceil(sqrt(c));// 注意要向上取整 27         mp.clear();28         if(a%c==0)29         {30         printf("no solution\n");31         continue;32         }33         // 费马小定理的有解条件 34         LL ans;//储存每一次枚举的结果 b* a^j35         for(LL j=0;j<=m;j++)  // a^(i*m) = b * a^j36         {37             if(j==0)38             {39                 ans=b%c;40                 mp[ans]=j;// 处理 a^0 = 1 41                 continue;42             }43             ans=(ans*a)%c;// a^j 44             mp[ans]=j;// 储存每一次枚举的结果 45         }46         LL t=fastpow(a,m,c);47         ans=1;//a ^(i*m)48         LL flag=0;49         for(LL i=1;i<=m;i++)50         {51             ans=(ans*t)%c;52             if(mp[ans])53             {54                 LL out=i*m-mp[ans];// x= i*m-j55                 printf("%lld\n",(out%c+c)%c);56                 flag=1;57                 break;58             }59             60         }61         if(!flag)62         printf("no solution\n");    63     }64     65     return 0;66 }

 

Discrete Logging


联系
我们