AKS素数判定法
第5ステップで用いている判定法は、累乗数についてはうまく働かない。累乗数であるならばすなわち合成数なのだから、最初のステップにおいて累乗数であると判明した場合には「合成数である」と出力して終了する。
次に、 n {\displaystyle n} の位数が十分に大きくなるような法 r {\displaystyle r} を求める。このような r {\displaystyle r} が存在するのかどうかが問題となるが、最小公倍数に関する議論から r ≤ ⌈ 16 log  ( n ) 5 ⌉ {\displaystyle r\leq \lceil 16\log(n)^{5}\rceil } までに存在することが示される。
その次に、 n {\displaystyle n} が実際に ( Z / r Z ) × {\displaystyle (\mathbb {Z} /r\mathbb {Z} )^{\times }} の元であるかを確かめている。これは第5ステップが正しく動作するために必要である。 ( Z / r Z ) × {\displaystyle (\mathbb {Z} /r\mathbb {Z} )^{\times }} に属する必要十分条件が (n, r) = 1 であるが、この段階で最大公約数が 1 でなかったなら、それはつまり n {\displaystyle n} の非自明な因数が発見されたということであるから、「合成数である」と出力して終了する。
AKSアルゴリズムの時間的計算量は高々 O ~ ( log  ( n ) 7.5 ) {\displaystyle {\tilde {O}}(\log(n)^{7.5})} である。
PRIMES is in P の初版では、このアルゴリズムは O ~ ( log  ( n ) 12 ) {\displaystyle {\tilde {O}}(\log(n)^{12})} のアルゴリズムとして提示された。その後の改訂を経て、現在では O ~ ( log  ( n ) 7.5 ) {\displaystyle {\tilde {O}}(\log(n)^{7.5})} であることが証明されている。しかし、実際には O ~ ( log  ( n ) 6 ) {\displaystyle {\tilde {O}}(\log(n)^{6})} であろうと考えられている。また、現在の証明は篩理論の高度な結果によっているが、初歩的な代数学の知識だけでも O ~ ( log  ( n ) 10.5 ) {\displaystyle {\tilde {O}}(\log(n)^{10.5})} であることは証明できる。