Тест Агравала — Каяла — Саксены

---

Тест Аграва́ла — Кая́ла — Саксе́ны (тест AKS) — единственный известный на данный момент универсальный (то есть применимый ко всем числам) полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.

Если существует ${\displaystyle r\in \mathbb {Z} }$ такое, что ${\displaystyle o_{r}(n)>\log ^{2}n}$ и для любого ${\displaystyle a}$ от 1 до ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log(n)\right\rfloor }$ выполняется сравнение ${\displaystyle (x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n}}}$,
то ${\displaystyle n}$ — либо простое число, либо степень простого числа.

Здесь и далее ${\displaystyle o_{r}(n)}$ обозначает показатель числа ${\displaystyle n}$ по модулю ${\displaystyle r}$, ${\displaystyle \log }$ — двоичный логарифм и ${\displaystyle \varphi (\cdot )}$ — функция Эйлера^[1].

---