Discussion related to cado-nfs

[Pierrick Gaudry <pierrick.gaudry@loria.fr>]

You have to think p-adically: we look for x in Q_2 such that f(x) = 0 in
Q_2. The 2-adic number x cannot be represented exactly, but we can find
approximations of it modulo 2^k for k as high as we want.

Another way of answering your question is that f(44) = 0 modulo a higher
power of 2 than f(172), therefore 44 is a better lift than 172.

In Sagemath:

Q2 = pAdicField(2, 50)
Q2X.<x> = Q2['x']
f = 1790958688632-666051894*x-967547*x^2+40*x^3
f.roots()

and you can see that one of the roots is 1120936292249644 mod 2^50. This
is the one we are talking about. If you reduce it mod 2^128 we get 44.

Regards,
Pierrick


On Mon, Aug 10, 2020 at 02:48:17PM +0430, Sayyed Ahmad Mousavi wrote:
> Dear Pierrick,
> Thank you very much for your answer. From yesterday to now, I tried to
> understand your answer. But, I can not find out your reason.
> What means correct lift of 44 (mod 128)? We know that f'(44)= 0 (mod 2); So
> we have two lifts for 44 (mod 256). One of them is 44, and the other is
> 172.
> 
> Best regards
> Sayyed Ahmad
> 
> 
> On Sun, Aug 9, 2020 at 12:28 PM Pierrick Gaudry <pierrick.gaudry@loria.fr>
> wrote:
> 
> > Dear Sayyed,
> >
> > I think the output of makefb is correct on this example.
> > There are 3 2-adic roots for this polynomials, and indeed the
> > approximation mod 256 of them are 44, 178 and 376.
> >
> > You mention 172, but this is not the correct lift of the first root mod
> > 256. The value 44 (=172 mod 128) is the one you want.
> >
> > Regards,
> > Pierrick
> >
> > On Sun, Aug 09, 2020 at 12:06:41PM +0430, Sayyed Ahmad Mousavi wrote:
> > > Hello All
> > >
> > > I have the following problem in the makefb program.
> > >
> > > Consider the following output of makefb
> > >
> > >
> > > # Roots for polynomial 1790958688632-666051894*x-967547*x^2+40*x^3
> > > # DEGREE: 3
> > > # lim = 2
> > > # maxbits = 9
> > > 2: 2
> > > 2:2,0: 0
> > > 4:2,1: 4
> > > 4:3,2: 0,2
> > > 8:3,2: 8
> > > 8:4,3: 2,4
> > > 16:4,3: 24
> > > 16:5,4: 2,12
> > > 32:5,4: 56
> > > 32:6,5: 12,18
> > > 64:6,5: 120
> > > 64:7,6: 44,50
> > > 128:7,6: 248
> > > 128:8,7: 44,50
> > > 256:8,7: 376
> > > 256:9,8: 44,178
> > > 512:9,8: 888
> > >
> > >
> > > We know that f(172)=0 (mod 256), but 172 does not exist in the above
> > list?
> > >
> > >
> > > Regards
> > >
> > > Sayyed Ahmad Mousavi
> >
> > > _______________________________________________
> > > Cado-nfs-discuss mailing list
> > > Cado-nfs-discuss@lists.gforge.inria.fr
> > > https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss
> >
> >