Algorithm for determining whether $\gcd$ of two polynomials is unequal $1$, for use in Schoof's algorithm and $ECC$

Question

I'm currently working on a $ECC$ Project. In the implementation of Schoof's Algorithm we need to check, if the following property holds for high order q: $$\gcd\left(x^q-x,x^3 + Ax +B\right) \neq 1$$ An easy way to compute this is using the Euclidean algorithm and polynomial division, but is there an asymptotically faster way to find this result?

Answer 1

The Euclidean algorithm does not work efficiently enough here since $q$ is typically an enormous number in the context of Schoof's algorithm. The correct method is to use modular exponentiation (square and multiply) to compute $x^q \bmod (x^3 + ax + b)$, which yields a remainder $r(x)$ of degree at most $2$, and then compute $\gcd(r(x)-x, x^3+ax+b)$ using the Euclidean algorithm.