5
$\begingroup$

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
$\endgroup$
8
  • $\begingroup$ How do you measure probability in 4? Over $n$ or $p$, or both? $\endgroup$ Apr 18, 2021 at 14:48
  • $\begingroup$ @MaxAlekseyev I don't have rigorous statistics. I fix $g=2$ and p random prime. Then I compute D(i) for i in the range of first few hundreds. It works for random $i$ too. $\endgroup$
    – joro
    Apr 18, 2021 at 15:11
  • $\begingroup$ @MaxAlekseyev For p=10^100+267 and 1000 random pairs D(n),D(n+1) the probability is about 1/2. $\endgroup$
    – joro
    Apr 18, 2021 at 16:20
  • $\begingroup$ @MaxAlekseyev for g=2 I have stronger conjecture, check: mathoverflow.net/questions/390761/… $\endgroup$
    – joro
    Apr 21, 2021 at 10:54
  • 2
    $\begingroup$ @DavidESpeyer By mod p I don't mean congruence, but the reduction modulo $p$ operator. $A \bmod p$ is integer in the range [0,p-1], which breaks your example. $\endgroup$
    – joro
    Apr 23, 2021 at 4:24

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks. I think this deserves paper or a note. You didn't show infinitely many non-Wieferich primes in base 2, right? $\endgroup$
    – joro
    May 9, 2021 at 17:49
  • $\begingroup$ I'm not sure how this can be useful and what's the goal of all these considerations. I do not see any implications about the infinitude of non-Wieferich primes. The case of $p$ being a Wieferich prime base $g$ is special in sense that it implies $a(n)=1$ for all $n$. $\endgroup$ May 9, 2021 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.