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.     

On arithmetical algorithms over finite fields

Standard methods for calculating over GF(pⁿ), the finite field of pⁿ elements, require an irreducible polynomial of degree n with coefficients in GF(p). Such a polynomial is usually obtained by choosing it randomly and then verifying that it is irreducible, using a probabilistic algorithm. If it is not, the procedure is repeated. Here we given an explicit basis, with multiplication table, for the fields GF(p^pk), for k = 0, 1, 2,…, and their union. This leads to efficient computational methods, not requiring the preliminary calculation of irreducible polynomials over finite fields and, at the same time, yields a simple recursive formula for irreducible polynomials which generate the fields. The fast Fourier transform (FFT) is a method for efficiently evaluating (or interpolating) a polynomial of degree < n at all of the nth roots of unity, i.e., on the finite multiplicate subgroups of F, in O(nlogn) operations in the underlying field. We give an analogue of the fast Fourier transform which efficiently evaluates a polynomial on some of the additive subgroups ofF. This yields new “fast” algorithms for polynomial computation.     

Factoring polynomials over finite fields

We propose a new deterministic method of factoring polynomials over finite fields. Assuming the generalized Riemann hypothesis (GRH), we obtain, in polynomial time, the factorization of any polynomial with a bounded number of irreducible factors. Other consequences include a polynomial time algorithm to find a nontrivial factor of any completely splitting even-degree polynomial when a quadratic nonresidue in the field is given.     

Generators for cubic surfaces with two skew lines over finite fields

Let S be a smooth cubic surface defined over a field K. As observed by Segre [5] and Manin [3, 4], there is a secant and tangent process on S that generates new K-rational points from old ones. It is natural to ask for the size of a minimal generating set for S(K). In a recent paper, for fields K with at least 13 elements, Siksek [7] showed that if S contains a skew pair of K-lines, then S(K) can be generated from one point. In this paper we prove the corresponding version of this result for fields K having at least 4 elements, and slightly milder results for # K = 2 or 3.     

Deciding finiteness for matrix groups over function fields

LetF be a field andt an indeterminate. In this paper we consider aspects of the problem of deciding if a finitely generated subgroup of GL(n,F(t)) is finite. WhenF is a number field, the analysis may be easily reduced to deciding finiteness for subgroups of GL(n,F), for which the results of [1] can be applied. WhenF is a finite field, the situation is more subtle. In this case our main results are a structure theorem generalizing a theorem of Weil and upper bounds on the size of a finite subgroup generated by a fixed number of generators with examples of constructions almost achieving the bounds. We use these results to then give exponential deterministic algorithms for deciding finiteness as well as some preliminary results towards more efficient randomized algorithms. Supported in part by NSF DMS Awards 9404275 and Presidential Faculty Fellowship.     

Explicit bounds of polynomial coefficients and counting points on Picard curves over finite fields

In this paper, we describe an algorithm for computing the order of the Jacobian varieties of Picard curves over finite fields. This is an extension of the algorithm of Matsuo, Chao and Tsujii (MCT) [K. Matsuo, J. Chao, S. Tsujii, An improved baby step algorithm for point counting of hyperelliptic curves over finite fields, in: LNCS vol. 2369, Springer-Verlag, 2005, pp. 461–474] for hyperelliptic curves. We study the characteristic polynomials and the Jacobian varieties of algebraic curves of genus three over finite fields. Based on this, we investigate the explicit computable bounds for coefficients of the characteristic polynomial and improve a part of the baby-step giant-step of the counting points algorithm. Usefulness of the proposed method is illustrated and verified by the simple examples.     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

Testing low‐degree polynomials over prime fields

We present an efficient randomized algorithm to test if a given function f : ?? → ??_p (where p is a prime) is a low‐degree polynomial. This gives a local test for Generalized Reed‐Muller codes over prime fields. For a given integer t and a given real ε > 0, the algorithm queries f at O( ) points to determine whether f can be described by a polynomial of degree at most t. If f is indeed a polynomial of degree at most t, our algorithm always accepts, and if f has a relative distance at least ε from every degree t polynomial, then our algorithm rejects f with probability at least . Our result is almost optimal since any such algorithm must query f on at least points. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Moment subset sums over finite fields

The k-subset sum problem over finite fields is a classical NP-complete problem. Motivated by coding theory applications, a more complex problem is the higher m-th moment k-subset sum problem over finite fields. We show that there is a deterministic polynomial time algorithm for the m-th moment k-subset sum problem over finite fields for each fixed m when the evaluation set is the image set of a monomial or Dickson polynomial of any degree n. In the classical case $m=1$, this recovers previous results of Nguyen-Wang (the case $m=1,p>2$) [22] and the results of Choe-Choe (the case $m=1,p=2$) [3].     

