3
$\begingroup$

Let $a$ and $p$ be integers such that $p$ is prime, and $a$ is a square modulo $p$. When $p\equiv3\pmod4$, show that $a^{(p+1)/4}\pmod p$ is a square root of $a$. Why does this technique not work when $p\equiv1\pmod4$?

This is a question that appeared on a past exam paper for Cryptography at Undergraduate level. I think it might have something to do with the Legendre Symbol: $(\frac{-1}{p}) =\begin{cases} 1 & \mbox{ if }p \equiv 1\mod{4} \\ -1 & \mbox{ if }p \equiv 3\mod{4}. \end{cases}$

But I cannot seem to make the connection here. I have also thought about the use of Euler's criterion $a^{(p-1)/2} \equiv (\frac{a}{p}) \equiv 1 \pmod p.$ But that does not mean $a^{(p-1)/4}$ is a square root of $a$.

Could anyone hint me please on the direction I should take? Thanks in advance!

$\endgroup$
4
$\begingroup$

When you mentioned Euler's Criterion, you were nearly finished. Let $a$ be a quadratic residue of $p$. Then $$a^{(p-1)/2}\equiv 1\pmod{p}.\tag{1}$$ Multiplying by $a$ we get $$a^{(p+1)/2}\equiv a\pmod{p}.\tag{2}$$ If $p$ is of the form $4k+3$, then $\frac{p+1}{4}$ is an integer, and from (2) we obtain $$\left(a^{(p+1)/4} \right)^2\equiv a\pmod{p}.$$

Remark: The method does not work for primes of the form $4k+1$ for the simple reason that $\frac{p+1}{4}$ is then not an integer. There is a modification of the idea for primes of the form $8k+5$, which uses facts about the quadratic character of $2$.

$\endgroup$
  • $\begingroup$ ahh yes I was rather tired yesterday, I didn't quite see that. I keep thinking about $a^{(p−1)/4}$ instead of $a^{(p+1)/4}$. Thank you! $\endgroup$ – dessskris May 10 '15 at 6:07
  • $\begingroup$ You are welcome. As I mentioned, there is (almost) a formula for square roots of $a$ using exponentiation if $p$ is of the form $8k+5$. The results for $4k+3$ and $8k+5$ are of some importance, since modular exponentiation using the binary method is "cheap." Things get more complicated for square roots modulo primes of the form $8k+1$. $\endgroup$ – André Nicolas May 10 '15 at 6:12
0
$\begingroup$

If $a$ is divisible by $p$, the assertion is trivial. Otherwise, we want to know whether $a^{\frac{p+1}{4}}$ squared is congruent to $a$ modulo $p$. Just work backwards: $$a^{\frac{p+1}{2}} \equiv a \pmod p $$ if and only if (multiplying both sides by $a^{-1}$): $$a^{\frac{p-1}{2}} \equiv 1 \pmod p$$ This last assertion is true because in your hypothesis you said there is some $x$ for which $a \equiv x^2$, whence (raising both sides to the $(p-1)/2$ power) $$a^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod p$$ Since $a$ is not divisible by $p$, neither is $x$, so of course $x^{p-1} \equiv 1$. We cannot even formulate your assertion when $p$ is not $3$ modulo $4$, since otherwise $(p+1)/4$ is not even an integer. But besides being able to pose a well defined problem, I didn't use $p \equiv 3 \pmod 4$ anywhere, only that $p$ was odd.

$\endgroup$
0
$\begingroup$

Hint: if $p \equiv 3 \mod 4$, then $a^{\frac{p+1}{4}} = a^m, m \in \Bbb Z$

And if $p \equiv 1 \mod 4$ then $a^{\frac{p+1}{4}} = a^{\frac{1}{2}} a^m, m \in \Bbb Z$

$\endgroup$
  • $\begingroup$ @hardmath OK. Let me add that in. $\endgroup$ – SalmonKiller May 9 '15 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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