h（x）= x2 + xx3-x-1

Toeplitz矩阵A∈Fn×n是一个矩阵，其条目沿对角线是恒定的，例如：

A =（321432543）

（f0，…，fn-1）↦（f（α0），…，f（αn-1））？

## Required Exercises

`Remember that you are only required to turn in 5 out of the 6 exercises below.`

### Problem 1 – Fast Modular Composition (20 points)

Let g=h=x3+2×2+3x+4 and f=x4−1 be polynomials over F5[x]. Use the fast modular composition algorithm to compute g(h)modf.

### Problem 2 – proving that ωdet=ωmult (20 points)

Given a matrix A∈FN×N where N=2k, prove that one can compute det(A) in time O(nω), where ω is the matrix multiplication exponent. You can assume that any matrix that you need to invert in the process is invertible.

Optional question: how would you remove the assumption given above?

### Problem 3 – linear recurrence relations and minimal polynomials (20 points)

1. Determine a recurrence relation and sufficiently many initial values of the sequence (ai)i∈N∈QN if h(x)=∑i≥0aixi is

h(x)=x2+xx3−x−1

1. Compute the minimal polynomial of the sequence 1,3,4,7,11,18,29,47,… of rational numbers, given that the recursion order is at most 4. Give the next 5 elements of the sequence.

### Problem 4 – using linear recurrent relations to decide singularity (20 points)

Let A∈Qn×n be a square matrix. Give a probabilistic “black box” algorithm which performs at most O(c(A)⋅n+n2) field operations and decides whether A is singular. Your algorithm should return the correct answer with probability at least 2/3.

### Problem 5 – Toeplitz matrices (20 points)

Toeplitz matrix A∈Fn×n is a matrix whose entries are constant along the diagonals, for instance:

A=(321432543)

1. Prove that you can multiply an n×n Toeplitz matrix by an n×1 vector in O(M(n)) operations, where recall that M(n) is the number of operations needed to multiply two polynomials of degree ≤n.
2. Prove that given β∈F, you can compute β0,β1,β4,β9,…,β(n−1)2 in O(n) operations in F.

Hint: think of (i+1)2−i2

1. Given a polynomial f(x)∈F[x] with degree <n, and α∈F, let us now see how to compute f(α0),f(α1),…,f(αn−1), assuming that we know β∈F such that β2=α (that is, a square root of α).

Let f(x)=f0+f1x+…+fn−1xn−1 What is the matrix of the operation

(f0,…,fn−1)↦(f(α0),…,f(αn−1))?

Describe this matrix by showing what the (i,j) entry of this matrix is.

1. Using the fact that ij=(i+j)2−i2−j22, rewrite the matrix from the previous part as a product of 3 matrices, involving a particular Toepliz matrix.

Suggestion: write this down for n=3 first

1. Show that you can compute f(α0),f(α1),…,f(αn−1) in O(M(n)) operations.