A p-adic logarithm as a limit of discrete logs

Question

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

Thanks in advance!

Answer 1

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<k$, $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)$.

Answer 2

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