Computations in finite fields and probabilistic analysis of algorithms

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

The overall area of my research is the design and analysis of algorithms. My recent research has centered around two lines: the investigation of algorithms in finite fields and their applications in modern communication areas, and the study of algorithms when randomness is considered. A main area of my research involves computations in finite fields and their applications. Algorithms that work with finite fields play a crucial role in innumerous practical applications in communications, cryptography, coding theory and information theory. My goal in this area is the design of efficient algorithms in finite fields, and the usage of elements from the theory of finite fields in engineering applications. Examples are efficient implementation of arithmetic using polynomials and normal elements, and constructions of certain types of polynomials over finite fields (irreducible, primitive, among others). The main applications of these studies are in cryptography, with other areas including codes and combinatorial constructions. My second line of research is the probabilistic analysis of algorithms that comprises the study of algorithms when randomness is used. In particular, average-case analysis of algorithms focuses on understanding the behaviour of algorithms on random inputs. An essential goal of the area is to advance in the understanding of randomness. Immediate goals are better understanding of particular algorithms, and the development of new efficient algorithms based on this knowledge. The scientific approach is based on mathematical proofs involving generating functions for counting the properties of interest for the analysis of the algorithms, and asymptotic analysis. My goal in this area is two-fold: to develop algorithms for fundamental problems like searching with better performance than previously known algorithms, and to contribute to the mathematical understanding of random polynomials over finite fields.