Can anyone please help me to understand what the complexity of checking whether $$ f(x) \equiv g(x) \hspace{3mm} (\text{mod } h(x), n) $$ might be? This notation denotes that $f(x)$ is congruent to $g(x)$ in the quotient polynomial ring $\mathbb{Z}_n / h(x)$.

I am basing this question on my attempt to understand the complexity of the AKS primality test algorithm found here (on page 3). In particular, I am trying to understand the complexity of line 5.

On page 6 they say that the complexity of line 5 is $O (r \sqrt{\phi (r)} \log^3 n)$. Clearly, the while statement on this line will loop (a maximum of) $\sqrt{\phi (r)} \log n$ times. Thus, denoting by $f(n)$ the maximum number of operations required for checking whether $$ (X + a)^n \neq X^n + a \hspace{6mm} (\text{mod} \hspace{2mm} X^r - 1, \hspace{2mm} n) $$ we must have $$ O(f(n) \sqrt{\phi (r)} \log n) = O(r \sqrt{\phi (r)} \log^3 n) $$

Thus, I am assuming that $$ f(n) = r \cdot \log^2 n $$

However, I do not know whether this is correct.

  • 1
    $\begingroup$ What model of computation are you interested in? Do you count basic operations modulo $n$ as running in $O(1)$ time? $\endgroup$
    – D.W.
    Commented Mar 9, 2018 at 16:58
  • $\begingroup$ I am not certain. I have edited my post to give more background. I don't know if this makes the answer more obvious? $\endgroup$
    – M Smith
    Commented Mar 9, 2018 at 22:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.