Re: Tower field extensions in libPARI

On Thu, 19 Mar 2020 at 09:12, Aleksandr Lenin <aleksandr.lenin@cyber.ee> wrote:

Good morning John,

I'm sorry, I didn't express myself clearly yesterday. By saying that
Sage was also struggling to obtain the cardinality of a curve defined
over (F_11[Y]/(y^2+1))[X]/(x^6 + (y + 3)) I was literally meaning that
(F_11[Y]/(y^2+1))[X]/(x^6 + (y + 3)) was constructed as 6-th degree
extension of a 2-nd degree extension of F_11. I was using the following
code (2 versions):

F = GF(11)
R.<x> = PolynomialRing(F,'x')
F1.<x> = F.extension(x^2^1,'x')
S.<y> = PolynomialRing(F1,'y')
F2 = F1.extension(y^6 + (x+3),'y')
E = EllipticCurve(F2,[0,1])
E.cardinality()

and

E = EllipticCurve(F,[0,1])
E = E.base_extend(F1)
E = E.base_extend(F2)
E.cardinality()

In both cases, E is reported to be an "Elliptic Curve defined by y^2 =
x^3 + 1 over Univariate Quotient Polynomial Ring in y over Univariate
Quotient Polynomial Ring in x over Finite Field of size 11 with modulus
x^2 with modulus y^6 + x + 3".

Also in both cases, the call E.cardinality() returns an error
"AttributeError: 'EllipticCurve_generic_with_category' object has no
attribute 'cardinality'".

This is exactly what I mean by saying Sage is struggling to calculate
it. But indeed, Sage has no problem calculating the cardinality over a
12-th degree extension of F_11, and gives 3138424833600.

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.

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