Subquadratic-time factoring of polynomials over finite fields

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree over a finite field of constant cardinality in time . Previous algorithms required time . The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree over the finite field with elements, the algorithms use arithmetic operations in .

The new ``baby step/giant step' techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields.

     

An algebraic foundation for factoring linear boundary problems

Motivated by boundary problems for linear differential equations, we define an abstract boundary problem as a pair consisting of a surjective linear map (“differential operator”) and an orthogonally closed subspace of the dual space (“boundary conditions”). Defining the composition of boundary problems corresponding to their Green’s operators in reverse order, we characterize and construct all factorizations of a boundary problem from a given factorization of the defining operator. For the case of ordinary differential equations, the main results can be made algorithmic. We conclude with a factorization of a boundary problem for the wave equation. This work was supported by the Austrian Science Fund (FWF) under the SFB grant F1322.     

An efficient algorithm for the multivariable Adomian polynomials

In this article the sum of the series of multivariable Adomian polynomials is demonstrated to be identical to a rearrangement of the multivariable Taylor expansion of an analytic function of the decomposition series of solutions u₁, u₂, … , u_m about the initial solution components u_1,0, u_2,0, … , u_m,0; of course the multivariable Adomian polynomials were developed and are eminently practical for the solution of coupled nonlinear differential equations. The index matrices and their simplified forms of the multivariable Adomian polynomials are introduced. We obtain the recurrence relations for the simplified index matrices, which provide a convenient algorithm for rapid generation of the multivariable Adomian polynomials. Another alternative algorithm for term recurrence is established. In these algorithms recurrence processes do not require complicated operations such as parametrization, expanding and regrouping, derivatives, etc. as practiced in prior art. The MATHEMATICA program generating the Adomian polynomials based on the algorithm in this article is designed.     

Algorithm of polynomial complexity for factoring polynomials over local fields

An algorithm is obtained for factoring polynomials in several variables over local fields with complexity which is polynomial in the length of notation of the input data and the characteristic of the residue field of the local field. Here by definition we assume that an infinite series can be calculated in polynomial time if its i-th partial sum can be calculated in time which is polynomial in the length of notation of the input data and i for any i.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 112–148, 1991.     

An algebraic structure for Faber polynomials

Let Σ be the set of functions, convergent for all |z|>1, with a Laurent series of the form f(z)=z+∑_n?0a_nz^-n. In this paper, we prove that the set of Faber polynomial sequences over Σ and the set of their normalized kth derivative sequences form groups which are isomorphic to the hitting time subgroup and the Bell^(k) subgroup of the Riordan group, respectively. Further, a relationship between such Faber polynomial sequences and Lucas and Sheffer polynomial sequences is derived.     

Permutation polynomials over algebraic number fields

Let K be an algebraic number field. It is known that any polynomial which induces a permutation on infinitely many residue class fields of K is a composition of cyclic and Chebyshev polynomials. This paper deals with the problem of deciding, for a given K, which compositions of cyclic or Chebyshev polynomials have this property. The problem is reduced to the case where K is an Abelian extension of $\text{Q}$. Then the question is settled for polynomials of prime degree, and the Abelian case for composite degree polynomials is considered. Finally, various special cases are dealt with.     

Cubic polynomials over algebraic number fields

We prove that every cubic form in 16 variables over an algebraic number field represents zero, generalizing the corresponding result of Davenport for cubic forms over the rationals. (This has already been proved for cubic forms in 17 or more variables by Ryavec.) We present this result as a special case of a “local-implies-global” theorem for cubic polynomials.     

An extremal problem for real algebraic polynomials

Let G _n be the set of all real algebraic polynomials of degree at most n, positive on the interval (?1, 1) and without zeros inside the unit circle (|z| < 1). In this paper an inequality for the polynomials from the set G _n is obtained. In one special case this inequality is reduced to the inequality given by B. Sendov [5] and in another special case it is reduced to an inequality between uniform norm and norm in the L ₂ space for the Jacobi weight.     

An efficient algorithm for range computation of polynomials using the Bernstein form

