Estimating discrete logarithms via sum of group elements

The discrete logarithm problem is one of the cornerstones of modern asymmetric cryptography. Several algorithms exist and each approaches the problem in different ways. For example, the Pohlig-Hellman algorithm exploits smooth group orders, the index calculus algorithm uses a small set of known discrete logarithms in order to combine them to solve the problem in question and Pollards Rho-Algorithms makes use of the birthday paradox.

I am not aware of any approach that makes use of the fact, that the residues $r_i$ in the group $\mathcal{G} \subseteq \mathbb{F}_p$ generated by the element $g$ are often nearly equal distributed. Ok, this is not always true and there are some deep and highly non-trivial theorems about the distribution of these group elements. But for our purposes we can assume that the average size of a group element is $(p-1)/2$. That means, if we assume that $g$ is a primitive root, hence $\mathcal{G} = \mathbb{F}^*_p$, and $r_i \equiv g^i\pmod{p}$ it holds: $$ \sum^e_{i=1} r_i \approx e\cdot \frac{p-1}{2} $$ And since $e < p$ it in particular holds $$ S := \sum^e_{i=1} r_i = e\cdot \frac{p-1}{2} + \mathcal{O}(p^{1/2}) < p^2 $$ So if we can compute $S$ we get a very good approximation of $e$ since $$ \frac{2\cdot S}{p-1} = e + \mathcal{O}(1) $$

Input: $(g,r_e,p)$. In order to get $S$, we can start and use our lovely Chinese Remainder Theorem (CRT). We can get the remainder of $S$ modulo $p$ easily via the following computation:
\begin{align*}
 \sum^e_{i=1} r_i & \equiv \sum^e_{i=1} g^i \pmod{p}\\
&= \frac{g^{e+1}-g}{g-1} \equiv \frac{r_{e+1}-g}{g-1} \pmod{p}\\
&\equiv \frac{gr_e-g}{g-1} = R_1 \pmod{p}
\end{align*}
The computation of the value $R_1$ from the given input triple $(g,r_e,p)$ is already half of the work. Because another reduction by an integer of similar size as $p$ would immediately give us the entire sum $S$ using the CRT.

We assume that $S < p\cdot g$ which is not a real constraint since one could use the self-reducibility of the discrete logarithm together with the fact, that one could reduce the exponent $e$ "a little bit" by taking square roots and keeping track of all possibilities. But getting this other residue is of course as hard as the discrete logarithm problem.

So perhaps this is not the best sum to target. Fortunately, there are other sums which would also be worth to know, since they all depend heavily on the secret exponent $e$:

