Алгоритм AKS

1. Делимость5 n на числа от 2 до проверяется≤ 5 в лоб;

2. Ищется r , для которого выполняется(i)в теореме 2;

3. Проверяется (iii);

4. Проверяется не извлекается ли из n целый корень.

Доказано~, что сложность7,5 алгоритма довольно высока поэтому практической ценности алгоритм пока не имеет.