Algorithms for Computing in Finite Fields

Greg Stein, New York City College of Technology

This project involved the development and implementation of algorithms related to the problem of efficiently performing computations over finite fields, especially those with large characteristics. There exist techniques linking the factorization of cyclotomic polynomials to computing traces of roots of unity (Gauss Sums) over finite fields. Previous algorithms have been constructed to create solutions for each of these problems, given the solution of the other, by working in a quotient of a multivariate polynomial ring isomorphic to the Berlekamp subalgebra as well as various other algorithmic solutions developed for the project. Software was then developed to implement existing algorithms. The software generalizes the existing algorithms to work with arbitrary polynomials over arbitrary finite fields. The two programs were designed to assist in the investigation of a basic problem in mathematics; that of factoring cyclomatic polynomials over finite fields in a time polynomial, in the degree of the polynomial, and the logarithm of the characteristic of the field.

Education - This is a contributing Drupal Theme
Design by WeebPal.