Re: Tower field extensions in libPARI

[Aleksandr Lenin <aleksandr.lenin@cyber.ee>]

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