RE: Oddities modulo multivariate polynomials

["Kerl, John" <John.Kerl@Avnet.com>]

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
situation was adequate for me.

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.)
Thanks for the reply.

Allright now I think I understand what the problem is.  Is there an easy
way to solve this issue?  Wat I really want to do is arithmetic in a
ring of the form

Fp[X,Y] / (f(X), g(X,Y))

This is: a finite field (with prime order, so it's just modulo p) with 2
variables modulo two polynomials.  Can this be done with GP?
If it can't be done directly, I'll probably try to hack something like
that myself.