各ステップの評価
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 10:07 UTC 版)
「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})} である。 第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})} であるといえる。
※この「各ステップの評価」の解説は、「AKS素数判定法」の解説の一部です。
「各ステップの評価」を含む「AKS素数判定法」の記事については、「AKS素数判定法」の概要を参照ください。
- 各ステップの評価のページへのリンク
