Title page for ETD etd-0428100-133037

Document Type thesis

Author Name Bailey, Daniel V

URN etd-0428100-133037

Title Computation in Optimal Extension Fields

Degree MS

Department Computer Science

Advisors
Christof Paar, Advisor
Gabor Sarkozy, Reader

Keywords
finite fields
cryptography
implementation

Date of Presentation/Defense 2000-04-26

Availability unrestricted

Abstract
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.

Files
bailey.pdf

Browse by Author | Browse by Department | Search all available ETDs

Questions? Email etd-questions@wpi.edu
Maintained by webmaster@wpi.edu

Document Type	thesis
Author Name	Bailey, Daniel V
URN	etd-0428100-133037
Title	Computation in Optimal Extension Fields
Degree	MS
Department	Computer Science
Advisors	Christof Paar, Advisor Gabor Sarkozy, Reader
Keywords	finite fields cryptography implementation
Date of Presentation/Defense	2000-04-26
Availability	unrestricted
Abstract 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.
Files	bailey.pdf