Тест Агравала-Каяла-Саксена - полиномиальный детерминированный тест простоты чисел.

АКС - первый опубликованный тест на простоту, который одновременно:

• универсален - проверка любого числа
• полиномиален - время ограничено полиномом от количества цифр в числе
• детерминизм - алгоритм гарантирует получение ответа
• безусловность - корректность не зависит от недоказанных гипотез.

Комментарии