Advertisement
Guest User

Untitled

a guest
Feb 17th, 2020
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. long long Euklides(long long a, long long b)
  6. {
  7. while( a != b )
  8. {
  9. if( a < b )
  10. {
  11. b = b - a;
  12. }
  13. else
  14. {
  15. a = a - b;
  16. }
  17. }
  18. return a;
  19. }
  20.  
  21. long long odwr_mod ( long long a, long long n )
  22. {
  23. long long a0, n0, p0, p1, q, r, t;
  24.  
  25. p0 = 0; p1 = 1; a0 = a; n0 = n;
  26. q = n0 / a0;
  27. r = n0 % a0;
  28. while( r > 0 )
  29. {
  30. t = p0 - q * p1;
  31. if( t >= 0 )
  32. t = t % n;
  33. else
  34. t = n - ( ( -t ) % n );
  35. p0 = p1; p1 = t;
  36. n0 = a0; a0 = r;
  37. q = n0 / a0;
  38. r = n0 % a0;
  39. }
  40. return p1;
  41. }
  42.  
  43. long long kluczPrywatny(long long e, long long phi)
  44. {
  45. long long d;
  46. for( e = 3; Euklides( e, phi ) != 1; e += 2 );
  47. d = odwr_mod ( e, phi );
  48. return d;
  49. }
  50.  
  51. long long potegowanie(long long a, long long n) //potegowanie metoda wielokrotnych kwadratów
  52. {
  53. long long wynik = 1;
  54.  
  55. while(n > 0)
  56. {
  57. if(n % 2 == 1) // jeśli bit jest = 1
  58. wynik = wynik * a;
  59.  
  60. a = a*a;
  61. n/=2; //skrocenie o bit
  62. }
  63. return wynik;
  64. }
  65.  
  66. long long funEulera(long long p, long long q)
  67. {
  68. return (p-1)*(q-1);
  69. }
  70.  
  71. long long modulN(long long p, long long q)
  72. {
  73. return p*q;
  74. }
  75.  
  76. int main()
  77. {
  78. int t;
  79. cin >> t;
  80. long long n;
  81. long long p,q,e,c;
  82. long long klucz_pryw,phi,d;
  83.  
  84. for (int i = 0; i < t; i++)
  85. {
  86. cin >> p >> q >> e >> c;
  87. n = modulN(p,q);
  88. phi = funEulera(p,q);
  89. d = kluczPrywatny(e,phi);
  90. klucz_pryw = potegowanie(c,d) %n;
  91. cout << klucz_pryw << endl;
  92. }
  93. return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement