[Cado-nfs-discuss] FactorBaseFormat

Pankaj Charpe charpe.pankajamol at gmail.com
Mon Feb 5 11:20:56 CET 2018


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 at 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 at 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 at 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 at 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 at 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 at lists.gforge.inria.fr
> > >> > > >> https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-
> discuss
> > >> > > >
> > >> > > >_______________________________________________
> > >> > > >Cado-nfs-discuss mailing list
> > >> > > >Cado-nfs-discuss at lists.gforge.inria.fr
> > >> > > >https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss
> > >> > >
> > >> > > --
> > >> > > Sent from my phone. Please excuse brevity and misspellings.
> > >> > >
> > >>
> > >
> > >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/attachments/20180205/e1acbefd/attachment-0001.html>


More information about the Cado-nfs-discuss mailing list