8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @Kyle Jones, any chance you might be willing to restore (undelete) your answer? I think it has a nice insight -- I didn't quite appreciate it on first glance, but on further inspection I think it's a nice example. $\endgroup$ – D.W. Dec 11 '15 at 6:20
  • $\begingroup$ @D.W. OK. I didn't think it had much value given your more comprehensive answer, but I'll bring it back if you think it is worthwhile. $\endgroup$ – Kyle Jones Dec 11 '15 at 6:23
  • $\begingroup$ I had a new idea after reviewing Miller-Rabin. What do you think about my newly proposed algorithm? @KyleJones $\endgroup$ – Charlie Parker Dec 14 '15 at 1:50
  • $\begingroup$ @CharlieParker If you have a new question, you should ask it in a separate post. If you edit this question so that it invalidates existing answers, it defeats the purpose of having repository of questions and answers. $\endgroup$ – Kyle Jones Dec 14 '15 at 2:10
  • $\begingroup$ @KyleJones its hard to decide because its really about the same topic. What do you suggest? I can open a new question, I just wasn't sure if it was appropriate. $\endgroup$ – Charlie Parker Dec 14 '15 at 2:53
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I had a new idea after reviewing Miller-Rabin. What do you think about my newly proposed algorithm? $\endgroup$ – Charlie Parker Dec 14 '15 at 1:50
  • 1
    $\begingroup$ @CharlieParker, rather than editing the question in a way that invalidates existing answers, we'd usually prefer that you ask a new question. I suggest you do that. (Hint: think about how you plan to compute sqrt...) $\endgroup$ – D.W. Dec 14 '15 at 1:52
3
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ I wonder if there's an error somewhere in your calculations, or if I misunderstand the proposed algorithm. $a=10$ doesn't pass the QR test: $a^{(N-1)/2} = 10^7 \equiv 10 \pmod{15}$, not $1$. Therefore, according to my understanding of the proposed algorithm, $a=10$ wouldn't be accepted as a QR and the algorithm wouldn't try to do any further calculations with it. I'm assuming that the way the algorithm finds an acceptable QR is to pick $a$ randomly and test whether $a^{(N-1)/2}\equiv 1 \pmod{N}$; that seems to be what the text is suggesting. $\endgroup$ – D.W. Dec 11 '15 at 6:16
  • $\begingroup$ @D.W. OK. Your answer is altogether better anyway. $\endgroup$ – Kyle Jones Dec 11 '15 at 6:17
  • 1
    $\begingroup$ Ahh, looking a little closer, I see what's going on: 10 is indeed a QR, but the check $a^{(N-1)/2}=1 \pmod N$ mistakenly thinks it is not a QR. So, if the way the algorithm worked as to pick a random number $r$, square it, and call $a$ the result (i.e., $a =r^2 \bmod N$), then your answer would be a valid counterexample -- and that's not an unreasonable interpretation of the proposed algorithm. Cool, nice answer! $\endgroup$ – D.W. Dec 11 '15 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.