Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
1  
Bit of notation. Do you mean $x^2 \equiv q \pmod{p}$ –  user2468 Jul 15 '12 at 20:02
    
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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
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
1  
@AgainstASicilian: Because $-2912856368\bmod p = 1087143639$. –  Arturo Magidin Jul 15 '12 at 20:38

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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