Re: Tower field extensions in libPARI

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

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.