3
$\begingroup$

Probably this is easy, but we would like to see it on paper.

Let $p$ be prime and $D,g,n$ positive integers.

Let $A=g^n \bmod p^D$.

Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$. In pari/gp notation: $\log(p,a,D)=$log(a+O(p^D)). $\log(p,a,D)$ is efficiently computable.

Define $dlog(p,g,A,D)=\frac{\log(p,A,D)}{\log(p,g,D)}$.

Is is true that $dlog(p,g,A,D) \bmod{p^{D-1}} = n \bmod{p^{D-1}}$?

We tested hundreds of large tuples for experimental support.

This might have some cryptography application for discrete logarithms modulo prime powers.

We are interested in the discrete logarithm of $A$ in base $g$.

For this reason we generated hundreds of tuples $p,g,D,n$ and the code below correctly computed $n \mod{p^{D-1}}$.

Comments suggest constraints on $g$ but the implementation works for arbitrary $g$.

Adding pari/gp code due to comments

You can run in it in a browser: https://pari.math.u-bordeaux.fr/gp.html

    /* discrete logarith modulo p^(D-1) 
    https://pari.math.u-bordeaux.fr/gp.html
    */
{
dlog1(p,g,a,D=2)=lift(log(lift(a)+O(p^D))/log(lift(g)+O(p^D)));
}

{
tt()=
D=2;
setrand(1);
p=nextprime(10^8);X0=random(p^D);g=Mod(2,p^D);a=g^X0;
X1=dlog1(p,g,a,D);
print([(X1-X0)%p^(D-1)]);
}
tt()
Improve this question
$\endgroup$
6
  • $\begingroup$ A lot of misunderstandings in your question. $g$ must be $\equiv 1\bmod p$. $\log(g+O(p^D)) = \log(g)+O(P^D)$, $\log(g^n)=n\log(g)$ and for $D>r=v_p(\log g)$, $\frac{\log(g^n+O(p^D))}{\log( g+O(p^D))}=n+O(p^{D-r})$ where $r=v_p(g-1)$ if $p$ is odd, $r=\max(2,v_p(g-1))$ if $p=2$. It is not the most efficient algorithm to find $n$. The discrete logarithm in $(1+p\Bbb{Z})/(1+p^D\Bbb{Z})$ is a bit trivial. $\endgroup$
    – reuns
    Apr 26, 2021 at 15:59
  • $\begingroup$ @reuns You are misunderstanding. There are no constraints on $g$ and we checked hundreds of random g's. Added pari/gp code, which you can run online. Please check the code before claiming further constraints. $\endgroup$
    – joro
    Apr 26, 2021 at 16:51
  • 3
    $\begingroup$ No, the $p$-adic logarithm is defined only for $g\equiv 1\bmod p$, even if you can set $\log(g) = \frac1{p-1}\log(g^{p-1})$ for other $g\ne 0\bmod p$, which is the same as assuming $g\equiv 1\bmod p$. $\endgroup$
    – reuns
    Apr 26, 2021 at 16:58
  • $\begingroup$ @reuns I am asking about finding n mod p^(D-1), no matter about the p-adic algorithm. Is your answer solution to this too? $\endgroup$
    – joro
    Apr 26, 2021 at 17:43
  • $\begingroup$ You get $n \bmod p^{D-r}$ not $n\bmod p^{D-1}$. Taking $g=1+p$ for $p$ odd then $r=1$. $\endgroup$
    – reuns
    Apr 26, 2021 at 17:52

1 Answer 1

Reset to default
1
$\begingroup$

We asked on the pari-dev mailing list and developer Bill Allombert replied

Your function is not defined for all (p,g,A,D). Otherwise this follows from the definition of the Iwasawa logarithm.

Since pari can compute the tests, the function dlog is defined for the cases of interest.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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