Computational Problems over Finite Fields

这项研究致力于有限域上计算中的两个主要问题，即(A)因式分解问题和(B)大型线性方程组的求解问题。研究人员计划使用组合学、几何学和数论的工具，设计新的高效算法来分解单变量和多变量多项式。有限域上的大型线性方程组产生于高次多项式的因式分解以及其他几个重要的问题，包括有限域上的离散对数的计算、整数的因式分解以及代数或微分方程的求解。这些系统可以是稀疏的(显式给定)，也可以是密集的(隐式给定)。主要的焦点是用于求解这样的大型系统的有效的块算法。该项目的研究是在计算数学领域，并在数字通信中有应用。有限域是对象的有限集合，人们可以用与实数类似的方式执行加法、乘法和除法。不同之处在于，有限域运算根本不涉及舍入误差。正是这种重要的性质使得有限域对于编码(和隐藏)数字信息是有用的。事实上，几乎所有已知的纠错和数据安全编码方法都是基于有限域上的代数结构的。例如，美国数字签名标准(1998)是基于有限域运算的，而基于有限域的纠错码如今可以在几乎每个家庭(CD播放机)和太阳系外围(旅行者探测器)找到。该项目专注于有限域中的高效计算，并在编码理论、密码学和计算机科学中有重要的应用。

This research project is devoted to two major problems in computations over finite fields, namely the problems of (a) factoring polynomials and (b) solving large systems of linear equations. The investigator plans to design new efficient algorithms for factoring both univariate and multivariate polynomials, using tools from combinatorics, geometry, and number theory. Large systems of linear equations over finite fields arise in factoring polynomials of high degrees as well as in several other important problems including computing discrete logarithms in finite fields, factoring integers and solving algebraic or differential equations. These systems could be sparse (given explicitly) or dense (given implicitly). The main focus is on efficient block algorithms for solving such large systems. The research of the project is in the area of computational mathematics and has applications in digital communications. A finite field is a finite collection of objects where one can perform addition, multiplication and division in a similar fashion as for real numbers. The difference is that finite field operations involve no round-off errors at all. It is exactly this important property that makes finite fields useful for encoding (and hiding) digital information. In fact, almost all the known encoding methods for error correction and data security are based on algebraic structures over finite fields. For instance, the US Digital Signature Standard (1998) is based on finite field operations, while error correction codes based on finite fields can be found today in almost every household (CD players) and on the outskirts of the solar system (Voyager probe). This project focuses on efficient computations in finite fields and has important applications to coding theory, cryptography, and computer science.