fork(2) download
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <math.h>
  5.  
  6. // Нахождение GCD
  7. long long gcd(long long a, long long b){
  8. if(b == 0)
  9. return a;
  10. return gcd(b, a % b);
  11. }
  12.  
  13. // Двоичное умножение по модулю для защиты от переполнений
  14. long long mul(long long a, long long b, long long m){
  15. if(b == 1)
  16. return a;
  17. if(b % 2 == 0){
  18. long long t = mul(a, b/2, m);
  19. return (2 * t) % m;
  20. }
  21. return (mul(a, b - 1, m) + a) % m;
  22. }
  23.  
  24. // Возведение в степень по модулю
  25. long long modpow (long long a, long long b, long long m){
  26. if(b==0)
  27. return 1;
  28. if(b % 2 == 0){
  29. long long t = modpow (a, b/2, m);
  30. return mul(t, t, m) % m;
  31. }
  32. return (mul(modpow (a, b - 1, m), a, m)) % m;
  33. }
  34.  
  35. int jacobi (int nominator, int denominator)
  36. {
  37. int s = 0;
  38. int remainder, power_of_two, t;
  39. do{
  40. remainder = nominator % denominator;
  41. power_of_two = t = 0;
  42. while(remainder % 2 == 0)
  43. {
  44. power_of_two++;
  45. remainder >>= 1;
  46. }
  47. t = remainder;
  48. s = (s + power_of_two * (denominator * denominator - 1) / 8 + (t - 1) * (denominator - 1) / 4) % 2;
  49. if(t == 1)
  50. return (s) ? -1 : 1;
  51. nominator = denominator;
  52. denominator = t;
  53. }while(t >= 3);
  54. }
  55.  
  56. int main(int argc, char* argv[])
  57. {
  58. long n; /*n > 2, нечетное натуральное число, которое необходимо проверить на простоту*/
  59. long k; /* параметр, определяющий точность теста */
  60. long a;
  61. long residue;
  62. double t;
  63. int flag = 0;
  64.  
  65. std::cin >> n;
  66. std::cin >> k;
  67. t = 1 - 1 / pow(2.0, k);
  68.  
  69. srand(time(NULL));
  70.  
  71. for (int i=1; i <= k; i++)
  72. {
  73. a = rand() % (n - 2) + 2;
  74. long long p = modpow(a, (n - 1) / 2, n);
  75. int j = jacobi (a, n);
  76. residue = p - n;
  77.  
  78. if (gcd(a, n) != 1)
  79. {
  80. flag = 1;
  81. break;
  82. }
  83. else if (residue != j)
  84. {
  85. std::cout << "[DEBUG]: p - n = " << (p - n) << std::endl;
  86. std::cout << "[DEBUG]: residue = " << residue << std::endl;
  87. std::cout << "[DEBUG]: modpow = " << p << std::endl;
  88. std::cout << "[DEBUG]: jacobi = " << j << std::endl;
  89. flag = 2;
  90. break;
  91. }
  92. }
  93.  
  94.  
  95. if (flag !=0)
  96. {
  97. std::cout << "composite \n";
  98. }
  99. else
  100. std::cout<<"prime with possibility " << t << "\n";
  101. return 0;
  102. }
Success #stdin #stdout 0s 3420KB
stdin
311 10
stdout
[DEBUG]: p - n = -310
[DEBUG]: residue = -310
[DEBUG]: modpow = 1
[DEBUG]: jacobi = 1
composite