AKS素数判定法
p進のニュートン法を用いれば、各自然数 b {\displaystyle b} について n b {\displaystyle {\sqrt[{b}]{n}}} は O ~ ( log  ( n ) 2 ) {\displaystyle {\tilde {O}}(\log(n)^{2})} で計算できる。 n = a b {\displaystyle n=a^{b}} なる b {\displaystyle b} の上界は log 2  n {\displaystyle \log _{2}n} であるから、最初のステップは O ~ ( log  ( n ) 3 ) {\displaystyle {\tilde {O}}(\log(n)^{3})} で動作する。
第2ステップは、 r ≤ ⌈ 16 log  ( n ) 5 ⌉ {\displaystyle r\leq \lceil 16\log(n)^{5}\rceil } であったことを思い出せば、 O ~ ( log  ( n ) 7 ) {\displaystyle {\tilde {O}}(\log(n)^{7})} で動作するといえる。
第3ステップでは、ユークリッドの互除法を用いれば最大公約数 1 つを O ~ ( log  ( n ) ) {\displaystyle {\tilde {O}}(\log(n))} で計算できる。これを O ( r ) = O ( log  ( n ) 5 ) {\displaystyle O(r)=O(\log(n)^{5})} 回繰り返すので、第3ステップにかかる時間は O ~ ( log  ( n ) 6 ) {\displaystyle {\tilde {O}}(\log(n)^{6})} である。
であることは、 n {\displaystyle n} は合成数であることと同値である。
このことは、二項定理により各次数の係数を評価すれば容易に証明できる。
上の式は、 X {\displaystyle X} が恒等的に 0 だと思えばフェルマーの小定理の対偶そのものである。つまり、上の条件による判定はフェルマーテストをより厳密にしたものといえる。
厳密にしたことによりフェルマーテストとは異なり必要十分条件を与えている。したがって上の合同式を真面目に評価してやれば素数性を判定する決定性アルゴリズムができるが、これは時間がかかりすぎる。つまり、最悪の場合 n {\displaystyle n} 個の係数を評価しなければならないので、これは n {\displaystyle n} のビット数に対して指数関数時間である。
そこでもう少し大雑把に評価することにする。具体的には、何らかの小さい r {\displaystyle r} をとって X r − 1 {\displaystyle X^{r}-1} を法として評価する。すると、 X r − 1 {\displaystyle X^{r}-1} による剰余は高々 r − 1 {\displaystyle r-1} 次だから、評価する係数の数を減らすことができる。
アルチン予想を認めるならば r = O ( log  ( n ) 2 ) {\displaystyle r=O(\log(n)^{2})} である。
ソフィー・ジェルマン素数の密度予想が正しいと仮定すれば、 r = O ~ ( log  ( n ) 2 ) {\displaystyle r={\tilde {O}}(\log(n)^{2})} である。
これらの仮説はともに一般リーマン仮説を認めれば証明できる。多くの数学者がリーマン仮説は正しいと信じていることを考えれば、 r = O ( log  ( n ) 2 ) {\displaystyle r=O(\log(n)^{2})} つまり、AKSアルゴリズムの時間的計算量が O ~ ( log  ( n ) 6 ) {\displaystyle {\tilde {O}}(\log(n)^{6})} である見込みは高い。