Discrete logarithm and the sequence $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$

Question

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)$:

1. $a(n)$ is periodic with period divisor of $p-1$.
2. The multiplicative order of $a(n)$ modulo $p^2$ is $p$.
3. 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.
4. 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

Answer 1

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}$.