Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Max Alekseyev
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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_n(n)\cdot g$$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}$.

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

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

Source Link
Max Alekseyev
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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