Etd

 

Computation in Optimal Extension Fields Public

Downloadable Content

open in viewer

This thesis focuses on a class of Galois field used to achieve fast finite field arithmetic which we call Optimal Extension Fields (OEFs), first introduced in cite{baileypaar98}. We extend this work by presenting an adaptation of Itoh and Tsujii's algorithm for finite field inversion applied to OEFs. In particular, we use the facts that the action of the Frobenius map in $GF(p^m)$ can be computed with only $m-1$ subfield multiplications and that inverses in $GF(p)$ may be computed cheaply using known techniques. As a result, we show that one extension field inversion can be computed with a logarithmic number of extension field multiplications. In addition, we provide new variants of the Karatsuba-Ofman algorithm for extension field multiplication which give a performance increase. Further, we provide an OEF construction algorithm together with tables of Type I and Type II OEFs along with statistics on the number of pseudo-Mersenne primes and OEFs. We apply this new work to provide implementation results for elliptic curve cryptosystems on both DEC Alpha workstations and Pentium-class PCs. These results show that OEFs when used with our new inversion and multiplication algorithms provide a substantial performance increase over other reported methods.

Creator
Contributors
Degree
Unit
Publisher
Language
  • English
Identifier
  • etd-0428100-133037
Keyword
Advisor
Defense date
Year
  • 2000
Date created
  • 2000-04-28
Resource type
Rights statement
License

Relationships

In Collection:

Items

Permanent link to this page: https://digital.wpi.edu/show/mg74qm17c