Advertisement
Guest User

Untitled

a guest
May 20th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.55 KB | None | 0 0
  1. // производится k раундов проверки числа n на простоту
  2.         static bool MillerRabinTest(BigInteger n, int k) {
  3.             // если n == 2 или n == 3 - эти числа простые, возвращаем true
  4.             if (n == 2 || n == 3)
  5.                 return true;
  6.  
  7.             // если n < 2 или n четное - возвращаем false
  8.             if (n < 2 || n % 2 == 0)
  9.                 return false;
  10.  
  11.             // представим n − 1 в виде (2^s)·q, где t нечётно, это можно сделать последовательным делением n - 1 на 2
  12.             BigInteger q = n - 1;
  13.  
  14.             //Степень 2-ки
  15.             int s = 0;
  16.  
  17.             while (q % 2 == 0) {
  18.                 q /= 2;
  19.                 s += 1;
  20.             }
  21.  
  22.             // повторить k раз
  23.             for (int i = 0; i < k; i++) {
  24.                 // выберем случайное целое число a в отрезке [2, n − 2]
  25.                 RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
  26.  
  27.                 byte[] _a = new byte[n.ToByteArray().LongLength];
  28.  
  29.                 BigInteger a;
  30.  
  31.                 do {
  32.                     rng.GetBytes(_a);
  33.                     a = new BigInteger(_a);
  34.                 }
  35.                 while (a < 2 || a >= n - 2);
  36.  
  37.                 // x ← a^t mod n, вычислим с помощью возведения в степень по модулю
  38.                 BigInteger x = BigInteger.ModPow(a, q, n);
  39.  
  40.                 // если x == 1 или x == n − 1, то перейти на следующую итерацию цикла
  41.                 if (x == 1 || x == n - 1)
  42.                     continue;
  43.  
  44.                 // повторить s − 1 раз
  45.                 for (int r = 1; r < s; r++) {
  46.                     // x ← x^2 mod n
  47.                     x = BigInteger.ModPow(x, 2, n);
  48.  
  49.                     // если x == 1, то вернуть "составное"
  50.                     if (x == 1)
  51.                         return false;
  52.                        
  53.  
  54.                     // если x == n − 1, то перейти на следующую итерацию внешнего цикла
  55.                     if (x == n - 1)
  56.                         break;
  57.                 }
  58.  
  59.                 if (x != n - 1)
  60.                     return false;
  61.             }
  62.  
  63.             // вернуть "вероятно простое"
  64.             return true;
  65.         }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement