if $x^2 \bmod p = q$ and I know $p$ and $q$, how to get $x$?

Question

I'm aware this has to do with quadratic residues but I do not know how to actually solve it. $p$ is a prime of form $4k+3$

Please make the body of the question self-contained. The title is an indexing feature, much like writing the title of a book on the spine to make finding the book on the bookshelf easier. But you don't expect the book to start at the spine. — Arturo Magidin, Jul 15 '12 at 20:03
@J.D. $a\bmod b$ usually means the nonnegative remainder of $a$ when divided by $b$. It is the mathematical notation for the operation that many computer languages denote by % — Arturo Magidin, Jul 15 '12 at 20:04
There are reasonably efficient algorithms to compute square roots mod $\rm,p,:$ e.g. the Tonelli-Shanks and Cipolla algorithms. — Bill Dubuque, Jul 15 '12 at 20:04
There are algorithms for finding square roots when the modulus is prime. E.g.,, the Tonelli-Shanks algorithm. Finding square roots with composite moduli is computationally equivalent to factoring. — Arturo Magidin, Jul 15 '12 at 20:08

Cocopuffs · Accepted Answer · 2012-07-15T21:30:32.743

4

Euler's theorem says that $\left(\frac{q}{p}\right) \equiv q^{\frac{p-1}{2}} \bmod p$. On the other hand, assuming there is a solution, $\left(\frac{q}{p}\right) = 1$.

So you have $q^{\frac{p+1}{2}} \equiv q*q^{\frac{p-1}{2}} \equiv q \bmod p$. Since $p+1$ is divisible by $4$, this gives solutions $$x \equiv \pm q^{\frac{p+1}{4}} \bmod p.$$

edited Jul 15 '12 at 21:30

answered Jul 15 '12 at 20:08

Cocopuffs

10,307

hmm this doesn't seem to synthesize the answer I currently have but the equation works for one of the solutions – MyNameIsKhan Jul 15 '12 at 20:24
@AgainstASicilian If it works for one of the solutions, the other solution has to be its negative. – Cocopuffs Jul 15 '12 at 20:29
I try both the positive and negative and they give me the same solution for some reason – MyNameIsKhan Jul 15 '12 at 20:29
@AgainstASicilian What is the answer you currently have? You should mention this in your question. Cocopuff's solution is valid for all cases, in fact it is equivalent to Tonelli-Shanks ($p=4k+3$ is the easiest case). – Erick Wong Jul 15 '12 at 20:30
p = 4000000007, q = 1749870067. For x I get 2912856368. Trying to get the other answer 1087143639 – MyNameIsKhan Jul 15 '12 at 20:30
@AgainstASicilian Have you not looked at $-x$?? Hint: what is $2912856368 + 1087143639$? – Erick Wong Jul 15 '12 at 20:31
I did. It gave me the same output – MyNameIsKhan Jul 15 '12 at 20:31
@AgainstASicilian: If $x$ is a solution modulo $p$, then $p-x$ is "the" other solution. – Arturo Magidin Jul 15 '12 at 20:32
@AgainstASicilian: "Output"? You mean you got the same square? Of course! Squaring both $x$ and $p-x$ will give you $q$ modulo $p$. But $x\neq p-x$, because $p$ is odd. – Arturo Magidin Jul 15 '12 at 20:33
oh, interesting... not sure why/how any of this works but that is clever! – MyNameIsKhan Jul 15 '12 at 20:33
@ArturoMagidin No, as in I calculate x with pow(q,(p+1)/4,p). But if I try pow(-q,(p+1)/4,p), I get the same output for x. – MyNameIsKhan Jul 15 '12 at 20:33
1

@AgainstASicilian: No, no, no! That's not what people are telling you. You don't change the sign of $q$. once you know one value of $x$ that gives a solution, then $p-x$ is the other solution. There's no cleverness about it: it's exactly the same observation as noting that if $a$ is a solution to $x^2=b$ in the real numbers, then $-a$ is the other solution. – Arturo Magidin Jul 15 '12 at 20:34
1

@AgainstASicilian The minus sign is outside of the exponent! – Cocopuffs Jul 15 '12 at 20:35
1

@AgainstASicilian $(-1)^{100}$ is not the same as $-1^{100}$. – Erick Wong Jul 15 '12 at 20:35
I guess I do not understand how x = 2912856368 is an answer but so is x = -2912856368, when in fact the real answer is x = 1087143639 ? – MyNameIsKhan Jul 15 '12 at 20:37
@AgainstASicilian They are the same $\mod p$. – Cocopuffs Jul 15 '12 at 20:38
1

@AgainstASicilian: Because $-2912856368\bmod p = 1087143639$. – Arturo Magidin Jul 15 '12 at 20:38
I see... thanks for the explanation! – MyNameIsKhan Jul 15 '12 at 20:40
@Cocopuffs: Use \bmod for the "binary mod". It omits the annoying extra white space before mod.. Compare $\mod p$ (\mod p) with $\bmod p$ (\bmod p). – Arturo Magidin Jul 15 '12 at 20:47
@ArturoMagidin Thanks, I didn't know about that. – Cocopuffs Jul 15 '12 at 21:30

score 0 · Answer 2 · answered Jul 15 '12 at 20:28

A finite field of order $\rm\:4n\!+\!3\:$ has subgroup of squares of order $\rm\:2n\!+\!1.\:$ But one easily shows that in any group of odd order $\rm\; 2n\!+\!1\:$ the equation $\rm\; x^2 = a\;$ has solution $\rm\: a^{n+1}\;$ (Lagrange, 1769).

More generally, there are reasonably efficient algorithms to compute square roots mod $\rm\,p,\:$ e.g. the Tonelli-Shanks and Cipolla algorithms.

if $x^2 \bmod p = q$ and I know $p$ and $q$, how to get $x$?

2 Answers2

Linked