Hilbert's Tenth Problem for fields of rational functions over finite fields

Summary We prove that there is no algorithm to solve arbitrary polynomial equations over a field of rational functions in one letter with constants in a finite field of characteristic other than 2 and hence, Hilbert's Tenth Problem for any such field is undecidable.Oblatum 1-XI-1989Supported in part by NSF Grant DMS 8605198.     

A classification of Minkowski planes over half-ordered fields

This paper concerns a construction of Minkowski planes over half-ordered fields [5] and [20]. Solving various functional equations the Klein-Kroll types of these Minkowski planes are determined with respect toG- andq-translations and (p, q)-homotheties. Examples for some of the resulting types are given.     

Effective construction of an algebraic variety nonsingular in codimension one over a ground field of zero characteristic

Let k be a field of zero characteristic finitely generated over a primitive subfield. Let f be a polynomial of degree at most d in n variables, with coefficients from k, irreducible over an algebraic closure [`(k)] \bar{k} . Then we construct an algebraic variety V nonsingular in codimension one and a finite birational isomorphism V → Z(f), where Z(f) is the hypersurface of all common zeros of the polynomial f in the affine space. The running time of the algorithm for constructing V is polynomial in the size of the input. Bibliography: 8 titles.     

Writing representations over minimal fields

The chief aim of this paper is to describe a procedure which, given a d-dimensional absolutely irreducible matrix representation of a finite group over a finite field E, produces an equivalent representation such that all matrix entries lie in a subfield F of E which is as small as possible. The algorithm relies on a matrix version of Hilbert's Theorem 90, and is probabilistic with expected running time O(|E:F|d³) when |F| is bounded. Using similar methods we then describe an algorithm which takes as input a prime number and a power-conjugate presentation for a finite soluble group, and as output produces a full set of absolutely irreducible representations of the group over fields whose characteristic is the specified prime, each representation being written over its minimal field.     

Sums of units in function fields

Let R be the ring of S-integers of an algebraic function field (in one variable) over a perfect field, where S is finite and not empty. It is shown that for every positive integer N there exist elements of R that can not be written as a sum of at most N units. Moreover, all quadratic global function fields whose rings of integers are generated by their units are determined.     

Witt equivalence of function fields of curves over local fields

Two fields are Witt equivalent if their Witt rings of symmetric bilinear forms are isomorphic. Witt equivalent fields can be understood to be fields having the same quadratic form theory. The behavior of finite fields, local fields, global fields, as well as function fields of curves defined over Archimedean local fields under Witt equivalence is well understood. Numbers of classes of Witt equivalent fields with finite numbers of square classes are also known in some cases. Witt equivalence of general function fields over global fields was studied in the earlier work [13 G?adki, P., Marshall, M. Witt equivalence of function fields over global fields. Trans. Am. Math. Soc., electronically published on April 11, 2017, doi: https://doi.org/10.1090/tran/6898 (to appear in print).[Crossref] , [Google Scholar]] by the authors and applied to study Witt equivalence of function fields of curves over global fields. In this paper, we extend these results to local case, i.e. we discuss Witt equivalence of function fields of curves over local fields. As an application, we show that, modulo some additional assumptions, Witt equivalence of two such function fields implies Witt equivalence of underlying local fields.     

Ergodicity of certain cylinder flows

Here we build on the result given in [P1] and extend those in [HL2] to functions which arek times differentiable a.e.,k>1. For eachk we give a class of irrational numbersS _k such that the skew product extension defined by these functions is ergodic for irrational rotations by these numbers. In the second part of this paper we examine the cohomology of functions over the adding machine transformation, and produce extensions of results from [H1] and [HL3]. Supported by SERC Grant No. 85318881 and ARC Grant No. 150325.     

Exponential sums over definable subsets of finite fields

We prove some general estimates for exponential sums over subsets of finite fields which are definable in the language of rings. This generalizes both the classical exponential sum estimates of varieties of finite fields due to Weil, Deligne and others, and the result of Chatzidakis, van den Dries and Macintyre concerning the number of points of those definable sets. As a first application, there is no formula in the language of rings that defines for infinitely many primes an “interval” in Z/p Z that is neither bounded nor with bounded complement.     

On coefficients of polynomials over finite fields

In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations.