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 all positive integers $n$, the correct square root modulo $p$ of $g^{2n}$ is $g^n$.

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?

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.

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?

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?

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 all positive integers $n$, the correct square root modulo $p$ of $g^{2n}$ is $g^n$.

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?