Computations in finite fields and probabilistic analysis of algorithms

有限域计算和算法的概率分析

• 批准号: 238757-2013
• 负责人: Panario, Daniel
• 金额: $ 2.62万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570486
• 关键词: Computations; finite; fields; probabilistic; analysis

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.

我研究的总体领域是算法的设计和分析。我最近的研究集中在两条线上：有限域的算法研究及其在现代通信领域的应用，以及考虑随机性时的算法研究。