Finding n mod p^(D-1) given A=g^n mod p^D

Georgi Guninski <[email protected]>
Newsgroups gmane.comp.mathematics.pari.devel
Message-ID <CAGUWgD_csG_uTk22zETWQdnauimGb8o+xemrggWbYcvEUVcX6Q@mail.gmail.com>
We asked this on mathoverlow [1], but didn't get answer.

Let p be prime and n,g,D integers. Let A=g^n mod p^D

Let dlog(p,g,A,D)=log(A+O(p^D))/log(g+O(p^D)).

Conjecture 1: dlog(p,g,A,D) mod p^(D-1) = n mod p^(D-1)

dlog is efficiently computable.

We verified it with hundreds of large tuples (p,g,D,n).

It is also related to the discrete logarithm of A in base g
modulo p^D.

Is the conjecture true?

[1]: https://mathoverflow.net/questions/391223/p-adic-logarithms-with-fixed-precision

Code:

/*
discrete logarithm modulo p^(D-1)
A=g^n mod p^D

dlog(p,g,A,D) mod p^(D-1) = n mod p^(D-1)

Author Georgi Guninski
*/

{
dlog1(p,g,a,D=2)=lift(log(lift(a)+O(p^D))/log(lift(g)+O(p^D)));
}

{
tt()=
D=3;
setrand(1);
p=nextprime(10^18);X0=random(p^D);g=Mod(2,p^D);a=g^X0;
X1=dlog1(p,g,a,D);
\\print(X1,X0);
print([(X1-X0)%p^(D-1)]);
}
tt()
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.