| Aleksandr Lenin on Thu, 19 Mar 2020 14:28:32 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| Re: Tower field extensions in libPARI |
Aleksandr
On 3/19/20 1:56 PM, John Cremona wrote:
> Can you report this as a bug via the sage-devel or sage-support mailing
> lists? The way you have constructed the field extensions has somehow
> bypassed Sage's normal way to construct field extensions, with the
> result that the final object E in your code has the wrong type (it
> should be EllipticCurve_finite_field or similar). There is no
> cardinality method for such a generic elliptic curve type. If it had
> the right type it would find the cardinality easily, by recognising that
> the j-invariant was in the prime field, doing a point count there (or in
> this case seeing that j=0 and using the appropriate formula) and then
> determining the carinality over the extension field using a standard
> formula.
Done. I sent the description of the issue together with the two samples
I've produced, your interpretation of what's possibly happening and the
two code examples below to sage-devel. After the post passes moderation,
it will appear.
>
> With apologies to pari people for more Sage code:
>
> sage: F = GF(11)
> sage: x = polygen(F)
> sage: F1.<a> = F.extension(x^2+1)
> sage: y = polygen(F1)
> sage: F2.<b> = F1.extension(y^6+a+3)
> sage: F, F1, F2
> (Finite Field of size 11,
> Finite Field in a of size 11^2,
> Univariate Quotient Polynomial Ring in b over Finite Field in a of size
> 11^2 with modulus b^6 + a + 3)
> sage: E = EllipticCurve(F,[0,1])
> sage: E1 = E.change_ring(F1)
> sage: E2 = E.change_ring(F2)
> sage: E.cardinality()
> 12
> sage: E1.cardinality()
> 14
> sage: E2.cardinality()
> (error message as in your post)
>
> If instead you construct F2 by giving just its degree over F1 and not a
> specific polynomial, all is well:
> sage: F2 = F1.extension(6)
> sage: F2
> Finite Field in z12 of size 11^12
> sage: E2 = E.change_ring(F2)
> sage: E2.cardinality()
> 3138424833600
>
> but the polynomial is not the one you wanted:
>
> sage: F2.gen().minpoly()
> x^12 + x^8 + x^7 + 4*x^6 + 2*x^5 + 5*x^4 + 5*x^3 + 6*x^2 + 5*x + 2
>
>
>
>
> Aleksandr
>
> On 3/18/20 10:02 PM, John Cremona wrote:
> >
> >
> > On Wed, 18 Mar 2020 at 19:57, Aleksandr Lenin
> <aleksandr.lenin@cyber.ee <mailto:aleksandr.lenin@cyber.ee>
> > <mailto:aleksandr.lenin@cyber.ee
> <mailto:aleksandr.lenin@cyber.ee>>> wrote:
> >
> > A follow-up question, as it appears I also have difficulties doing
> > elliptic curve operations in F_11^2^6. Consider a BN curve E
> defined by
> > y^2 = x^3 + 1 defined over (F_11[Y]/(y^2+1))[X]/(x^6 + (y + 3)).
> >
> > To set up the extension field, I run the following code:
> >
> > long var_y = fetch_user_var("y");
> >
> > GEN p = stoi(11);
> >
> > // T = y^2 + 1 in F_p[Y]
> > GEN T = mkpoln(3,gen_1,gen_0,gen_1);
> > setvarn(T,var_y);
> >
> > // s = y + 3 in F_p[Y]
> > GEN s = mkpoln(2,gen_1,stoi(3));
> > setvarn(s,var_y);
> >
> > // U = x^6 + (y + 3) in (F_p[Y]/(T))[X]
> > GEN U = mkpoln(7, pol_1(0), pol_0(0), pol_0(0), pol_0(0),
> > pol_0(0), pol_0(0), s);
> >
> >
> > I asked for the cardinality of an elliptic group of a curve
> defined over
> > (F_11[Y]/(y^2+1))[X]/(x^6 + (y + 3)) by running a call
> > FpXQ_ellcard(pol_0(0),pol_1(0),U,p). The cardinality was
> reported to be
> > 1774224, which looks suspicious to me, as I expected a much bigger
> > number there. I checked it in SageMath. Sage also was
> struggling to
> > obtain the cardinality of a curve defined over
> (F_11[Y]/(y^2+1))[X]/(x^6
> > + (y + 3)), but for a 12-th degree extension of F_11, the
> cardinality
> > should be 3138424833600, according to SageMath. Why does
> FpXQ_ellcard
> > report 1774224?
> >
> >
> > sage:
> EllipticCurve(GF(11),[0,0,0,0,1]).cardinality(extension_degree=12)
> > 3138424833600
> >
> > 103ms
> >
> >
> >
> > Operations on point curves end up in a crash. In example, the call
> > FpXQE_mul(mkvec2(pol_0(0),pol_1(0)),stoi(10),gen_0,U,p)
> produces "bug in
> > PARI/GP (Segmentation Fault), please report."
> >
> > Do I need some version of FpXQXQE_ function here? I'm obviously
> > tourchering and probably misusing libPARI here, but I hope to
> be able to
> > do something useful with elliptic curves defined over towered
> extension
> > fields.
> >
> > Aleksandr
> >
> > On 3/18/20 6:13 PM, Aleksandr Lenin wrote:
> > > thanks, Bill
> > >
> > > Aleksandr
> > >
> > > On 3/18/20 5:31 PM, Bill Allombert wrote:
> > >> On Wed, Mar 18, 2020 at 05:08:24PM +0200, Aleksandr Lenin
> wrote:
> > >>> Hello,
> > >>>
> > >>> I am trying to build a 12-th degree extension of a prime
> finite
> > field as
> > >>> a degree-6 extension of degree-2 extension of F_p.
> > >>>
> > >>> I seem to get a working solution in libPARI (working = doesn't
> > crash nor
> > >>> overflow the stack), but the results I get are somewhat
> > unexpected. Let
> > >>> me describe what I am doing in libPARI step-by step.
> > >>>
> > >>> Let p = 11, hence F_11 is the base field.
> > >>>
> > >>> In libPARI, it translates into the following lines of code:
> > >>>
> > >>> GEN p = stoi(11);
> > >>> GEN T = mkpoln(3,gen_1,gen_0,gen_1); // T = x^2 + 1
> > >>>
> > >>>
> > >>> Now that I have p and T, I can reduce any polynomials in
> Z[X] to
> > >>> F_11[X]/(x^2+1). In example, x^2+1 is 0 in F_11^2, and the
> following
> > >>> code works fine, the results are consistent.
> > >>>
> > >>> FpXQ_red(mkpoln(3,gen_1,gen_0,gen_1),T,p); // x^2 + 1 ---> 0
> > >>> FpXQ_red(mkpoln(3,gen_1,gen_1,gen_1),T,p); // x^2 + x +
> 1 ---> x
> > >>> FpXQ_red(mkpoln(3,gen_1,gen_0,gen_0),T,p); // x^2 ---> 10
> > >>>
> > >>> So far so good. Next, I build a degree 6 extension of
> F_11^2 to
> > obtain
> > >>> F_11^12 = (F_11[X]/(x^2+1))[Y]/(y^6 + x + 3). First, I need to
> > represent
> > >>> polynomial y^6 + x + 3 as a polynomial in variable y, with the
> > >>> coefficients being polynomials in F_11[X]/(x^2+1). I achieve
> > this with
> > >>> the following lines of code.
> > >>>
> > >>> long var_y = fetch_user_var("y"); // activate variable y
> > >>> // U = y^6 + (x + 3)
> > >>> GEN U = mkpoln(7, pol_1(0), pol_0(0), pol_0(0), pol_0(0),
> > >>> pol_0(0), pol_0(0),
> mkpoln(2,gen_1,stoi(3)));
> > >>> setvarn(U,var_y); // polynomial U in variable 'y'
> > >>
> > >> Beware, in gp, x has high priority than y,
> > >> so U must be
> > >> U = x^6 + (y + 3)
> > >> and T must be
> > >> T = y^2+1
> > >>
> > >> A lot of low level function will still work with
> polynomials with
> > invalid
> > >> variable ordering, but other will fail.
> > >>
> > >>> Now, I would expect that U maps to 0 in F_11^2^6, but it
> appears
> > it is
> > >>> not the case in libPARI. The call to FpXQX_red(U,U,p)
> returns U
> > instead
> > >>> of 0.
> > >>
> > >> FpXQX_red(U,U,p) is not valid.
> > >>
> > >> What is valid is either:
> > >> FpXQX_red(U,T,p) (reduce the coefs of U mod T,p)
> > >> FpXQX_rem(U,U,T,p) (compute U%U mod T,p)
> > >>
> > >> Maybe what you are after would be if it existed:
> > >> FpXQXQ_red(U,U,T,p) (reduce U mod U,T,p)
> > >>
> > >> this last one is not present in the library, it is defined as
> > >>
> > >> GEN FpXQXQ_red(GEN U, GEN S, GEN T, GEN p)
> > >> { return FpXQX_rem(FpXQX_red(U, T, p), S, T, p); }
> > >>
> > >> Cheers,
> > >> Bill.
> > >>
> > >
> >
>