AKS素数判定法
第4ステップは、単に比較するだけであるから O ( log  n ) {\displaystyle O(\log n)} である。
第5ステップでは、 mod X r − 1 {\displaystyle \mod X^{r}-1} で考えているので多項式の次数は高々 r − 1 {\displaystyle r-1} であり、 mod n {\displaystyle \mod n} で考えているので係数は高々 n − 1 {\displaystyle n-1} である。高速フーリエ変換を用いれば、このような多項式の冪は O ~ ( r log  ( n ) 2 ) {\displaystyle {\tilde {O}}(r\log(n)^{2})} で計算される。繰り返しの回数をかければ、第5ステップは O ~ ( r φ ( r ) log  ( n ) 3 ) = O ~ ( log  ( n ) 10.5 ) {\displaystyle {\tilde {O}}(r{\sqrt {\phi (r)}}\log(n)^{3})={\tilde {O}}(\log(n)^{10.5})} で動作するといえる。
第6ステップは、定数時間である。
したがって、全体の時間は O ~ ( log  ( n ) 10.5 ) {\displaystyle {\tilde {O}}(\log(n)^{10.5})} であるといえる。