[Cado-nfs-discuss] FactorBaseFormat

Pankaj Charpe charpe.pankajamol at gmail.com
Mon Feb 5 11:57:02 CET 2018


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 at 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 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/8ee88044/attachment-0001.html>


More information about the Cado-nfs-discuss mailing list