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

                                                                         30

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

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

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

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

      1. Случайным образом выбирается число a < n, и вычисляется
d =Н.О.Д.(a, n).
      2. Если d > 1, то выносится решение о том, что n составное. Иначе
проверяется сравнение (1.9). Если оно не выполнено, то n - составное. Иначе,
a является свидетелем простоты числа n.
      Если после завершения k раундов найдено k свидетелей простоты, то
делаем заключение «n–вероятно простое число».

Вычислительная сложность и эффективность теста

      В каждом раунде вероятность отсеять составное число больше 1/2,
поэтому через k раундов тест Соловея–Штрассена определяет простое
число с вероятностью ошибки, меньшей 2−k . Поэтому этот тест сравним по
эффективности с тестом Ферма, но имеет преимущество перед тестом Ферма
в том, что он отсеивает все числа Кармайкла (см.разд. 1.19).
      С другой стороны, он проигрывает тесту Миллера–Рабина, который за
k раундов имеет ошибку, меньшую 4−k .
      Общая вычислительная сложность алгоритма оценивается как
O(k log2 n).