Computational Problems over Finite Fields

点击翻译按钮获取中文摘要

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.