We write the dlp congruence as an equation $$\text{(Eq. 0)}\;\;\;g^e = r_e + p\sum^{e-1}_{j=0}k_{e,j}g^j$$, whereof the integers $k_{e,j}$ are the coefficients of the $g$-adic representation of the integer $(g^e-r_e)/p$. Next, we span an equation system:
\begin{align*}
g^1 & = r_1 + pk_{1,0} \\
g^2 & = r_2 + p(k_{2,1}g+k_{2,0}) \\
g^3 & = r_3 + p(k_{3,2}g^2+k_{3,1}g + k_{3,0}) \\
\ldots & = \ldots \\
g^{e-1} & = r_{e-1} + p(k_{e-1,e-2}g^{e-2}+\ldots+k_{e-1,0}) \\
g^e & = r_e + p(k_{e,e-1}g^{e-1}+\ldots+k_{e,0}) \\
\end{align*} Note that two coefficients $k_{i,j}$ and $k_{u,v}$ are equal if $i-j = u-v$. Knowing this, we can sum up the equations and get
\begin{align*}
\text{(Eq. 1)}\;\;\;\sum^e_{j=1} g^j = \sum^e_{j=1} r_j + p \sum^{e-1}_{j=0}k_{e,e-1-j}\sum^{e-1-j}_{i=0}g^i
\end{align*} If we reduce Eq. (1) modulo $g$, we get
\begin{align*}
\text{(Eq. 2)}\;\;\;0 & \equiv \sum^e_{j=1} r_j + p\sum^{e-1}_{j=0}k_{e,e-1-j}\pmod{g}\\
& \equiv S + p\sum^{e-1}_{j=0}k_{e,j} \pmod{g}
\end{align*} If we reduce Eq. (1) modulo $g-1$, we get
\begin{align*}
\text{(Eq. 3)}\;\;\;e & \equiv \sum^e_{j=1} r_j + p\sum^{e-1}_{j=0}(e-j)k_{e,e-1-j}\pmod{g-1}\\
& \equiv S + p\sum^{e-1}_{j=0}(j+1)k_{e,j} \pmod{g-1}
\end{align*} If we reduce Eq. (1) modulo $g+1$, we get (after some skipped computation)
\begin{align*}
\text{(Eq. 4)}\;\;\;-1 + r_{e+1} - pk_{e+1,0} \equiv 2S+ p\sum^{e-1}_{j=0}k_{e,j} \pmod{g+1}
\end{align*}
We multiply Eq. 2 by $2$ and use Eq. 4:
\begin{align*}
0 & \equiv 2S + 2p\sum^{e-1}_{j=0}k_{e,j}\pmod{g} \\
-1 + r_{e+1} - pk_{e+1,0} & \equiv 2S+ p\sum^{e-1}_{j=0}k_{e,j} \pmod{g+1} \\
\end{align*} The target is the entire sum $2S + p\sum^{e-1}_{j=0}k_{e,j}$, since it heavily depends on $e$. The left sides would be equal if $2p \equiv x\pmod{g}$ and $p \equiv x\pmod{g+1}$. Clearly, this is almost never true.

But (and this is connected with the problem to backdoor discrete logarithms in $\mathbb{F}_p$) is there at least a potential setup with $2p \equiv x\pmod{g}$ and $p \equiv x\pmod{g+1}$? And does this setup allow the combined sum $2S + p\sum^{e-1}_{j=0}k_{e,j}$ to be smaller than $g(g+1)$?

A rough estimation yields
\begin{align*}
2S + x\sum^{e-1}_{j=0}k_{e,j} & = 2e\frac{p-1}{2} + 2\mathcal{O}(p^{1/2}) + xe\frac{g-1}{2} + x\mathcal{O}(g^{1/2})\\
& \approx ep + xe\frac{g-1}{2}
\end{align*}
So, to make this work, we first test, if such a prime $p$ and an integer $g$ can be found theoretically: For the prime $p$ it must hold
\begin{align*}
2p \equiv x(g+1)I_1 + 2xgI_2 \pmod{g(g+1)}
\end{align*} whereof $I_1(g+1) \equiv 1\pmod{g}$ and $I_2g \equiv 1\pmod{g+1}$. Hence $I_1 = 1$ and $I_2 = -1$, so we have
\begin{equation}
p = \frac{x(g+1)}{2} - xg + \frac{g(g+1)}{2}K
\end{equation} We required that $$ ep + xe\frac{g-1}{2} < g(g+1) $$ If we use our computed $p$ value we get
\begin{align*}
ep + xe\frac{g-1}{2} & = e\left(\frac{x(g+1)}{2} - xg + \frac{g(g+1)}{2}K\right) + xe\frac{g-1}{2} \\
& = \frac{ex(g+1)}{2} - exg + \frac{eg(g+1)}{2}K + xe\frac{g-1}{2} \\
& = \frac{exg}{2}+\frac{ex}{2} - exg + \frac{eg(g+1)}{2}K + \frac{xeg}{2}-\frac{xe}{2} \\
& = \frac{eg(g+1)}{2}K \leq_? g(g+1)\\ 
\end{align*} Thus only for $e \leq 2$ the last inequality holds. So this particular approach does not work. But does this approach perhaps leads to some success, e.g. $e < c\cdot \log p$ regarding other or similar sums?