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.

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.

1. $f(g^{4n},p) \equiv g^{2n} \pmod{p}$.
2. $f(g^{4n+2},p) \equiv -g^{2n+1} \pmod{p}$.
3. $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?