Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Mathematics
MATHS 328 Assignment
There are 100 marks in total. If you use GAP in your solutions (except for Questions 1 and 2
where GAP is not allowed), then please include a screenshot/printout of your GAP code.
1. (20=5+5+10 marks) [No GAP please]
(a) Express f(x) = x6 + x4 + x + 1 ∈ Z2[x] as a product of irreducible polynomials.
(b) Prove that g(x) = x5 + x2 + 1 ∈ Z2[x] is an irreducible polynomial.
(c) Using the extended Euclidean algorithm, compute (x4 + x3)−1 in the field F = Z2[x]/(g(x)).
2. (20=2+6+4+8 marks) [No GAP please]
Let K = Z3[x]/(x2 + x + 2).
(a) Prove that K is a field.
(b) Show that x + 1 is a primitive element in K by calculating a table of all powers of x + 1.
(c) Using the table you created in part (b), calculate the following element of K:
2x5(x + 2)−3(2x + 1) + (2x + 2)4.
(d) Determine the minimal annihilating polynomial of a = 2x + 1 in the extension Z3 ⊆ K.
3. (15 marks) There are four people A,B,C,D in a room, and one of them is a foreign spy. Three of
the participants share a secret using Shamir’s scheme with a polynomial p(x) ∈ Z13. Any two of
them can recover the secret. The foreign spy chooses his share randomly, giving the following four
shares of the form (ai, p(ai)):
A : (2, 10), B : (4, 6), C : (8, 7), D : (11, 12).
Find out who is the foreign spy and calculate the secret.
4. (15=5+10 marks) Consider a linear secret sharing scheme for users U = {1, 2, 3, 4} defined by the
following matrix over a large finite field:
H =
h0
h1
h2
h3
h4
=
1 0 0
1 2 3
1 0 1
0 1 1
0 1 2
(a) The dealer randomly chooses the vector t =
21
3
in order to distribute the shares. What are
the shares dealt to each user? What is the secret?
(b) Find the access structure of this scheme.
MATHS 328 Assignment 4 Page 1 of 2
5. (10=2+4+4 marks)
(a) Consider the following binary vectors:
u = (0 0 1 0 1 0 1), v = (1 0 0 1 1 1 0).
Determine the Hamming weights of u, v, u+ v.
(b) Let u and v be binary vectors of length n with v = (1, 1, . . . , 1). Show that wt(u + v) =
n− wt(u).
(c) Let a be a word in Z72. How many elements are there in the ball B4(a) of radius 4?
6. (20=6+2+2+2+4+4) Let us consider a code C given by its parity check matrix
H =
0 1 1 1 0 0 1
0 1 0 1 0 1 1
0 0 1 1 1 0 1
1 1 1 1 1 1 0
.
(a) Compute the generator matrix for C. What is the number of information symbols for this
code? Encode the message vector whose coordinates are all equal to 1.
(b) Will the code C correct any single mistake? Give reasons
(c) Check that h1 + h7 = h4, where hi is the ith column of H. What are the implications of that
in relation to the ability of C to correct a pair of mistakes?
(d) Will the code C detect any two mistakes? Give reasons.
(e) Decode y1 = (1 0 1 1 0 0 1) and y2 = (1 0 1 1 0 1 0);
(f) Show that a single mistake could not result in receiving the vector y3 = (1 0 1 0 1 1 0). Show
that two mistakes could result in receiving y3.