# What is the complexity of checking whether $f(x) \equiv g(x) \hspace{3mm} (\text{mod } h(x), n)$?

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.

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