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

                                                                             39

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

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

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


2.15. Полиномиальный критерий простоты AKS
         Одной     из     важных   проблем,   долгое   время   стоявших   перед
исследователями, была проблема построения детерминированного алгоритма
проверки       простоты    натуральных   чисел,   имеющего     полиномиальную
оценку времени работы. Алгоритм Миллера–Рабина, упомянутый в
предыдущем разделе, имеет полиномиальную оценку, но не является
детерминированным. Другие тесты, например тест Поклингтона (разд.2.10),
являются детерминированными, но не имеют полиномиальной оценки.
      В 2004 г. тремя молодыми индийскими математиками Агравелой,
Каялом     и      Саксеной     ([1])   был    разработан   детерминированный
полиномиальный безусловный тест AKS проверки простоты заданного
натурального числа. Тест AKS основывается на следующей теореме: