John Cremona on Thu, 19 Mar 2020 12:56:31 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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