6
$\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$

3 Answers 3

7
$\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$
2
  • $\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
    Commented May 10, 2015 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$ Commented May 10, 2015 at 6:12
1
$\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$
1
  • $\begingroup$ @hardmath OK. Let me add that in. $\endgroup$ Commented May 9, 2015 at 3:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .