Manuel Kauers Hagenberg, December 17, 2002 RISC-Linz

Computer Algebra Exercises

Solution 3

Ex. (11) According to MAPLE, the polynomial p(x) = x^{3} + 2x + 1 is irreducible over ℤ_{3}[x]:^{1}

>> Factor(x^3+2*x+1) mod 3;

x^{3} + 2x + 1

>> p:=%:

So we can define GF(27) := ℤ_{3}[x]/(p). The following table shows all elements

b_{2}x^{2} + b_{1}x + b_{0} ∈ GF(27)

as powers of x as well as their respective minimal polynomials.

\begin{matrix}n & x^{n} & b_{2} & b_{1} & b_{0} & min poly /ℤ_{3} \\ ∗ & 0 & 0 & 0 & 0 & x \\ 0 & 1 & 0 & 0 & 1 & x + 2 \\ 1 & x & 0 & 1 & 0 & p(x) \\ 2 & x^{2} & 1 & 0 & 0 & x^{3} + x^{2} + x + 2 \\ 3 & x + 2 & 0 & 1 & 2 & x^{3} + 2x + 1 \\ 4 & x^{2} + 2x & 1 & 2 & 0 & x^{3} + x^{2} + 2 \\ 5 & 2x^{2} + x + 2 & 2 & 1 & 2 & x^{3} + 2x^{2} + x + 1 \\ 6 & x^{2} + x + 1 & 1 & 1 & 1 & x^{3} + x^{2} + x + 2 \\ 7 & x^{2} + 2x + 2 & 1 & 2 & 2 & x^{3} + x^{2} + 2x + 1 \\ 8 & 2x^{2} + 2 & 2 & 0 & 2 & x^{3} + 2x^{2} + 2x + 2 \\ 9 & x + 1 & 0 & 1 & 1 & x^{3} + 2x + 1 \\ 10 & x^{2} + x & 1 & 1 & 0 & x^{3} + x^{2} + 2 \\ 11 & x^{2} + x + 2 & 1 & 1 & 2 & x^{3} + x^{2} + 2x + 1 \\ 12 & x^{2} + 2 & 1 & 0 & 2 & x^{3} + x^{2} + 2 \\ 13 & 2 & 0 & 0 & 2 & x + 1 \\ 14 & 2x & 0 & 2 & 0 & x^{3} + 2x + 2 \\ 15 & 2x^{2} & 2 & 0 & 0 & x^{3} + 2x^{2} + x + 1 \\ 16 & 2x + 1 & 0 & 2 & 1 & x^{3} + 2x + 2 \\ 17 & 2x^{2} + x & 2 & 1 & 0 & x^{3} + 2x^{2} + 1 \\ 18 & x^{2} + 2x + 1 & 1 & 2 & 1 & x^{3} + x^{2} + x + 2 \\ 19 & 2x^{2} + 2x + 1 & 2 & 2 & 1 & x^{3} + 2x^{2} + x + 1 \\ 20 & 2x^{2} + x + 1 & 2 & 1 & 1 & x^{3} + 2x^{2} + 2x + 2 \\ 21 & x^{2} + 1 & 1 & 0 & 1 & x^{3} + x^{2} + 2x + 1 \\ 22 & 2x + 2 & 0 & 2 & 2 & x^{3} + 2x + 2 \\ 23 & 2x^{2} + 2x & 2 & 2 & 0 & x^{3} + 2x^{2} + 1 \\ 24 & 2x^{2} + 2x + 1 & 2 & 2 & 1 & x^{3} + 2x^{2} + 2x + 2 \\ 25 & 2x^{2} + 1 & 2 & 0 & 1 & x^{3} + 2x^{2} + 1 \\ 26 & 1 & 0 & 0 & 1 & x + 2 \end{matrix}

1By hand irreducibility can be checked via p(0) = 1, p(1) = 1, p(2) = 1.

According to p. 48 (and to Tobias ;-), the minimal polynomial for β = x^{k} is given by the formula

m_{β}(y) = ∏_{i=0}^{2}(y − β^{3^{i}}).

In MAPLE,

>> m := k -> Rem((y-Rem(x^k, p, x) mod 3) *
>>     (y-Rem(x^(3*n), p, x) mod 3) *
>>     (y-Rem(x^(9*n), p, x) mod 3), p, x) mod 3;

defines a function m which maps k ∈ ℕ_{0} to the minimal polynomial of x^{k} ∈ GF(27) over ℤ_{3}.

Ex. (12) We need two irreducible polynomials p_{1}, p_{2} ∈ ℤ_{2}[x] both of degree 3. Let’s take

p_{1}(x) = x^{3} + x + 1, p_{2}(x) = x^{3} + x^{2} + 1

and let F_{1} := ℤ_{2}[x]/(p_{1}), F_{2} := ℤ_{2}[x]/(p_{2}). We prove F_{1} ≅ F_{2} by providing an isomorphism.

