Univariate Polynomial Decomposition And Matrix Multiplication Index Of Improvement In The Limited Domain

On one hand, we study asymptotically fast algorithm for factoring univariate polynomials over finite fields. We present a selective distinct-degree factorization algorithm, which produces three different complexitiy estimates by selecting different basic polynomial arithmetics. To factor a polynomial of degree n over Fq, the number of arithmetic operations in Fg isO(n1.8010111405662083logq) or O(n2+o(1) +n1+o(1) log q) or O(n (1,3/4,3/4)+ n1+o(1) logq), of which the first one is less by 0. 00433886 than the previous record.On the other hand, we study asymptotically fast algorithm for rectangular matrix multiplication. We propose a new conception: Index Distribution Chart, which makes it possible for us to construct a new fast multiplication algorithm for matrix pairs of arbitrary dimensions. For a large class of input matrix pairs, the algorithm improves the known exponents. It is just the improvement made in this domain that makes the improvement for factoring univariate polynomials over finite fields.In addition, this thesis is also a survey of the above two subjects.