I was reading CLRS and it mentions that if $p$ is a prime of the form $4k+3$ and $a$ is a quadratic residue, then $a^{k+1}$ is a square root of $a$. One can also easily show that $a^{-k}$ is a square root of $a$ as well.
Can we use this to get a primality test, for numbers $N$ of the form $N=4k+3$?
After reviewing Miller-Rabin (and after asking the related question Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function? ) and thinking about it a little more I thought of an algorithm that seems promising. The intuition is that if $N=pq$ (or some other composite) there will be more than 2 square roots. Therefore, if we can find more than 2 square roots, we have evidence that $N$ is a composite. With that idea, here is the algorithm:
PrimalityTest$(N)$: (where $N = 4k + 3$)
- Choose $x \in \mathbb{Z}_N$ and compute $a = x^2 \pmod N$.
- Compute $y = a^{(N+1)/4} \pmod N$. (Notice that if $N$ is prime, this is just computing a square root of $a$.)
- If $y^2 \equiv a \pmod N$ but $y \not \equiv \pm x \pmod N$ then there are more than 2 distinct square roots of $a$. Therefore, return "composite".
- If $y^2 \not \equiv a \pmod N$ then return "composite". (If $N$ were prime, then step 2 would have computed a valid square root of $a$, so by the contrapositive, if $y$ is not a valid square root, then $N$ is not prime.)
- If $y^2 \equiv a \pmod N$ and $y \equiv \pm x \pmod N$ we have no idea what $N$ is. Therefore, go back to step 1 and choose a different $x$. If this step happens too often, simply return "prime".
I believe this will succeed with probability 1/2, since it has half chance of choosing a "bad" square root that gives us no information. The only step I am not sure how to analyze probabilistically is step 4, but it seems that step 2 might do nonsense when $N$ is composite, it seems the probability that 4 catches is is quite high. I'd guess around $\frac{N-2}{N}$.