It's given a prime $p$ with $p\equiv3\pmod4$.
What shortcut (if any) is there to compute $x=2^{(p+1)/4}\bmod p$, compared to a general algorithm to compute $x=2^k\bmod p$ applied for $k=(p+1)/4$ ?
I'm aware that
- $x^2\equiv-2\pmod p$ if $p\equiv3\pmod8$, and $x^2\equiv2\pmod p$ if $p\equiv7\pmod8$, but I see no way to use that;
- we can compute $2^k\bmod p$ nearly twice faster than $m^k\bmod p$ for a random $m\in[0,p)$, for the range of $p$ I'm interested in (some thousands bits).
The application would be in computing a Rabin signature using the Chinese Remainder Theorem.