В информатике тест Агравала — Каяла — Саксены (или тест AKS) — это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёными Маниндрой Агравалом, Нираджем Каялом и Нитином Саксеной и впервые опубликованный 6 августа 2002 года в статье «PRIMES is in P».^[1] До этой публикации принадлежность задачи распознавания простоты классу P являлась открытой проблемой. За своё открытие авторы получили премию Гёделя в 2006 году.

В 2005 году был предложен вариант алгоритма, который выполняется за (N ⁶) операций, где N — количество знаков в тестируемом числе (это соотношение можно записать как (log⁶ n), где n — само тестируемое число)^[2]

Свойства

Основным достижением авторов является то, что тест АКС является первым опубликованным алгоритмом проверки на простоту, который одновременно универсален, полиномиален, детерминирован и безусловен. Предыдущие алгоритмы обладали не более чем тремя из перечисленных свойств.

• Универсальность: Тест AKS может использоваться для проверки простоты любых чисел. Многие быстрые тесты предназначены для проверки чисел из ограниченного множества. Например, тест Люка́ — Лемера работает только для чисел Мерсенна, а тест Пепина применим лишь к числам Ферма.
• Полиномиальность: Наибольшее время работы алгоритма ограничено полиномом от количества цифр в проверяемом числе. Тесты ECPP и APR могут доказать или опровергнуть простоту числа, но для них не доказано, что время работы будет полиномиальным для любого входного числа.
• Детерминизм: Алгоритм гарантирует получение ответа. Вероятностные тесты, такие как тест Миллера — Рабина и тест BPSW (англ.), могут проверить простоту числа за полиномиальное время, но при этом дают лишь вероятностный ответ.
• Безусловность: Корректность теста AKS не зависит от каких-либо недоказанных гипотез. Напротив, тест Миллера детерминирован и работает за полиномиальное время для любого входного числа, но его корректность зависит от недоказанной обобщённой гипотезы Римана.

Примечания