Тест на простоту Rabin-Miller

1) Сгенерируем случайное n-битовое число p

101010101010101010101

2) Установите старший и младший биты равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший бит обеспечивает его нечетность.)

101010101010101010101
p =
1234567

3) Убедитесь, что p не делиться на небольшие простые числа: 3, 5 7, 11, и т.д. Во многих реализациях проверяется делимость p на все простые числа, меньшие 256. Наиболее эффективной является проверка на делимость для всех простых чисел, меньших 2000. Это может быть эффективно выполнено с помощью колеса.

4) Выполните тест Rabin-Miller для некоторого случайного числа a. Если p проходит тест, сгенерируйте другое случайное a и повторите проверку. Выбирайте небольшие значения a для ускорения вычислений. Выполните пять тестов. (Одного может показаться достаточным, но выполните пять.) Если p проходит одной из проверок, сгенерируйте другое p и попробуйте снова.

Шаги проверки Rabin–Miller

Вычислите b - число делений p - 1 на 2 (т.е., 2b - это наибольшая степень числа 2,
на которое делиться p - 1).

Затем вычислите m, такое что p = 1 + 2b * m.
  1. Выберите случайное целое a в диапазоне [2, p−1].
  2. Установите j = 0 и z = am mod p.
  3. Если z = 1 или если z = p - 1, то p проходит проверку и может быть простым числом.
  4. Если j > 0 и z = 1, то p не является простым числом.
  5. Установите j = j + 1. Если j < b и z (p - 1, установите z = z2 mod p и вернитесь на этап (4). Если z = p - 1, то p проходит проверку и может быть простым числом.)
  6. Если j = b и z ≠ p - 1, то p не является простым числом.
a ∈ [2, p-1]