Finite fields, Cryptography, Coding theory, Commutative algebra, Symbolic computation, Quantum computation and Algorithmic number theory
A New Framework for Computing Grobner Bases (with Frank Volny IV and Mingsheng Wang) Mathematics of Computation, 85:449--465, 2016.
ABSTRACT: This paper presents a new framework for computing Gröbner bases for ideals and syzygy modules. It is proposed to work in a module that accommodates any given ideal and the corresponding syzygy module (for the given generators of the ideal). A strong Gröbner basis for this module contains Gröbner bases for both the ideal and the syzygy module. The main result is a simple characterization of strong Gröbner bases. This characterization can detect useless S-polynomials without reductions, thus yields an efficient algorithm. It also explains all the rewritten rules used in F5 and the recent papers in the literature. Rigorous proofs are given for the correctness and finite termination of the algorithm. For any term order for an ideal, one may vary signature orders (i.e. the term orders for the syzygy module). It is shown by computer experiments on benchmark examples that signature orders based on weighted terms are much better than other signature orders. This is useful for practical computation. Also, since computing Gröbner bases for syzygies is a main computational task for free resolutions in commutative algebra, the algorithm of this paper should be useful for computing free resolutions in practice.
Factoring multivariate polynomials via partial differential equations Mathematics of Computation, 72:801--822, February 2003.
ABSTRACT: A new method is presented for factorization of bivariate polynomials
over any field of characteristic zero or of relatively large characteristic. It
is based on a simple partial differential equation that gives a system of linear
equations. As in Berlekamp’s and Niederreiter’s algorithms for factoring univariate
polynomials, the dimension of the solution space of the linear system
is equal to the number of absolutely irreducible factors of the polynomial to
be factored, and any basis for the solution space gives a complete factorization
by computing gcd’s and by factoring univariate polynomials over the ground
field. The new method finds absolute and rational factorizations simultaneously
and is easy to implement for finite fields, local fields, number fields, and
the complex number field. The theory of the new method allows an effective
Hilbert irreducibility theorem, thus an efficient reduction of polynomials from
multivariate to bivariate.
Optimal normal bases (with Hendrik W. Lenstra, Jr.) Designs, Codes and Cryptography, 2:315-323, 1992.
ABSTRACT: Let K ⊂ L be a finite Galois extension of fields, of degree n. Let G be the Galois group, and let (<α)<∈G be a normal basis for L over K. An argument due to Mullin, Onyszchuk, Vanstone and Wilson (Discrete Appl. Math. 22 (1988/89), 149–161) shows that the matrix that describes the map x → αx on this basis has at least 2n - 1 nonzero entries. If it contains exactly 2n - 1 nonzero entries, then the normal basis is said to be optimal. In the present paper we determine all optimal normal bases. In the case that K is finite our result confirms a conjecture that was made by Mullin et al. on the basis of a computer search.
MATH 3110 - Linear Algebra
Introduction to the
algebra of matrices, vector spaces, polynomials, and
linear transformations. Includes Honors sections.