Advertisement
Guest User

Untitled

a guest
Apr 24th, 2019
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. using namespace::std;
  4.                
  5.  
  6.  
  7.  
  8. void Input(int&a, int&p, int&y)
  9. {
  10.     cout << "Введите a,p,y: ";
  11.     cin >> a >> p >> y;
  12. }
  13.  
  14.  
  15. int calcK(int p)
  16. {
  17.     return (int)(sqrt(p)) + 1;
  18. }
  19.  
  20.  
  21.  
  22.  
  23. int ModPow(int base, int exp, int modulus)
  24. {
  25.   base %= modulus;
  26.   int result = 1;
  27.   while (exp > 0)
  28.   {
  29.     if (exp & 1) result = (result * base) % modulus;
  30.     base = (base * base) % modulus;
  31.     exp >>= 1;
  32.   }
  33.   return result;
  34. }
  35.  
  36. map <int, int> BuildFirstSeri(int y,int a,int m,int p)
  37. {
  38.     map<int, int> seri;
  39.     for (int i = 0; i < m; i++)
  40.     {
  41.        
  42.         seri.insert(pair<int, int>(i, y%p*ModPow(a, i, p)%p));
  43.     }
  44.     return seri;
  45. }
  46.  
  47. int getSolution (map<int,int> firstseri,int a, int k,int p)
  48. {
  49.     cout << "Second seri: ";
  50.     for (int i = 0; i < k; i++)
  51.     {
  52.         int tmpvalue=ModPow(a,(i+1)*k,p);
  53.  
  54.         cout << tmpvalue << " ";
  55.         for (auto x : firstseri)
  56.         {
  57.             if (x.second == tmpvalue)
  58.                 return k*(i+1)-x.first;
  59.         }
  60.        
  61.     }
  62.     return -1;
  63. }
  64.  
  65.  
  66. void PrintMap(map<int, int> mapToConsole)
  67. {
  68.     for (auto x : mapToConsole)
  69.         cout << x.second << " ";
  70.     cout << endl;
  71.  
  72. }
  73.  
  74. // y=a^xmodp
  75. int main()
  76. {
  77.     setlocale(LC_ALL, "Russian");
  78.     int y, a, p,k,m;
  79.     map<int, int> firstSeri;
  80.     Input(a,p,y);
  81.     k=m=calcK(p);
  82.     cout << "k:" << k << endl;
  83.     firstSeri = BuildFirstSeri(y, a, m,p);
  84.     cout << "First seri:";
  85.     PrintMap(firstSeri);
  86.     cout <<endl<< "solution: " << getSolution(firstSeri, a, k, p)<<endl;
  87.    
  88.    
  89.  
  90.     system("pause");
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement