0
$\begingroup$

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

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$

  • 1
    Bit of notation. Do you mean $x^2 \equiv q \pmod{p}$2012-07-15
  • 0
    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.2012-07-15
  • 0
    @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 `%`2012-07-15
  • 0
    There are reasonably efficient algorithms to compute square roots mod $\rm\,p,\:$ e.g. the [Tonelli-Shanks](http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) and [Cipolla](http://en.wikipedia.org/wiki/Cipolla's_algorithm) algorithms.2012-07-15
  • 1
    There are algorithms for finding square roots when the modulus is prime. E.g.,, the [Tonelli-Shanks algorithm](http://en.wikipedia.org/wiki/Shanks_algorithm). Finding square roots with composite moduli is computationally equivalent to factoring.2012-07-15

2 Answers 2

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

  • 0
    hmm this doesn't seem to synthesize the answer I currently have but the equation works for one of the solutions2012-07-15
  • 0
    @AgainstASicilian If it works for one of the solutions, the other solution has to be its negative.2012-07-15
  • 0
    I try both the positive and negative and they give me the same solution for some reason2012-07-15
  • 0
    @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).2012-07-15
  • 0
    p = 4000000007, q = 1749870067. For x I get 2912856368. Trying to get the other answer 10871436392012-07-15
  • 0
    @AgainstASicilian Have you not looked at $-x$?? Hint: what is $2912856368 + 1087143639$?2012-07-15
  • 0
    I did. It gave me the same output2012-07-15
  • 0
    @AgainstASicilian: If $x$ is a solution modulo $p$, then $p-x$ is "the" other solution.2012-07-15
  • 0
    @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.2012-07-15
  • 0
    oh, interesting... not sure why/how any of this works but that is clever!2012-07-15
  • 0
    @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.2012-07-15
  • 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.2012-07-15
  • 1
    @AgainstASicilian The minus sign is outside of the exponent!2012-07-15
  • 1
    @AgainstASicilian $(-1)^{100}$ is not the same as $-1^{100}$.2012-07-15
  • 0
    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 ?2012-07-15
  • 0
    @AgainstASicilian They are the same $\mod p$.2012-07-15
  • 1
    @AgainstASicilian: Because $-2912856368\bmod p = 1087143639$.2012-07-15
  • 0
    I see... thanks for the explanation!2012-07-15
  • 0
    @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`).2012-07-15
  • 0
    @ArturoMagidin Thanks, I didn't know about that.2012-07-15
0

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.