Discussion related to cado-nfs

[Pankaj Charpe <charpe.pankajamol@gmail.com>]

can you please provide a link to any reference paper to study this?  It will be very helpful to me.

-pankaj

On Mon, Feb 5, 2018 at 4:27 PM, Pankaj Charpe <charpe.pankajamol@gmail.com> wrote:

okay. Now got it.Thank you very much for the valuable information.

-pankaj

On Mon, Feb 5, 2018 at 3:56 PM, Emmanuel Thomé <Emmanuel.Thome@inria.fr> wrote:

On Mon, Feb 05, 2018 at 03:50:56PM +0530, Pankaj Charpe wrote:
> Yeah this my question. From your answer what I understood , 1 and 6 are
> roots for both mod 5 and mod 25.Then in order to get the distinct root we
> replace x by 1+5*x in case of mod 5. am I clear on this ?
> How this linear composition F(a*x+b) will help us to get the distinct roots
> ? Can you please elaborate it ?

f=(x-1)*(x-6)+125

solve for x in f(1+5*x) = 0 mod 125.

We're essentially doing hensel lifting step by step because this is a bit
nasty in this case.

E.

>
> -Pankaj
>
> On Mon, Feb 5, 2018 at 3:31 PM, Emmanuel Thomé <Emmanuel.Thome@inria.fr>
> wrote:
>
> > On Mon, Feb 05, 2018 at 03:20:13PM +0530, Pankaj Charpe wrote:
> > > Respected sir,
> > >
> > > I have one last doubt in understanding factor base construction.
> > >
> > > *In ffs/makefb.c*
> >
> > This is related to ffs, which is now an obsolete algorithm.
> >
> > But presumably what you describe holds nonetheless both for FFS and NFS.
> >
> > > we find all the affine roots which satisfies the equation  f(r)=0 modp .
> > >
> > > I am clear with all the procedure except one, when the multiplicity of
> > the
> > > root more than one then why  we are finding linear compostion  FF(x) :=
> > > F(phi1 * x + phi0) and recursively calling affine_roots.
> > > what is the need to find linear combination of a polinomial in case of
> > > multiplicity ? Can you please brief that else block. I will be very
> > > thankful to you.
> >
> > I'm not sure I understand your question correctly.
> >
> > If you have a multiple root, let's say in the case of (x-1)*(x-6)+125
> > which has the double root 1 mod 5, then clearly you need to replace x by
> > 1+5*x in order to tell apart the two distinct roots given by the
> > congruence classes 1 mod 25 and 6 mod 25.
> >
> > E.
> >
> > > Thanks & Regards
> > > Pankaj Charpe
> > >
> > >
> > >
> > > On Mon, Feb 5, 2018 at 11:49 AM, Pankaj Charpe <
> > charpe.pankajamol@gmail.com>
> > > wrote:
> > >
> > > > I am clear with this now. Thanks for the explanation.
> > > >
> > > > -Pankaj charpe
> > > >
> > > > On Mon, Feb 5, 2018 at 1:28 AM, Emmanuel Thomé <
> > Emmanuel.Thome@inria.fr>
> > > > wrote:
> > > >
> > > >> On Sat, Feb 03, 2018 at 08:12:49PM +0530, Pankaj Charpe wrote:
> > > >> > Thanks for the reply. I have studied your thesis. p and r (roots)
> > are
> > > >> clear
> > > >> > to me but I am not getting any explanation for those n1 and n2. Can
> > you
> > > >> > elaborate their use? I would really appreciate your reply. I also
> > mailed
> > > >> > via mailing list.
> > > >> >
> > > >> > Thanks & Regards
> > > >> > Pankaj Charpe
> > > >>
> > > >> Hi,
> > > >>
> > > >> Let's say we have:
> > > >>
> > > >> 5: 1,3
> > > >> 25:2,1: 6,13
> > > >>
> > > >> All pairs with a-1*b = 0 mod 5 or a-3*b = 0 mod 5 must receive a
> > > >> contribution equal to round(log(5)).
> > > >>
> > > >> Pairs with a-6*b = 0 mod 25 (which implies, in particular, a-1*b = 0
> > mod
> > > >> 5) receive an extra contribution of round(2*log(5))-round(1*log(5)).
> > > >>
> > > >> A polynomial with this behaviour could be, for example (two distinct
> > > >> examples below):
> > > >>     sage: ((x-6)*(x-13)+25).expand()
> > > >>     x^2 - 19*x + 103
> > > >>     sage: ((x-6)*(x-13)*ZZ['x'](GF(5)['x'].irreducible_element(2))+
> > 25)
> > > >> .expand()
> > > >>     x^4 - 15*x^3 + 4*x^2 + 274*x + 181
> > > >>
> > > >> And it can go on and on, as you lift to higher 5-adic roots.
> > Unramified
> > > >> roots in the p-adics will follow a simple pattern of this kind.
> > > >>
> > > >> Now there are cases for which we need more information. Consider for
> > > >> example the polynomial:
> > > >>     sage: ((x-6)*(x-1)+25).expand()
> > > >>     x^2 - 7*x + 31
> > > >>
> > > >> For a-1*b = 0 mod 5, the 5-valuation goes from 0 to 2. We write this
> > as:
> > > >>
> > > >>     5:2,0: 1
> > > >>
> > > >> while for higher powers we would write:
> > > >>
> > > >>     25:3,2: 1,6
> > > >>
> > > >> All sorts of situations are possible. The factor base format is meant
> > to
> > > >> express the different things that can occur in down-to-earth terms.
> > > >>
> > > >> E.
> > > >>
> > > >>
> > > >>
> > > >>
> > > >>
> > > >>
> > > >>
> > > >> > On Feb 3, 2018 5:30 PM, "Emmanuel Thomé" <emmanuel.thome@inria.fr>
> > > >> wrote:
> > > >> >
> > > >> > > Yes.
> > > >> > > Actually log(p) would be less misleading than degree(p)...
> > > >> > > E.
> > > >> > >
> > > >> > >
> > > >> > > On February 3, 2018 11:21:24 AM GMT+01:00, Pierrick Gaudry <
> > > >> > > pierrick.gaudry@loria.fr> wrote:
> > > >> > > >Hi,
> > > >> > > >
> > > >> > > >From an old README file I have somewhere in an old directory:
> > > >> > > >
> > > >> > > >    Factor base file format:
> > > >> > > >    ------------------------
> > > >> > > >
> > > >> > > >    An entry is of the form:
> > > >> > > >
> > > >> > > >    q:n1,n2: r1,r2,r3
> > > >> > > >
> > > >> > > >    In the (frequent) case where n1,n2=1,0 this can be abridged
> > with:
> > > >> > > >
> > > >> > > >    q: r1,r2,r3
> > > >> > > >
> > > >> > > >Here, q is a irreducible or a irreducible power, ri are the
> > > >> > > >corresponding
> > > >> > > >roots and the contribution that must be subtracted at these
> > positions
> > > >> > > >is
> > > >> > > >    (n1-n2)*degree(p) (assuming smaller powers of this
> > irreducible
> > > >> have
> > > >> > > >  alredy been taken care of).  By position, we mean (a,b) such
> > that
> > > >> a -
> > > >> > > >    b*ri = 0 mod q.
> > > >> > > >
> > > >> > > > The roots ri must be sorted in lexicographical order.  If a
> > root ri
> > > >> is
> > > >> > > >    greater or equal to q, it means that this is a projective
> > root:
> > > >> > > >    subtracting q gives a root for the reciprocal polynomial (or
> > > >> > > >    equivalently, (1:(ri-q)) is the projective root).
> > > >> > > >
> > > >> > > > It is allowed to have several lines with the same q, but there
> > must
> > > >> be
> > > >> > > >    only one line for a given (q,n1,n2) triple.
> > > >> > > >
> > > >> > > >Hopefully this is still valid in the version you are using.
> > > >> > > >
> > > >> > > >Regards,
> > > >> > > >Pierrick
> > > >> > > >
> > > >> > > >On Sat, Feb 03, 2018 at 01:50:46PM +0530, Pankaj Charpe wrote:
> > > >> > > >> Hi,
> > > >> > > >>  In factor base construction of cado-nfs we have this entry,
> > > >> > > >>                             Factor Base format:
> > q:n1,n2:r1,r2,r3
> > > >> > > >>
> > > >> > > >> Can you please explain me what is these n1 and n2 ?. I will be
> > very
> > > >> > > >> thankful to you.
> > > >> > > >>
> > > >> > > >>
> > > >> > > >> Thanks & Regards
> > > >> > > >> Pankaj charpe
> > > >> > > >
> > > >> > > >> _______________________________________________
> > > >> > > >> Cado-nfs-discuss mailing list
> > > >> > > >> Cado-nfs-discuss@lists.gforge.inria.fr
> > > >> > > >> https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-
> > discuss
> > > >> > > >
> > > >> > > >_______________________________________________
> > > >> > > >Cado-nfs-discuss mailing list
> > > >> > > >Cado-nfs-discuss@lists.gforge.inria.fr
> > > >> > > >https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss
> > > >> > >
> > > >> > > --
> > > >> > > Sent from my phone. Please excuse brevity and misspellings.
> > > >> > >
> > > >>
> > > >
> > > >
> >