Re: Tower field extensions in libPARI

On Wed, 18 Mar 2020 at 19:57, Aleksandr Lenin <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.
>>
>