Item – Theses Canada

​
OCLC number
429724836
Link(s) to full text
LAC copy
LAC copy
Author
Ahmadi Darvishvand, Omran,1975-
Title
Distribution of irreducible polynomials over finite fields.
Degree
Ph. D. -- University of Waterloo, 2006
Publisher
Ottawa : Library and Archives Canada = Bibliothèque et Archives Canada, 2007.
Description
2 microfiches
Notes
Includes bibliographical references.
Abstract
Finite fields play an important role in the implementation of public-key cryptosystems, and consequently there is much interest in their efficient implementation. It is well known that the implementation of the arithmetic of finite fields greatly depends on their representation, which in turn depends on the existence of irreducible polynomials of special forms. There are an abundant number of related open problems about the distribution of irreducible polynomials over finite fields. In this thesis we make progress towards resolving some of these outstanding questions, and in the process discover some new scenarios in which one can exploit the representation of finite fields to yield faster implementations. In the first part of the thesis we show how a properly chosen irreducible polynomial can be used to faster compute the trace of an element in finite fields of characteristic two or take cube roots in finite fields of characteristic three. In the second part of the thesis we focus on the study of irreducible polynomials. We derive necessary conditions for the irreducibility of some polynomials and show that some of these polynomials are suitable for implementation purposes. The polynomials considered include self-reciprocal, maximum weight and trinomials. We also present some constructive results which can be used to obtain new irreducible polynomials of special forms from the given ones. Along the way we prove a conjecture of von zur Gathen regarding irreducible trinomials over <math> <f> <blkbd>F<inf><rm>3</rm></inf></blkbd></f> </math> and a conjecture of Mullen and Yucas about the non-existence of self-reciprocal irreducible pentanomials over <math> <f> <blkbd>F<inf><rm>2</rm></inf></blkbd></f> </math>. Finally we give partial answers to some of the conjectures posed in the first part of the thesis about the trace spectra of polynomial bases for <math> <f> <blkbd>F<inf><rm>2<mit>n</mit></rm></inf></blkbd></f> </math>.
ISBN
9780494236727
0494236728