Using MAPLE, we verify that each of the two fields is generated by the polynomial q(x) = x^{2} + x + 1. Let i: F_{1} → F_{2} map 0 ∈ F_{1} to 0 ∈ F_{2} and each a = q^{n_{a}} mod p_{1} ∈ F_{1} to q^{n_{a}} mod p_{2} ∈ F_{2}. Then i is an isomorphism: Take a = q^{n_{a}} mod p_{1}, b = q^{n_{b}} mod p_{1} ∈ F_{1}. Then

i(a · b) = i(q^{n_{a}} · q^{n_{b}} mod p_{1}) = i(q^{n_{a}+n_{b}} mod p_{1})
= q^{n_{a}+n+b} mod p_{2} = q^{n_{a}} · q^{n_{b}} mod p_{2}
= i(a) · i(b),
i(a + b) = i(q^{n_{a}} + q^{n_{b}} mod p_{1}) = q^{n_{a}} + q^{n_{b}} mod p_{2}
= i(a) + i(b).

This completes the proof. .

Ex. (13) For the special case of constant g = 0 take r = h = 0. Now, assume g ≠ 0. We furthermore assume deg f ≥ 1 to avoid trouble. Then deg f ≤ deg ff′, so deg g < deg ff′. As f is square free, f and f′ are relatively prime, so we can apply the corollary to Theorem 3.1.2., i.e. there are u, v ∈ ℚ[x] such that

g = uf + vf′

with deg u ≤ deg f′ < deg f and deg v < deg f which can be computed by Euclid. We plug this into the integral, and start some calculation (using the fact that n ≥ 2):

∫ \frac{g(x)}{f(x)^{n}} dx = ∫ \frac{u(x)f(x) + v(x)f′(x)}{f(x)^{n}} dx

= ∫ \frac{u(x)}{f(x)^{n−1}} dx + ∫ \frac{f′(x)}{f(x)^{n}} · v(x) dx

= ∫ \frac{u(x)}{f(x)^{n−1}} dx − \frac{1}{n − 1} \frac{v(x)}{f(x)^{n−1}} + \frac{1}{n − 1} ∫ \frac{v′(x)}{f(x)^{n−1}} dx

= \underbrace{−\frac{1}{n − 1} \frac{v(x)}{f(x)^{n−1}}}_{=:r(x)} + ∫ \frac{\overbrace{u(x) − \frac{1}{n−1}v′(x)}^{=:h(x)}}{f(x)^{n−1}} dx.

Note that indeed deg h < deg f because deg v′ ≤ deg v and both deg u and deg v are known to be less than deg f by construction. .

Ex. (14) Given two polynomials u, v ∈ ℤ_{7}[x]:

u(x) = 3x^{6} + x^{5} + 4x^{4} + 4x^{3} + 3x^{2} + 4x + 1,
v(x) = 2x^{6} + 4x^{5} + 3x^{4} + 4x^{3} + 4x^{2} + x + 3.

What is their gcd? Let’s once again ask MAPLE for help.

>> Rem(u, v, x) mod 7;

2x^{5} + 3x^{4} + 5x^{3} + 4x^{2} + 6x + 1

>> Rem(v, %, x) mod 7;

x^{3} + 3x^{2} + 5x + 3

>> Rem(%%, %, x) mod 7;

x^{2} + 2x + 2

>> Rem(%%, %, x) mod 7;

x + 1

>> Rem(%%, %, x) mod 7;

1

>> Rem(%%, %, x) mod 7;

0

So, gcd(u, v) = 1.

Ex. (15) Without loss of generality, we may assume m > n. Because of quot(x^{m} − 1, x^{n} − 1) = x^{m−n} and

x^{m} − 1 − x^{m−n}(x^{n} − 1) = x^{m−n} − 1

we find as an invariant that u and v are always of the form x^{k} − 1 for some k ∈ ℕ_{0}, and that deg u keeps larger than deg v.

We proceed to prove the claim that r, s, r′, s′ are always of the desired form by induction along the loop of the algorithm. For the induction start,

(u, r, s, v, r′, s′) = (x^{m} − 1, 1, 0, x^{n} − 1, 0, 1),

it is clear that r, s, r′, s′ are of the desired form.

As for the induction step, assume the state

(u, r, s, v, r′, s′) = (x^{i} − 1, r_{0}, s_{0}, x^{j} − 1, r′_{0}, s′_{0})

where r_{0}, s_{0}, r′_{0}, s′_{0} are of the desired form by IH. To get to the next step, we compute q = quot(u, v) = x^{i−j} and get

(u, r, s, v, r′, s′) ← (v, r′_{0}, s′_{0}, x^{i−j} − 1, r′_{0} − x^{i−j}r_{0}, s′_{0} − x^{i−j}s_{0}).

It turns out that the new r, s, r′, s′ are still of the desired form. . For the special u = x^{21} − 1, u = x^{13} − 1, we find

x − 1 = gcd(u, v) = \underbrace{(x^{11} + x^{8} + x^{6} + x^{3} + 1)}_{=r} ·u

− \underbrace{(x^{19} + x^{16} + x^{14} + x^{11} + x^{8} + x^{6} + x^{3} + x)}_{=s} ·v