§1.IntroductionLet Fqdenote the finite field with q=pmelements,wherep is a prime.A polynomial f(x)inFqis called a permutation polynomial if f(x)=a has a solution in Fqfor every a in Fq.Many studieshave been made ...§1.IntroductionLet Fqdenote the finite field with q=pmelements,wherep is a prime.A polynomial f(x)inFqis called a permutation polynomial if f(x)=a has a solution in Fqfor every a in Fq.Many studieshave been made to develop properties of permutation polynomials.For a survey of the work on thissubject prior to 1920 we refer to Dickson.During this period it was Dickson himself who展开更多
We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve th...We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n 2 + n 1+o(1)logq) to O(n 1.9998 + n 1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m 1.575 n) to O(m 1.5356 n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.展开更多
文摘§1.IntroductionLet Fqdenote the finite field with q=pmelements,wherep is a prime.A polynomial f(x)inFqis called a permutation polynomial if f(x)=a has a solution in Fqfor every a in Fq.Many studieshave been made to develop properties of permutation polynomials.For a survey of the work on thissubject prior to 1920 we refer to Dickson.During this period it was Dickson himself who
文摘We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n 2 + n 1+o(1)logq) to O(n 1.9998 + n 1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m 1.575 n) to O(m 1.5356 n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.
