Discussion related to cado-nfs

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

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