AKS素数判定法
全体の時間を支配しているのは、第5ステップの時間であり、ひいては r {\displaystyle r} の大きさである。したがって、実は r {\displaystyle r} は ⌈ 16 log  ( n ) 5 ⌉ {\displaystyle \lceil 16\log(n)^{5}\rceil } よりも小さく定まるということを証明できれば、計算量の評価を改善することができる。
篩理論より r = O ( log  ( n ) 3 ) {\displaystyle r=O(\log(n)^{3})} であるということが分かるので、実際にはアルゴリズムは O ~ ( log  ( n ) 7.5 ) {\displaystyle {\tilde {O}}(\log(n)^{7.5})} で動作する。
更に、いくつかの証明されていない仮説を認めるならば、 r {\displaystyle r} の評価をより小さくできる。
素数性を判定すべき、2以上の自然数 n {\displaystyle n} を入力する。
もし、 n {\displaystyle n} が累乗数であるならば「合成数である」と出力してアルゴリズムを終了する。
o r ( n ) > 4 log 2  n {\displaystyle o_{r}(n)>4\log ^{2}n} になる最小の r {\displaystyle r} を見つける。
もし、ある a ≤ r {\displaystyle a\leq r} に対して 1 < ( a , n ) < n {\displaystyle 1<(a,n)<n} ならば、「合成数である」と出力してアルゴリズムを終了する。
もし、 n ≤ r {\displaystyle n\leq r} ならば、「素数である」と出力してアルゴリズムを終了する。
1 {\displaystyle 1} から [ 2 φ ( r ) log  n ] {\displaystyle [2{\sqrt {\phi (r)}}\log n]} まで、順に a {\displaystyle a} を動かすものとする。