Skip to main content
3 of 3
added experimental support
joro
  • 25.4k
  • 10
  • 66
  • 121

p-adic logarithms with fixed precision

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()
joro
  • 25.4k
  • 10
  • 66
  • 121