Let $n$ be an odd number, $D=a^2+4$ and $(D | n)=-1$ where $(D | n)$ is the Jacobi symbol.
Then $n$ is prime if and only if
$(x^2 + ax)^n = x^3 - x^2 + (D-2)x - D \pmod {{x^4 + Dx^2 + D},n}$
or
$(x^2 - ax)^n = x^3 - x^2 + (D-2)x - D \pmod {{x^4 + Dx^2 + D},n}$
I have constructed a proof (here) for the converse of this test but not the actual test itself. Are there counterexamples? A heuristic argument suggesting a counterexample?
There are no counterexamples for any $(|a|,n) < 10000$.
The idea for this algorithm came from a version of Agrawal's Conjecture with $r=5$ involving a quartic polynomial, without resorting to higher-degree polynomials (larger values of $r$). It is much easier to use a constructed family of cyclic quartic polynomials with one free parameter.
You can run the test here;
Also related is this conjecture/test here (which also gave me an idea for this test).
This is a partial answer.
This answer proves the following claim :
Claim : If $n$ is an odd prime, then $$(x^2 \pm ax)^n\equiv \pm ab_nx^3-x^2\mp aDb_{n-2}x-D\pmod{x^4 + Dx^2 + D,n}$$ where$$b_n=\frac{(-D+|a|\sqrt D)^{(n-1)/2}-(-D-|a|\sqrt D)^{(n-1)/2}}{2^{(n-1)/2}|a|\sqrt D}$$
The claim follows from the following four lemmas :
Lemma 1 : $$(x^2 \pm ax)^n\equiv \pm ax^n+x^{2n}\pmod{n}$$
Lemma 2 : $$\pm ax^n+x^{2n}\equiv \pm ab_nx^3+b_{2n+1}x^2\mp aDb_{n-2}x-Db_{2n-1}\pmod{x^4 + Dx^2 + D}$$where$$b_n=\frac{(-D+|a|\sqrt D)^{(n-1)/2}-(-D-|a|\sqrt D)^{(n-1)/2}}{2^{(n-1)/2}|a|\sqrt D}$$
Lemma 3 : $$b_{2n+1}\equiv -1\pmod n$$
Lemma 4 : $$Db_{2n-1}\equiv D\pmod n$$
Lemma 1 : $$(x^2 \pm ax)^n\equiv \pm ax^n+x^{2n}\pmod{n}$$
Proof for lemma 1 :
By the binomial theorem, we have $$(x^2\pm ax)^n=\sum_{k=0}^{n}\binom nk(x^2)^{n-k}(\pm ax)^k$$ Since $\binom nm\equiv 0\pmod n$ for $1\le m\le n-1$, we get $$(x^2\pm ax)^n\equiv (\pm ax)^n+x^{2n}=\pm a^nx^n+x^{2n}\equiv \pm ax^n+x^{2n}\pmod n$$
Lemma 2 : $$\pm ax^n+x^{2n}\equiv \pm ab_nx^3+b_{2n+1}x^2\mp aDb_{n-2}x-Db_{2n-1}\pmod{x^4 + Dx^2 + D}$$
Proof for lemma 2 :
Let $b_nx^3+c_nx^2+d_nx+e_n$ be the remainder when $x^n$ is divided by $x^4 + Dx^2 + D$. Then, we get $$b_{n+1}=c_n,\quad c_{n+1}=-Db_n+d_n,\quad d_{n+1}=e_n,\quad e_{n+1}=-Db_n$$ from which we have $$b_{n+2}=-Db_{n}-Db_{n-2}$$ which can be written as $$b_{n+2}+kb_n=m(b_{n}+kb_{n-2})$$ where $$m=\frac{-D+|a|\sqrt D}{2},\qquad k=\frac{D+|a|\sqrt D}{2}$$ So, we get $$b_n+kb_{n-2}=m(b_{n-2}+kb_{n-4})=\cdots =m^{(n-3)/2}(b_{3}+kb_1)=m^{(n-3)/2}$$ Dividing by $(i\sqrt k)^n$ gives
$$f_n-f_{n-2}=\frac{m^{(n-3)/2}}{(i\sqrt k)^n}:=g(n)$$ where $f_n=\frac{b_n}{(i\sqrt k)^n}$.
So, we get
$$f_n=f_1+\sum_{j=1}^{(n-1)/2}g(2j+1)$$ from which we have $$b_n=(i\sqrt k)^nf_n=\frac{(-D+|a|\sqrt D)^{(n-1)/2}-(-D-|a|\sqrt D)^{(n-1)/2}}{2^{(n-1)/2}|a|\sqrt D}$$
Finally, we get $$\begin{align}\pm ax^n+x^{2n}&\equiv \pm a(b_nx^3+c_nx^2+d_nx+e_n)+b_{2n}x^3+c_{2n}x^2+d_{2n}x+e_{2n} \\\\&\equiv \pm ab_nx^3+b_{2n+1}x^2\mp aDb_{n-2}x-Db_{2n-1}\pmod{x^4 + Dx^2 + D}\end{align}$$
Lemma 3 : $$b_{2n+1}\equiv -1\pmod n$$
Proof for lemma 3 :
From lemma 2, we get
$$\begin{align}2^{n-1}b_{2n+1}&=\frac{(D+|a|\sqrt D)^{n}+(-D+|a|\sqrt D)^{n}}{2|a|\sqrt D} \\\\&=\frac{1}{2|a|\sqrt D}\sum_{k=0}^{n}\binom nk(|a|\sqrt D)^{n-k}(D^k+(-D)^k) \\\\&=\frac{1}{|a|\sqrt D}\sum_{j=0}^{(n-1)/2}\binom n{2j}(|a|\sqrt D)^{n-2j}D^{2j} \\\\&=\sum_{j=0}^{(n-1)/2}\binom n{2j}(|a|\sqrt D)^{n-2j-1}D^{2j} \\\\&\equiv a^{n-1}\cdot D^{(n-1)/2}\pmod n \\\\&\equiv -1\pmod n\end{align}$$ from which we have $$b_{2n+1}\equiv -1\pmod n$$
Lemma 4 : $$Db_{2n-1}\equiv D\pmod n$$
Proof for lemma 4 :
$$\begin{align}2^{n}b_{2n+3}&=-\frac{1}{2|a|\sqrt D}(D+|a|\sqrt D)(D+|a|\sqrt D)^{n} \\&\qquad\qquad +\frac{1}{2|a|\sqrt D}(-D+|a|\sqrt D)(-D+|a|\sqrt D)^{n} \\\\&=-\frac{\sqrt D}{2|a|}\bigg((D+|a|\sqrt D)^{n}+(-D+|a|\sqrt D)^{n}\bigg) \\&\qquad\qquad +\frac 12\bigg(-(D+|a|\sqrt D)^{n}+(-D+|a|\sqrt D)^{n}\bigg) \\\\&=-\frac{\sqrt D}{2|a|}\sum_{k=0}^{n}\binom nk(|a|\sqrt D)^{n-k}(D^k+(-D)^k) \\&\qquad\qquad +\frac 12\sum_{k=0}^{n}\binom nk(|a|\sqrt D)^{n-k}(-D^k+(-D)^k) \\\\&=-\sum_{j=0}^{(n-1)/2}\binom n{2j}(|a|\sqrt D)^{n-2j-1}D^{2j+1} \\&\qquad\qquad-\sum_{j=1}^{(n+1)/2}\binom n{2j-1}(|a|\sqrt D)^{n-2j+1}D^{2j-1} \\\\&\equiv -a^{n-1}D^{(n+1)/2}-D^n\pmod n \\\\&\equiv 0\pmod n\end{align}$$ from which we have $$b_{2n+3}\equiv 0\pmod n$$ So, we get $$Db_{2n-1}\equiv -b_{2n+3}-Db_{2n+1}\equiv D\pmod n$$