For a polynomial $C(x)=c_0+\dots+c_n x^n$, consider a circulant matrix $C$ such that $$ C= \begin{pmatrix} c_0 & c_{n-1} & \cdots & c_2 & c_1 \\ c_1 & c_0 & c_{n-1} & & c_2 \\ \vdots & c_1 & c_0 & \ddots & \vdots \\ c_{n-2} & & \ddots & \ddots & c_{n-1} \\ c_{n-1} & c_{n-2} & \cdots & c_1 & c_0 \\ \end{pmatrix} $$ Its inverse is also a circulant matrix formed from the polynomial $C^{-1}(x) \pmod{x^n-1}$.
A classic way to find $C^{-1}(x)$ computationally is to perform discrete Fourier transform on $C(x)$, then invert the resulting values, and make the inverse transform. If one of the values is $0$, then the matrix is not invertible.
I'm considering circular matrices with elements from $GF(p)$, meaning that we would need to look for an inverse in the ring $\mathbb Z_p[x]/(x^n-1)$ rather than $\mathbb C[x]/(x^n-1)$. A significant caveat here is that unless $n$ divides $p-1$, it is not possible to conduct NTT over $GF(p)$. So far, some ways to consider on how to do this:
- Use extended Euclidean algorithm to find $C^{-1}(x) \pmod{x^n-1}$. Best-known algorithm (half-GCD) for this seems to work in $O(n \log^2 n)$ for this, is pretty complicated and has a large constant-time overhead.
- Try to work in a field extension of $GF(p)$ that contains the primitive root of $1$ of degree $n$. This essentially means working modulo $n$-th cyclotomic polynomial, which is most likely not doable in sub-quadratic time.
- Find inverse in $\mathbb C[x]/(x^n-1)$. It will be rational and can be converted back to remainders modulo $p$, but the precision needed to do this is probably too high for it to be feasible.
Are there any other viable approaches here to do this in a simpler manner, or reduce the runtime to $O(n \log n)$?
