I am asking this question to improve my understanding of the paper PRIMES is in P and the complexity of the algorithm described within it (on page 3).
In particular, I am wondering what the complexity of checking the congruence $$ (x+a)^n \equiv x^n + a \pmod{x^r-1, n} $$ on line 5 might be.
In section 5 (page 6) of this paper, they tell us that checking this congruence requires
- $O(\log n)$ multiplications
- ... of degree $r$ polynomials
- ... with coefficients of size $\log n$
Now if I could understand why the above is true, I would be able to understand the complexity of checking this congruence.
Note: The AKS primality test states that a number $n$ is prime iff $$ (x+a)^n \equiv x^n + a \pmod{n} $$ where $a$ is coprime to $n$. However, this is not a polynomial time algorithm since the expansion of the lhs will have $n+1$ terms, and each of these must be analyzed separately. The importance of this test stems from the fact that it is "obvious to see" that this congruence is satisfied iff the congruence $$ (x+a)^n \equiv x^n + a \pmod{x^r-1, n} $$ is satisfied. And this second congruence can be verified in polynomial time.
Based on the above, taken from the paper, I am presuming that (unlike the first congruence) the second congruence does not require us to expand the bracket on the lhs. Why is this?
One needs to compute $(x+a)^n$ modulo $x^r-1$ in the ring $R=(\Bbb Z/n\Bbb Z)[x]$. In other words find the unique $f(x)\in R$ of degree $< r$ such that $(x+a)^n\equiv f(x)\pmod{x^r-1}$ in $R$.
One can do this by adapting the exponentiation via squaring algorithm. To compute $(x+a)^m$ modulo $x^r-1$ when $m$ is even, first find $g(x)\equiv(x+a)^{m/2}\pmod{x^r-1}$ and then reduce $g(x)^2$ module $x^r-1$. When $m$ is odd, first find $h(x)\equiv (x+a)^{(m-1)/2}\pmod{x^r-1}$ and then reduce $(x+a)h(x)^2$ modulo $x^r-1$.
This method requires $O(\log n)$ iterations.