Discussion related to cado-nfs

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

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 ? 

-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.
> >> > >
> >>
> >
> >