0

I want to compute a solution of the congruence $$ a^2+b^2\equiv -1\pmod{p}. $$ I know that a solution always exists (this is a simple argument using the pidgeonhole principle). I also know that if $p\equiv 1\pmod{4}$, $-1$ is a quadratic residue mod $p$ and the problem can be solved by calculating a square root $a$ of $-1$ and letting $b=0$.

However, for general $p$, I know of no better method than simply trial and error (which is actually not so bad either since of course the chance to "stumble upon" quadratic residues is about a half). Does anyone know or can anyone think of a more efficient method?

I asked this question already about an hour ago and it was closed as a duplicate, but all the answers in the linked questions only proved the solvability of the congruence or determined the number of solution pairs, which is not what I was looking for. So let me be clear about this: What I am interested in is an algorithm to compute a solution pair $(a,b)$ which is better than just randomly trying values for $a$ and checking if $-1-a^2$ is a square mod $p$.

(I don't need to find all solutions - any particular one will do.)

mxian
  • 2,019
  • 2
    The answer here says "to find all solutions". – Dietrich Burde Sep 03 '21 at 16:59
  • @Dietrich Burde The answer explains how to find all solutions given we somehow have already "magically" found one solution as a starting point. I want to know how to algorithmically find that first solution - I don't even need all solutions, just any solution will do. The answer in the link does not explain how to do that. – mxian Sep 03 '21 at 18:14
  • But this post, for $a=b=-1$ there, gives you an algorithm how to compute one single solution, doesn't it? It should be the duplicate you are looking for. – Dietrich Burde Sep 03 '21 at 18:16
  • Well, but that is essentially also "just" a trial and error method: (In the notation of that post,) Pick some $x,y$ and hope that $ax^2+by^2$ is a square. This should not be much worse than (in my post's notation) picking some $a$ and hoping that $-1-a^2$ is a square as I suggested above. I understand that these methods will on average terminate quickly since half of the residues are squares, but they are still "just" guessing and checking - I want to know if there is a better method than that. – mxian Sep 03 '21 at 18:27
  • Well, then that is essentially it. I think it works quite well in practice. I do not know if there is a "general formula" at all you are expecting. – Dietrich Burde Sep 03 '21 at 18:42
  • There seems to be some interesting pointers in the comment section of this post https://math.stackexchange.com/q/446998/399263. – zwim Sep 03 '21 at 18:45

0 Answers0