I know that there are primality testings that are deterministic but I wanted to know the answer of this question anyways, just for fun.
I was trying to design a randomized algorithm that decides whether $N$ is prime or $N$ is composite in the special case when $N \equiv 3 \pmod 4$, assuming that we are able to compute square roots modulo $p$ (when $p$ is prime). The second fact is easy because if the following: Notice that if $p$ is prime then one can use the Legendre symbol to justify that one can compute square roots as follow $a^{-k}$, since if $a$ is a quadratic residue the:
$$a^{{(3+4k-1)}\over 2} \equiv 1 \pmod p$$ $$a^{1+2k} \equiv 1 \pmod p$$ $$a \equiv a^{-2k} \pmod p$$ $$a \equiv {(a^{-k})}^2 \pmod p$$ $$\sqrt{a} \equiv a^{-k} \pmod p$$
Thus, the square root is $\sqrt{a} \equiv a^{-k} \pmod p $. And since the Legendre symbol returns $-1$ when $a$ is not a quadratic residue its easy to compute square roots when there are square roots and point out when there are not (in the case that $p$) is prime.
So using the above procedure that computes square roots, I wanted to decide whether $N = pq \equiv 3 \pmod 4$ was prime or not.
The idea that I had was that we could do the following:
- Choose a random number $r \in \{1,....,N-1\}$
- compute x = SQRT($r^2$,N)
then if $N$ is prime it will alway return $r$ or $-r$, but if its not prime then SQRT might return anything. In fact if we are very unlucky SQRT (prob $\frac{2}{p-1}$ I believe) might output $r$ or $-r$ when $N=pq$. So the algorithm might make a mistake, right?
Is it true that this algorithm cannot be transformed to a Las Vegas algorithm so that it always outputs a correct answer and runs in polynomial time? Or am I missing something and there is a different algorithm that is always able to output correct answers in polynomial time using SQRT?
I guess the main issue is that who knows what SQRT(a,N) returns for $N$ is not prime if its defined as I described..