Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- using namespace::std;
- void Input(int&a, int&p, int&y)
- {
- cout << "Введите a,p,y: ";
- cin >> a >> p >> y;
- }
- int calcK(int p)
- {
- return (int)(sqrt(p)) + 1;
- }
- int ModPow(int base, int exp, int modulus)
- {
- base %= modulus;
- int result = 1;
- while (exp > 0)
- {
- if (exp & 1) result = (result * base) % modulus;
- base = (base * base) % modulus;
- exp >>= 1;
- }
- return result;
- }
- map <int, int> BuildFirstSeri(int y,int a,int m,int p)
- {
- map<int, int> seri;
- for (int i = 0; i < m; i++)
- {
- seri.insert(pair<int, int>(i, y%p*ModPow(a, i, p)%p));
- }
- return seri;
- }
- int getSolution (map<int,int> firstseri,int a, int k,int p)
- {
- cout << "Second seri: ";
- for (int i = 0; i < k; i++)
- {
- int tmpvalue=ModPow(a,(i+1)*k,p);
- cout << tmpvalue << " ";
- for (auto x : firstseri)
- {
- if (x.second == tmpvalue)
- return k*(i+1)-x.first;
- }
- }
- return -1;
- }
- void PrintMap(map<int, int> mapToConsole)
- {
- for (auto x : mapToConsole)
- cout << x.second << " ";
- cout << endl;
- }
- // y=a^xmodp
- int main()
- {
- setlocale(LC_ALL, "Russian");
- int y, a, p,k,m;
- map<int, int> firstSeri;
- Input(a,p,y);
- k=m=calcK(p);
- cout << "k:" << k << endl;
- firstSeri = BuildFirstSeri(y, a, m,p);
- cout << "First seri:";
- PrintMap(firstSeri);
- cout <<endl<< "solution: " << getSolution(firstSeri, a, k, p)<<endl;
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement