Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 26 стр.

                                                                               27

1.10. Тест простоты Миллера–Рабина
     В качестве критерия проверки, является ли заданное число n простым
или составным, может служить следующая теорема:

Теорема 1.5. (Критерий непростоты) Нечетное число n ≥ 3 является
составным тогда и только тогда, когда n является либо полным
квадратом, либо найдутся два натуральных числа x и y такие, что

              x 6≡ ±y ( mod n), и x2 ≡ y 2 ( mod n).                        (1.7)

Доказательство. Если выполняются условия (1.7) , то Н.О.Д.(n, x2 − y 2 ) 6=
1, 6= n. Обратно, если n = p · q , где p > q , то определим x = (p + q)/2,
y = (p − q)/2. Очевидно, x и y удовлетворяют (1.7).

      На    критерии        непростоты    основан     известный    вероятностный
тест Миллера–Рабина, который старается найти пару x и y                    =   1,
удовлетворяющие критерию непростоты.
      Пусть    n–число,      которое     необходимо    проверить   на   простоту.
Представим n − 1 в виде n − 1 = 2s · d, где d–нечетно. Назовем
произвольное число a ∈Z ∗n свидетелем простоты n, если выполняет
одно из следующих условий:

           1. x = ad ≡ ±1 (mod n), или
                                k
        2. (∃k, 0 < k < s) x2 ≡ −1 (mod n).                                 (1.8)
В противном случае, назовем a свидетелем непростоты n.
      Докажем сначала, что если для числа n найдется хотя–бы один
свидетель его непростоты, то n–составное.
      Действительно, пусть для некоторого a ∈Z ∗n не выполнен ни один из
п.1–2 условий (1.8), тогда последовательность

  x0 = ad (mod n), x1 = x20 (mod n), ... , xs−1 = x2s−2 (mod n)

не содержит −1. Вычислим xs , равное x2s−1 ( mod n). Оно не равно 1. Но если
                        s
n–простое, то xs = ad·2 = an−1 должно равняться по малой теореме Ферма
единице. Значит, число n – составное.