Алгоритм Агравала — Каяла — Саксены выглядит так:

• Если n представляет собой точную степень меньшего числа, выдаем СОСТАВНОЕ.

• Находим наименьшее r, такое, что наименьшая степень r, равная 1 по модулю n, больше или равна (log n)².

• Если какое-либо число, меньшее или равное r, имеет общий делитель с n, выдаем СОСТАВНОЕ.

• Если n меньше или равно r, выдаем ПРОСТОЕ.

• Для всех целых чисел a от 1 до определенного предела проверяем, совпадает ли многочлен (x + a)ⁿ с многочленом xⁿ + a по модулю n и по модулю x^r − 1. Если в обоих случаях ответ положительный, выдаем СОСТАВНОЕ.

• Выдаем ПРОСТОЕ.