0
$\begingroup$

Consider the multiplicative group $\mathbb{Z} / p\mathbb{Z}$. Let $g$ be a generator and suppose $g^n = x$. Can we say anything at all about the discrete logarithm of $x+1$? That is, can we write $m$ in terms of $n,g,x$ where $m$ is the solution to $g^m = x+1$ over the group?

Here was one thing I tried. You can expand $\log_g(x+1)$ formally as a power series and remove the residues. You're left with a $p^2$ periodic series that is Cesaro summable (similar to how $1+x+x^2+x^3...$ is Cesaro summable to the inverse of $1-x$ modulo p). However, I can't find a nice expression for the Cesaro sum.

Improve this question
$\endgroup$
3
  • 7
    $\begingroup$ This is not possible. For instance, think about the case $x=1$ and $n=0$; then the question is about the discrete logarithm of $2$. We don't even have a clean criterion for when $2$ is a generator, i.e. when $m \in \mathbf Z/(p-1)\mathbf Z$ is invertible. (A special case of Artin's conjecture says that this happens for infinitely many primes $p$, but as far as I know this remains open.) $\endgroup$
    – R. van Dobben de Bruyn
    Commented Sep 3, 2023 at 0:35
  • 5
    $\begingroup$ If we could say something about the discrete log of $x+1$ given that of $x$ then we could probably also say something about the discrete log of $xy+y$ given those of $x$ and $y$, i.e., of $z+y$ given those of $z$ and $y$. I don't think it would be much of an overstatement to say that vast amounts of crypto (Diffie-Hellman, ElGamal, DSA…) would collapse or, at least, be substantially weakened depending on what that “something” is: so the hope is very much that “no, we can't say anything”, and the discrete log is the reference “postulated hard” problem on which many crypto systems are gauged. $\endgroup$
    – Gro-Tsen
    Commented Sep 3, 2023 at 7:51
  • $\begingroup$ The answer is negative. I think either of those comments' authors can convert their comments to an answer. Maybe they will. Also, since you don't have anything but the discrete topology what does cesaro summation even mean in this case? $\endgroup$
    – kodlu
    Commented Sep 8, 2023 at 15:30

0

Reset to default

You must log in to answer this question.