本次加拿大数学代写主要是完成代数多项式计算

问题1-快速模块化组合(20分)

令g = h = x3 + 2×2 + 3x + 4和f = x4-1是F5 [x]上的多项式。使用快速模块化合成算法来计算g(h)modf。

问题2-证明ωdet=ωmult(20分)

给定一个矩阵A∈FN×N,其中N = 2k,证明可以在时间O(nω)上计算det(A),其中ω是矩阵乘法指数。您可以假定您需要在过程中求逆的任何矩阵都是可逆的。

可选问题:如何删除上面给出的假设?

问题3-线性递归关系和最小多项式(20分)
如果h(x)= ∑i≥0aixi是,则确定序列的递归关系和足够多的初始值(ai)i∈N∈QN

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

给定递归顺序最多为4,计算有理数序列1、3、4、7、11、18、29、47等的最小多项式。给定序列的下5个元素。
问题4-使用线性递归关系确定奇点(20分)

设A∈Qn×n为方阵。给出一个概率“黑盒”算法,该算法最多执行O(c(A)⋅n+ n2)个场运算,并确定A是否为奇数。您的算法应以至少2/3的概率返回正确的答案。

问题5-Toeplitz矩阵(20分)

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

A =(321432543)

证明您可以在O(M(n))运算中将n×n Toeplitz矩阵乘以n×1向量,其中回想M(n)是将两个≤n的多项式相乘所需的运算数。

证明给定β∈F,您可以在F的O(n)运算中计算β0,β1,β4,β9,…,β(n-1)2。

提示:想想(i + 1)2-i2

给定度数<n和α∈F的多项式f(x)∈F[x],现在让我们看看如何计算f(α0),f(α1),…,f(αn-1)我们知道β∈F使得β2=α(即α的平方根)。

设f(x)= f0 + f1x + … + fn-1xn-1

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

通过显示此矩阵的(i,j)项来描述此矩阵。

利用ij =(i + j)2-i2-j22的事实,将前一部分的矩阵重写为3个矩阵的乘积,涉及特定的Toepliz矩阵。

建议:先写下n = 3

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.