Let $p$ be prime congruent to $3$ modulo $4$.
The discrete logarithm problem asks: given $g,a,p$ such that $g^x \equiv a \pmod{p}$, find $x$.
Assume $g$ is of maximal multiplicative order.
In an attack on it, one may try to compute the square root of $g^{2n}$, but the problem is there are two square roots $g^n,-g^n$ and we don't know which one to choose.
For integer $n, 1 < n < (p-3)/4$, the correct square root modulo $p$ of $g^{2n}$ is $g^n$.
EDIT Earlier revision asked about all $n$, but comments disproved it.
Define $f(a,p)=a^{\frac{p+1}{4}}$.
It is folklore that if $a$ is square $f(a,p)^2 \equiv a \pmod{p}$, so $f$ computes one square root of $a$ and this might give additional structure in choosing the root in the discrete logarithm.
We believe we the following hold.
- $f(g^{4n},p) \equiv g^{2n} \pmod{p}$.
- $f(g^{4n+2},p) \equiv -g^{2n+1} \pmod{p}$.
- $f(g^{2n},p) \equiv (-g)^{n} \pmod{p}$.
In $g^n$ we can distinguish $n \mod 2$, but can't find $n \mod 4$ to use (1) and (2).
On the other hand we have determinism of computing the square root of $g^{4n}$ and we choose the correct root from $g^{2n},-g^{2n}$.
We get experimental support for the claims and try Pollard rho algorithm, but couldn't improve it.
Q1 What is the intuition for computing the correct square root of $g^{4n}$
Q2 Can we use the above for an attack of the discrete logarithm?
