Discrete Logging

亦凉 2021-05-03 02:27 415阅读 0赞

Discrete Logging

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

Description

Given a prime P, 2 <= P < 2 31, 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 

  1. B

L

  1. == 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. 5 2 1
  2. 5 2 2
  3. 5 2 3
  4. 5 2 4
  5. 5 3 1
  6. 5 3 2
  7. 5 3 3
  8. 5 3 4
  9. 5 4 1
  10. 5 4 2
  11. 5 4 3
  12. 5 4 4
  13. 12345701 2 1111111
  14. 1111111121 65537 1111111111

Sample Output

  1. 0
  2. 1
  3. 3
  4. 2
  5. 0
  6. 3
  7. 1
  8. 2
  9. 0
  10. no solution
  11. no solution
  12. 1
  13. 9584351
  14. 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 

  1. B

(P-1)

  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 

  1. B

(-m)

  1. == B

(P-1-m)

  1. (mod P) .

Source

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^j
  35.          for(LL j=0;j<=m;j++)  // a^(i*m) = b * a^j
  36.          {
  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-j
  55.                  printf("%lld\n",(out%c+c)%c);
  56.                  flag=1;
  57.                  break;
  58.              }
  60.          }
  61.          if(!flag)
  62.          printf("no solution\n");    
  63.      }
  65.      return 0;
  66.  }

发表评论

表情：
评论列表 （有 0 条评论，415人围观）

还没有评论，来说两句吧...

相关阅读