# A p-adic logarithm as a limit of discrete logs

I've been searching for something similar to the argument below for about a week now and I just must be missing out on the right key words. Can someone point me in the right direction and/or let me know where I'm going wrong? I haven't worked out the details yet; spending most of my time trying to find the article where someone must've worked through all this before...

Let $$p$$ be an odd prime. Let $$g$$ be a primitive root mod $$p^n$$ for all $$n \ge 2$$. Then for any $$a \in \mathbb{Z}$$ relatively prime to $$p$$, we can define the index $$\text{ind}_{(g,n)}(a) = k_n$$ where $$g^{k_n} \equiv a \mod p^n$$. Such $$k_n$$ are only defined modulo $$\phi(p^n) = (p-1)p^{n-1}$$. But it also must be true that $$k_n \equiv k_{n-1} \mod (p-1)p^{n-2}$$. Thus for some $$0 \le c_i \le p$$ and $$0\le c_0 \le p-1$$, $$k_n \equiv c_0 + c_1(p-1)+c_2(p-1)p+c_3(p-1)p^2+\cdots+c_{n-1}(p-1)p^{n-2} \mod (p-1)p^{n-1}.$$ Hence $$\{k_n\}$$ converges $$p$$-adically to some $$k \in \mathbb{Q}_p$$. Define $$\text{ind}_g(a)=k$$. Seems reasonable to believe then that $$g^k = a$$ in $$\mathbb{Q}_p$$.

Questions:

• Initially the domain is integers relatively prime to $$p$$. It seems like these methods can be extended to $$z \in \mathbb{Q}$$ with $$|z|_p = 1$$ (for $$z=\frac{a}{b}$$, just use $$ab^{-1}$$ computed mod $$p^n$$). So perhaps it can be defined on any unit of $$\mathbb{Q}_p$$?
• How does this relate (if at all) to the $$p$$-adic logarithm that shows up in all my internet searches? It seems that $$\text{ind}_g$$ is defined on the boundary of the domain of $$\log_p$$.

For $$p\ge 3$$ if $$g$$ is a generator of $$(\Bbb{Z}/(p^2))^\times$$ then it is a generator of all $$(\Bbb{Z}/(p^k))^\times$$. For $$a\in \Bbb{Z}_p^\times$$ there is a unique $$l_{g,k}(a)\in \Bbb{Z}/(p-1)p^{k-1}\Bbb{Z}$$ such that $$a= g^{l_{g,k}(a)}\bmod p^k$$.

For $$m, $$l_{g,k}(a)= l_{g,m}(a) \bmod (p-1)p^{m-1}$$ thus $$l_{g,k}(a)= l_{g,m}(a) \bmod p^{m-1}$$ and hence $$l_g(a)=\lim_{k\to \infty}l_{g,k}(a)$$ converges in $$\Bbb{Z}_p$$ and $$a=\lim_{k\to \infty} g^{l_{g,k}(a)}$$.

Let $$c_k\in 0\ldots p^{k-1}-1,c_k = l_{g,k}(a)\bmod p^{k-1}$$. Then $$a=\lim_{k\to \infty} g^{c_k}$$ iff $$a=1\bmod p$$. In other words the full discrete logarithm of a $$p$$-adic number is an element of $$\Bbb{Z}/(p-1) \times \Bbb{Z}_p$$ and when keeping only the $$\Bbb{Z}_p$$ part we lose the $$a\bmod p$$ information.

If $$c\in 1+p\Bbb{Z}_p$$ then $$l_g(c) = \frac{\log_p(c)}{\log_p(g^{p-1})}\in \Bbb{Z}_p$$ where $$\log_p$$ is the $$p$$-adic logarithm $$\log_p(1+pb)=\sum_{n\ge 1}\frac{p^n(-1)^{n-1} b^n}{n}, b\in \Bbb{Z}_p$$

For $$a,a'\in \Bbb{Z}_p^\times$$, $$l_g(a)=l_g(a')\in \Bbb{Z}_p$$ iff $$a/a'$$ has finite order in $$\Bbb{Z}_p^\times$$ iff $$a^{p-1}=(a')^{p-1}$$.

$$\log_p(g^{p-1})\ne 1$$ when $$g$$ is an integer. $$\log_p(1+pb)=1$$ iff $$1+pb=\sum_{n\ge 0}\frac{p^n b^n}{n!}=\exp_p(1)$$ which is not in $$\Bbb{Q}\cap \Bbb{Z}_p$$.

$$\log_p$$ is the discrete logarithm in base $$\exp_p(1)$$, ie. $$\log_p(1+pb)= \lim_{k\to \infty} l_{\exp_p(1)\bmod p^k,k}(1+pb)$$.

• This is great stuff. Is there a resource (book, article, etc.) that gives more detail? Or is this just, as my advisor used to say, known by those who know things? Jan 2, 2021 at 19:28
• Also, this doesn't answer the question of if the $k_n$ as constructed work. The $k_n$ explicitly contain the $\mathbb{Z}/(p-1)$ information. So we should be able to retain $a \mod p$. Mar 20 at 17:30

For whatever it's worth, below is a paper of mine that discusses lifting the elliptic curve discrete log in $$E(\mathbb F_p$$) to $$E(\mathbb Z/p^2\mathbb Z)$$ and eventually to $$E(\mathbb Z_p)$$. It gives two methods, neither of which allows one to solve the ECDLP, but they fail for somewhat different reasons, which I always found kind of interesting. BTW, you might want to add a cryptography tag to your question, since clearly it's very relevant there.

Again talking about elliptic curves, in the case the $$\#E(\mathbb F_p)=p$$, then in fact this sort of lifting procedure does work, because you can (more-or-less) multiply the point by $$p$$ to get into the formal group while maintaining the order coming from the mod $$p$$ point. That's the only situation that I know of where such a lifting works. I mention it because in some sense it shows what goes wrong in the classical $$\mathbb F_p$$ case, namely the order of the group $$\mathbb F_p^*$$ is $$p-1$$, which is not a multiple of $$p$$.

Lifting and Elliptic Curve Discrete Logarithms, Conference: Selected Areas in Cryptography, 15th International Workshop, SAC 2008, Sackville, New Brunswick, Canada, August 14-15,
DOI: 10.1007/978-3-642-04159-4_6