[Cado-nfs-discuss] FactorBaseFormat

Pankaj Charpe charpe.pankajamol at gmail.com
Mon Feb 5 10:50:13 CET 2018


Respected sir,

I have one last doubt in understanding factor base construction.

*In ffs/makefb.c*

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.

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/de8cacc1/attachment-0001.html>


More information about the Cado-nfs-discuss mailing list