Discrete logarithm and the sequence $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$ Let $p$ be prime and $g,n$ integers.
Define $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$
By mod p we don't mean congruence, but the reduction modulo $p$ operator. $A \bmod p$ is integer in the range $[0,p-1]$.
Some properties of $a(n)$:

*

*$a(n)$ is periodic with period divisor of $p-1$.

*The multiplicative order of $a(n)$ modulo $p^2$ is $p$.

*Let $D(n)$ be the discrete logarithm of $a(n)$, i.e.
given $p$, $g$, $a(n)$ we have $g^{D(n)} \mod p^2=a(n)$.
We can efficiently compute $D(n)=k(p-1)$ via p-adic logarithms.

*Let $g=2$. Experimentally with high probability
we have $D(n) \bmod p=D(n+1)+1 \bmod p$.
For other properties of the sequence with $g=2$ check
this question

Q1 Are there other functional relations between $g$, $n$, $a(n)$, $D(n)$?
We believe that finding $n$ given $p,g,a(n)$ will solve the discrete
logarithm modulo $p$, which is a major result.


Q2 For $g=2$, when do we have $D(n) \bmod p=D(n+1)+1 \bmod p$?


Q3 What is the intuition for efficiently computing $D(n)$
for period divisor of $p-1$?

sagemath code follows, one can run it in a browser:
def seqanp2(p,g,n):
    """
    a(n)=(g^n mod p)^(p-1) mod p^2
    """
    try:  g=lift(g)
    except:  pass
    r1=lift((Integers(p)(g))**n)
    K2=Integers(p**2)
    res=K2(r1)**((p-1))
    return res

def solveseqan(p,g,a):
    """
    g^res =a(n)  mod p^2
    """
    try:  g=lift(g)
    except:  pass
    try:  a=lift(a)
    except:  pass
    K=Qp(p,2)
    t=lift(K(a).log()/K(g).log() )
    res=(p-1)*(p-t%p)
    return res

set_random_seed(1)

p=next_prime(10**20);
K2=Integers(p**2);
g=K2(2) 
n0=randint(2,p-2)
r1=seqanp2(p,g,n0);r2=seqanp2(p,g,n0+1);
s1=solveseqan(p,g,r1);s2=solveseqan(p,g,r2)

print(g**s1==r1,g**s2==r2,seqanp2(p,g,n0)==seqanp2(p,g,n0+p-1)) #True True True

 A: Q1 is too vague, so let me answer Q2 and Q3.
Assume that a prime $p$ and a primitive root $g$ modulo $p$ are fixed.
Let $g_0(n) := g^n\bmod p$, $g_1(n) := \frac{g^n - g_0(n)}{p}\bmod p$, and $c := g_1(p-1)$. Assuming that $p$ is not Wieferich prime base $g$, we have $c\ne 0$.
From these definitions we have
$$g^n \equiv g_0(n) + g_1(n)p \pmod{p^2}$$
and
$$g^{p-1} \equiv 1 + cp \pmod{p^2}.$$
It follows that
$$1 + k(n) cp \equiv g^{D(n)}\equiv a(n) \equiv g_0^{p-1} \equiv 1 + (cn + \frac{g_1(n)}{g_0(n)})p\pmod{p^2}$$
and thus
$$k(n) = n + \frac{g_1(n)}{cg_0(n)}\bmod p,$$
which gives us an efficient way to compute $D(n) = k(n)\cdot (p-1)$.
Now, since $g_0(n+1) \equiv g_0(n)\cdot g\pmod{p}$, we have $k(n+1) \equiv k(n)+1\pmod{p}$ and correspondingly $D(n+1) \equiv D(n) - 1\pmod{p}$ if and only if $g_1(n+1) \equiv g_1(n)\cdot g\pmod{p}$, which happens when $g_0(n+1)=g_0(n)\cdot g$ and there is no carry from multiplying $g_0(n)$ by $g$. That is, we need $g_0(n) \leq \frac{p-1}{g}$, which under the assumption that $g_0(n)$ is distributed uniformly in $[1,p-1]$ has the probability $\frac{1}{g}$. So, for $g=2$, there is 50% chance that $D(n+1) \equiv D(n) - 1\pmod{p}$.
