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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Apr 28, 2021 at 01:54:01PM +0300, Georgi Guninski wrote:
> On Tue, Apr 27, 2021 at 12:56 PM Bill Allombert
> <Bill.Allombert@math.u-bordeaux.fr> wrote:
> 
> > > Conjecture 1: dlog(p,g,A,D) mod p^(D-1) = n mod p^(D-1)
> >
> > Your function is not defined for all (p,g,A,D).
> > Otherwise this follows from the definition of the Iwasawa logarithm.
> 
> Thanks for the answer.
> 
> We believe there are few counterexamples to the congruence
> if g is p-th power and dlog is successfully computed by pari:
> 
> ? p=113;D=3;X0=(p+2);g=Mod(2,p^D)^p;A=g^X0;X1=dlog1(p,g,A,D);

dlog(p,g,A,D) mod p^(D-1) is not defined in this case since
PARI only returns dlog(p,g,A,D) mod p^(D-2).

What happens is that the valuation of log(A) being positive,
one digit of relative precision is lost.

Cheers,
Bill.