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.