Polynomials

A polynomial in GAP is defined over a certain type of ring (or field) that GAP understands. For example, GAP knows the ring of integers, $\mathbb{Z}$. A variable (such as $x$) cannot be typed into GAP without first being defined.

Example 2.13.7   To define a variable for polynomials over the integers, call it $x$, type x:= Indeterminate( Integers, "x" );;. Now a polynomial such as $x^2-1$ can be defined: f:=x^2-1;. To multiply polynomials, use a $*$: type g:=(x^2-1)*(x-1); and GAP will return the (expanded) product. To evaluate a polynomial at a ring element, use the Value command: for example, Value(f,2); returns $3$.

Example 2.13.8   To define two variables for polynomials over the field $GF(4)$, say $x$ and $y$, type x:= Indeterminate( GF(4), "x" );;,
y:= Indeterminate( GF(4), "y" );;. Now a polynomial such as $x^2-y^2$ can be defined: f:=x^2-y^2;. To multiply polynomials, use a $*$: type g:=(x^2-y^2)*(y-1); and GAP will return the (expanded) product. To evaluate a polynomial at a ring element, use the Value command: for example, Value(f,[x,y],[2,-1]); returns $1$=Z(2)^0.

Type x:= Indeterminate( Rationals, "x" );; and GcdRepresentation( f, g ); for the extended Euclidean algorithm applied to the polynomials $f,g$ in $x$. For example,

GcdRepresentation( x^2+1, x^3+1 );

returns

[ 1/2-1/2*x-1/2*x^2, 1/2+1/2*x ].

To double check this: note

(1/2-1/2*x-1/2*x^2)*(x^2+1)+(1/2+1/2*x )*(x^3+1);

returns $1$, and

Gcd(x^2+1,x^3+1);

returns $1$.

Exercise 2.13.9   Find $gcd(x^2+1,x^3+1);$ over $GF(2)$.

Type R:= PolynomialRing( Rationals, 1 );,
x:= IndeterminatesOfPolynomialRing( R )[1]; and Factors( R, f ); to obtain the factorization of $f$ in $R$. For example, Factors( R, x^2-1 ); gives the factorization

[ -1+x_1, 1+x_1 ].

R:=PolynomialRing(Integers,[``x'']); and the command C:=CompanionMat(p); gives, for a monic polynomial $p$ of degree $n$ over a ring $R$, the companion matrix $C$ for $p$ as an element of $M_n(R)$.

Exercise 2.13.10   Verify the multiplication table in Example 2.7.5.

Exercise 2.13.11   Find all irreducible polynomials of degree $2$ in $\mathbb{F}_3[x]$. Let $p_1(x),...,p_k(x)$ be all the irreducibles you found. Compute $x^i\ {\rm mod}\ p_j(x)$, for all $i>0$ and for each $j$. (Hint: Use PowerMod.)

Find a primitive element of $\mathbb{F}_{9}$.

Exercise 2.13.12   Find all irreducible polynomials of degree $4$ in $\mathbb{F}_2[x]$. Let $p_1(x),...,p_k(x)$ be all the irreducibles you found. Compute $x^i\ {\rm mod}\ p_j(x)$, for all $i>0$ and for each $j$. (Hint: Use PowerMod.)

Find a primitive element of $\mathbb{F}_{16}$.