2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Aeryk
    Jan 2 at 19:28
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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