We present a novel optimization algorithm for computing the ranges of multivariate polynomials using the Bernstein polynomial approach. The proposed algorithm incorporates four accelerating devices, namely the cut-off test, the simplified vertex test, the monotonicity test, and the concavity test, and also possess many new features, such as, the generalized matrix method for Bernstein coefficient computation, a new subdivision direction selection rule and a new subdivision point selection rule. The features and capabilities of the proposed algorithm are compared with those of other optimization techniques: interval global optimization, the filled function method, a global optimization method for imprecise problems, and a hybrid approach combining simulated annealing, tabu search and a descent method. The superiority of the proposed method over the latter methods is illustrated by numerical experiments and qualitative comparisons.     

An efficient algorithm for maximum entropy extension of block-circulant covariance matrices

This paper deals with maximum entropy completion of partially specified block-circulant matrices. Since positive definite symmetric circulants happen to be covariance matrices of stationary periodic processes, in particular of stationary reciprocal processes, this problem has applications in signal processing, in particular to image modeling. In fact it is strictly related to maximum likelihood estimation of bilateral AR-type representations of acausal signals subject to certain conditional independence constraints. The maximum entropy completion problem for block-circulant matrices has recently been solved by the authors, although leaving open the problem of an efficient computation of the solution. In this paper, we provide an efficient algorithm for computing its solution which compares very favorably with existing algorithms designed for positive definite matrix extension problems. The proposed algorithm benefits from the analysis of the relationship between our problem and the band-extension problem for block-Toeplitz matrices also developed in this paper.     

The best extension of algebraic polynomials from the unit circle

We study the class $ \mathfrak{P}_n $ \mathfrak{P}_n of algebraic polynomials P _n (x, y) in two variables of total degree n whose uniform norm on the unit circle Γ₁ centered at the origin is at most 1: $ \left\| {P_n } \right\|_{C(\Gamma _1 )} $ \left\| {P_n } \right\|_{C(\Gamma _1 )} ≤ 1. The extension of polynomials from the class $ \mathfrak{P}_n $ \mathfrak{P}_n to the plane with the least uniform norm on the concentric circle Γ _r of radius r is investigated. It is proved that the values θ _n (r) of the best extension of the class $ \mathfrak{P}_n $ \mathfrak{P}_n satisfy the equalities θ _n (r) = r ⁿ for r > 1 and θ _n (r) = r ⁿ⁻¹ for 0 < r < 1.     

An algebraic approach to Lidstone polynomials

A new definition of Lidstone polynomials [G.L. Lidstone, Note on the extension of Aitken’s theorem (for polynomial interpolation) to the Everett types, Proc. Edinb. Math. Soc. 2 (2) (1929) 16–19] is proposed; this is a Hessemberg determinantal form. The algebraic approach provides an elementary proof of the main recursive properties of Lidstone polynomials.     

The best extension of algebraic polynomials from the unit circle

We study the class \(\mathfrak{P}_n \) of algebraic polynomials P _n (x, y) in two variables of total degree n whose uniform norm on the unit circle Γ₁ centered at the origin is at most 1: \(\left\| {P_n } \right\|_{C(\Gamma _1 )} \) ≤ 1. The extension of polynomials from the class \(\mathfrak{P}_n \) to the plane with the least uniform norm on the concentric circle Γ _r of radius r is investigated. It is proved that the values θ _n (r) of the best extension of the class \(\mathfrak{P}_n \) satisfy the equalities θ _n (r) = r ⁿ for r > 1 and θ _n (r) = r ^n?1 for 0 < r < 1.     

Factorization of polynomials over a finite field and the solution of systems of algebraic equations

An algorithm is constructed for factoring polynomials in several variables over a finite field, which works in polynomial time in the size of the polynomial and q. Previously this result was known in the case of one variable. An algorithm is given for the solution (over the algebraic closure F of the field F) of systems of algebraic equations, where with working time of order where L is the size of a representative of the original system, is the degree of transcendence of the field F over the prime subfield, q=char(F). Previously the estimate was known for =0.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 20–79, 1984.     

An algorithm for the divisors of monic polynomials over a commutative ring

Gilmer and Heinzer proved that given a reduced ring R, a polynomial f divides a monic polynomial in R[X] if and only if there exists a direct sum decomposition of R = R₀ ⊕ … ⊕ R_m (m ≤ deg f), associated to a fundamental system of idempotents e₀, … , e_m, such that the component of f in each R_i[X] has degree coefficient which is a unit of R_i. We propose to give an algorithm to explicitly find such a decomposition. Moreover, we extend this result to divisors of doubly monic Laurent polynomials.