[Cado-nfs-discuss] FactorBaseFormat

Pankaj Charpe charpe.pankajamol at gmail.com
Mon Feb 5 12:01:01 CET 2018


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 at 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 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-dis
>> cuss
>> > > > >> > >
>> > > > >> > > --
>> > > > >> > > 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/071b1875/attachment-0001.html>


More information about the Cado-nfs-discuss mailing list