Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- long long Euklides(long long a, long long b)
- {
- while( a != b )
- {
- if( a < b )
- {
- b = b - a;
- }
- else
- {
- a = a - b;
- }
- }
- return a;
- }
- long long odwr_mod ( long long a, long long n )
- {
- long long a0, n0, p0, p1, q, r, t;
- p0 = 0; p1 = 1; a0 = a; n0 = n;
- q = n0 / a0;
- r = n0 % a0;
- while( r > 0 )
- {
- t = p0 - q * p1;
- if( t >= 0 )
- t = t % n;
- else
- t = n - ( ( -t ) % n );
- p0 = p1; p1 = t;
- n0 = a0; a0 = r;
- q = n0 / a0;
- r = n0 % a0;
- }
- return p1;
- }
- long long kluczPrywatny(long long e, long long phi)
- {
- long long d;
- for( e = 3; Euklides( e, phi ) != 1; e += 2 );
- d = odwr_mod ( e, phi );
- return d;
- }
- long long potegowanie(long long a, long long n) //potegowanie metoda wielokrotnych kwadratów
- {
- long long wynik = 1;
- while(n > 0)
- {
- if(n % 2 == 1) // jeśli bit jest = 1
- wynik = wynik * a;
- a = a*a;
- n/=2; //skrocenie o bit
- }
- return wynik;
- }
- long long funEulera(long long p, long long q)
- {
- return (p-1)*(q-1);
- }
- long long modulN(long long p, long long q)
- {
- return p*q;
- }
- int main()
- {
- int t;
- cin >> t;
- long long n;
- long long p,q,e,c;
- long long klucz_pryw,phi,d;
- for (int i = 0; i < t; i++)
- {
- cin >> p >> q >> e >> c;
- n = modulN(p,q);
- phi = funEulera(p,q);
- d = kluczPrywatny(e,phi);
- klucz_pryw = potegowanie(c,d) %n;
- cout << klucz_pryw << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement