В статье разберем алгоритм под названием Тест Миллера — Рабина. Он применяется при проверке числа на простоту.
Выполнять проверку числа на простоту требуется часто. Данная операция распространена и в задачах, и в алгоритмах.
Небольшое число легко проверить на простоту — достаточно в цикле перебрать все числа от 2 до N — 1 и проверить не делится ли N на них без остатка.
Но когда речь заходит об очень больших числах (содержащих в своем составе десятки разрядов) — такой подход не годится: вычисления займут большое время (часы, сутки).
В данном случае применяют специальные алгоритмы, называемые тестами на простоту. Рассмотрим один из таких тестов, он называется Тест Миллера — Рабина.
Тест Миллера — Рабина — описание алгоритма
Алгоритм является вероятностно-полиномиальным, т. е. быстро вычислимым (за приемлемое время) и дающим ответ с высокой точностью. При этом, жертвуя временем, можно добиться любой требуемой точности.
Таким образом, отвечая на вопрос «является ли число простым?», тест Миллера — Рабина дает один из двух вариантов ответа: «число составное» или «вероятно простое«.
Выполнив тест и получив положительный ответ, можно с большой вероятностью (но не 100%-й) утверждать, что число простое.
Ниже приведено описание алгоритма теста Миллера — Рабина на псевдокоде:
Тест Миллера — Рабина — реализация алгоритма
Приведем реализацию теста на языке программирования C#. Код снабжен комментариями.
Метод возвращает логическое значение true, если число n «вероятно простое», и false, если число n является составным.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
// тест Миллера — Рабина на простоту числа // производится k раундов проверки числа n на простоту public bool MillerRabinTest(BigInteger n, int k) { // если n == 2 или n == 3 - эти числа простые, возвращаем true if (n == 2 || n == 3) return true; // если n < 2 или n четное - возвращаем false if (n < 2 || n % 2 == 0) return false; // представим n − 1 в виде (2^s)·t, где t нечётно, это можно сделать последовательным делением n - 1 на 2 BigInteger t = n - 1; int s = 0; while (t % 2 == 0) { t /= 2; s += 1; } // повторить k раз for (int i = 0; i < k; i++) { // выберем случайное целое число a в отрезке [2, n − 2] RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider(); byte[] _a = new byte[n.ToByteArray().LongLength]; BigInteger a; do { rng.GetBytes(_a); a = new BigInteger(_a); } while (a < 2 || a >= n - 2); // x ← a^t mod n, вычислим с помощью возведения в степень по модулю BigInteger x = BigInteger.ModPow(a, t, n); // если x == 1 или x == n − 1, то перейти на следующую итерацию цикла if (x == 1 || x == n - 1) continue; // повторить s − 1 раз for (int r = 1; r < s; r++) { // x ← x^2 mod n x = BigInteger.ModPow(x, 2, n); // если x == 1, то вернуть "составное" if (x == 1) return false; // если x == n − 1, то перейти на следующую итерацию внешнего цикла if (x == n - 1) break; } if (x != n - 1) return false; } // вернуть "вероятно простое" return true; } |
В реализации используется структура BigInteger. Она позволяет хранить произвольно большие целые числа.
Тест Миллера — Рабина — видеоурок
В видео приводится разбор алгоритма и его реализация на C#.
Поделиться в соц. сетях: