0
$\begingroup$

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.

$\endgroup$
  • 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. Mar 9 '18 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 Mar 9 '18 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.