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

                                                                         38

Оценка эффективности теста Миллера–Рабина

            Следующая лемма была доказана Рабином в предположении
справедливости обобщенной гипотезы Римана о распределении простых
чисел (с. ??):

Лемма 2.1. Пусть число n–нечетное число, и n−1 = 2s ·d, где d–нечетно.
Если для всех x, 0 < x < 2 · ( log2 n)2 выполняется xd ≡ 1 (mod n), или
  k
      ·d
x2         ≡ −1 (mod n) для некоторого 0 ≤ k < s. Тогда число n является
простым.

Оценка, приведенная в этой лемме, является полиномиальной, однако,
с теоретической точки зрения она не может быть использована, пока
не доказана обобщенная гипотеза Римана, которая на сегодняшний день
является самой известной из нерешенных «проблем тысячелетия». Кроме
того, для практических расчетов эта оценка является сильно завышенной.
                                                                 ˙
Вместо нее обычно используется граница порядка O(log2 n) (см. [?]).


2.14. Вероятностный тест простоты Соловея–Штрассена
           Тест Соловея — Штрассена опирается на малую теорему Ферма (разд.
2.2) и свойства символа Якоби (разд. 2.12):

Теорема 2.6. Если n — нечетное составное число, то количество целых
чисел a, взаимно простых с n и меньших n, удовлетворяющих сравнению
                         ( )
                          a
              a(n−1)/2
                       ≡     ( mod n),                         (2.12)
                          n

не превосходит n/2.

Алгоритм Соловея — Штрассена

           Сначала для алгоритм Соловея — Штрассена выбирается целое число
k ≥ 1. Тест проверки простоты числа n состоит из k отдельных раундов. В
каждом раунде выполняются следующие действия: