Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

Question

I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square root).

I was wondering if using the previous fact and also that we knew we had a number of the form $N = 4k+3$ (not necessarily prime), then maybe there is a different primality testing for (any?) $N$ using the square root function (i.e. $SQRT_N(a) = a^{k+1} $).

So the algorithm that I thought was the following:

Choose a Quadratic Residue (QR) $a \in \mathbb{Z}^*_N$ (one can easily do this by checking if $a^{\frac{p-1}{2}} \equiv 1 \pmod p$ holds). Once we have a QR, compute $a^{k+1} = x_a$ and check if $x_a^2 $ is equal to $a$. If its true, then we conclude that $a$ is prime. Otherwise, we choose a different QR $a' \in \mathbb{Z}^*_N$ and repeat the algorithm. One can repeat this algorithm $k$ times. If after $k$ times there is no success then conclude the number is composite.

I have mainly intuitions on why its correct but not a formal proof. From the first fact that $x_a = a^{k+1}$ is a square root when $p$ is prime, it must mean that $x_a^2 \equiv a \pmod p$. Therefore, if $a$ is a QR then that check will pass (half the time we will choose a QR so the probably that we choose a non QR is only 1/2).

However, if $N$ is composite, it seems we have no guarantee that $x_a^2 \equiv a \pmod N$. So if it doesn't hold we are sure its not prime. But if it does hold then if its prime we are right but if its composite we might be wrong? Basically, is it possible to use the SQRT function when $N = 4k+3$ to decide if $N$ is prime or not?

---

I also thought of an another algorithm that deserved its own question: Is computing a square root of a number and having more than 2 roots a reliable way to decide primality?

Answer 1

Let me start with a counterexample where your algorithm gives the wrong answer: i.e., where $N$ is composite but your algorithm concludes it is prime. Suppose $N=91$ and $a=9$. Then $a^{(N-1)/2} = 9^{45} \equiv 1 \pmod{91}$, so $a$ passes your check to be a QR. Also, $a^{(N+1)/4} = 9^{23} \equiv 81 \pmod{91}$ and $81^2 \equiv 9 \pmod{91}$, so this passes your second test, your algorithm will conclude that 91 is prime. However, 91 is not prime: $91=7 \times 13$. Thus your algorithm has drawn the wrong conclusion in this case. This demonstrates that your algorithm can output incorrect answers in at least some cases.

---

Actually, there is a more serious problem with your algorithm. There is no number $N$ where your algorithm will ever output "composite". It thinks that all numbers are primes. More precisely, for every $N$, your algorithm will either loop forever (trying to find a number that passes the QR test, in vain), or will terminate and output "prime". So, your algorithm is about as wrong as could be.

You can see this by applying some number theory. You have a test whether $a$ is a QR and a second test based on the square root insight. If $a$ passes the first test, it will pass the second one.

Here's why. Your QR test succeeds if $a^{(N-1)/2} \equiv 1 \pmod N$. Your second test succeeds if $(a^{(N+1)/4})^2 \equiv a \pmod N$. The latter is equivalent to $a^{(N+1)/2} \equiv a \pmod N$. But $a^{(N+1)/2} \equiv a \times a^{(N-1)/2} \pmod N$. Therefore, if $a^{(N-1)/2} \equiv 1 \pmod N$, then (multiplying both sides by $a$) we immediately see that we must have $a^{(N+1)/2} \equiv a \pmod N$.

Each of the $k$ passes of your algorithm basically amounts to looking for an $a$ that passes the first test, and then checking whether it passes the second test -- but based on the prior insight, we see that any $a$ that passes the first test will be guaranteed to pass the second test as well. Thus, if the algorithm ever finds any value $a$ that passes the QR test, the second test will automatically pass and the algorithm will output "prime".

The lesson to learn: any time you think you have an algorithm that looks promising, it's worthwhile to code it up and try it on some test cases and see if it seems to work well. Trying it on a few test cases is not a substitute for a proof of correctness, but it can be a helpful way to weed out some incorrect algorithm quickly.

---

Finally, on to your real question: can we use something like this to build a primality test? Well, you can think of the Miller-Rabin primality test as loosely based on something like this. They are based on a characterization of what the square roots of $1$ should look like, if $N$ is prime. If you encounter a square root of $1$ that is not $1$ or $-1$, you can conclude that $N$ is not prime. However, it's not limited to numbers $N$ of the form $N=4k+3$, so in that sense it is definitely different.

Answer 2

The congruence is true for all primes $p$ of the correct form but it is also true for some composite numbers, which makes the congruence alone useless as a primality test.

Example: set $p$ to the number $15$, which is obviously composite and is of the form $4k + 3$ with $k = 3$. $10000$ is $100^2$, so $10000$ mod $15$ produces the quadratic residue $a$ = $10$. $10^{k+1}$ = $10^{4}$ = $10000$; applying mod $p$ to that yields $10$. Now the test: Under mod $p$ $10$ is supposed to be the square root of $a$ ($10$) only if $p$ is prime, but $10^2$ = $100$ which is $10$ mod $p$, so $p$ has passed the primailty test. Yet we know $p$ is composite.

This is demonstrating that even if your method for picking QR's is perfect, the algorithm still can err. For instance, here would be a reasonable way to pick $a$: pick a random number $r$, square it, and call $a$ the result (i.e., $a =r^2 \bmod N$). Then you know that $a$ is guaranteed to be a QR, and there's no need to test it using the test you listed. If that was how your algorithm picked $a$, then the example above shows that your algorithm can give the wrong answer in some cases (e.g., $p=15$, $r=5$).