Тестирование простоты за полиномиальное время: от рандомизированных алгоритмов до «PRIMES находится в P»

Самодостаточное рассмотрение теоретически и практически важных эффективных алгоритмов для проблемы простоты. В тексте рассматриваются рандомизированные алгоритмы Соловея-Штрассена и Миллера-Рабина конца 1970-х годов, а также недавний детерминистический алгоритм Агравала, Каяла и Саксены. Том написан для студентов, изучающих информатику, в частности, для тех, кто интересуется криптологией, и студентов, изучающих математику, и может использоваться в качестве дополнения к курсам или для самостоятельного изучения.