We represent $p - 1$ in the form of $2^K \cdot Q$ where $Q$ is odd. After that we select any residue class $A$ for the primality test.
If $z \equiv A^Q \not\equiv \pm 1$ under modulo $p$, we need to square the $z$ at most $K - 1$ times until we obtain the residue class $-1$. If this step fails then either Fermat's Little Theorem not holds or $1$ have a non-trivial square root. In each case $p$ is composite.
So, here is my idea to improve this test: Before starting to square the $z$, we should check if $-1$ is a quadratic residue modulo $p$, since otherwise we can't obtain it as a square. Hence we should check if $p$ is of residue class $1$ modulo $4$.
Can we make the test more efficient this way?