Kerl, John on Thu, 9 Oct 2003 13:57:24 -0700

 RE: Oddities modulo multivariate polynomials

```Jeroen:

What I used in precisely the same situation (extensions
of finite fields) was the following workaround.

One field is Fp(a), satisfying, say, a quadratic monic
irreducible; the other is Fp(b), satisfying, say, a cubic
monic irreducible.  Then elements of Fp(a)(b) are polynomials
in b which have coefficients that are polynomials in a,
and vice versa for Fp(b)(a).  The workaround was to use an
intermediate variable x, compute with that, then subst at the
end of computations.

For example:

\\ Polynomial modulus for F_2^2:
ra=Mod(1,2)*(a^2+a+1);
\\ Polynomial modulus for F_2^3:
rb=Mod(1,2)*(b^3+b+1);

\\ Polynomial modulus for F_2^6, when viewed as a cubic
\\ extension of F_2^2:
rra = Mod(1,ra) * x^3 + Mod(0,ra) * x^2 + Mod(1,ra) * x + Mod(1,ra);
\\ Polynomial modulus for F_2^6, when viewed as a quadratic
\\ extension of F_2^3:
rrb = Mod(1,rb) * x^2 + Mod(1,rb) * x + Mod(1,rb);

\\ An element of F_2^6:
ga = Mod(1,ra) * x^2 + Mod(a+1,ra) * x + Mod(1, ra);
gma = Mod(ga, rra);
\\ An element of F_2^6:
gb = Mod(b,rb) * x + Mod(b^2+b+1,rb);
gmb = Mod(gb, rrb);

Note however that subst'ing x for b doesn't seem to descend
into the polmod structures (I haven't researched why not),
but I found I could subst after lifting, which in this

For example:

? lift(lift(subst(gma,x,b)))
%15 = x^2 + (a + 1)*x + 1

whereas:

? subst(lift(lift(gma)),x,b)
%16 = b*a + (b^2 + b + 1)

-----Original Message-----
From: Jeroen Demeyer [mailto:jdemeyer@cage.ugent.be]
Sent: Thursday, October 09, 2003 1:13 PM
To: pari-users@list.cr.yp.to
Subject: Re: Oddities modulo multivariate polynomials

On Thu, Oct 09, 2003 at 08:51:32AM +0200, Gerhard Niklasch wrote:
> Hi Jeroen,
>
> > Could anyone please explain what is happening here:
> >
> >                   GP/PARI CALCULATOR Version 2.1.5 (released)
> >                 i686 running linux (ix86 kernel) 32-bit version
> >                 (readline v4.3 enabled, extended help available)
> >
> > ? Y                   /* Make sure Y is defined first */
> > %1 = Y
> > ? (Y^2) % (X^3 - Y^2)
> > %2 = X^3
> > ? (X^3) % (X^2 + 1)
> > %3 = -X
> > ? ((Y^2) % (X^3 - Y^2)) % (X^2 + 1)
> > %4 = 0
> >
> > How come the outputs of the two last statements are different?  Is this
> > a bug or am I doing something wrong?  Any help would be appreciated.
>
> Hint: %2 is a polynomial in Y, of degree 0, with constant term X^3.
> (\x will show this.)
>
> Thus the last '%' operation is performed in Q(X)[Y], not in Q[X],
> and the result is correct for Q(X)[Y] (where (X^2+1) is a nonzero
> constant and thus invertible - everything is divisible by it without
> remainder.)
>
> Evaluate %2 at Y=0 or just extract the coefficient to get the desired
> polynomial in X.
>
> (Just another facet of the general fact that PARI deals in polynomials
> in one variable over fields, not in multivariate polynomials, unlike
> most computer _algebra_ software.)