Free storage basis conversion over finite fields

Authors

ERSAN AKYILDIZ
NDANGANG YAMPA HAROLD
AHMET SINAK

Abstract

Representation of a field element plays a crucial role in the efficiency of field arithmetic. If an efficient representation of a field element in one basis exists, then field arithmetic in the hardware and/or software implementations becomes easy. Otherwise, a basis conversion to an efficient one is searched for easier arithmetic. However, this conversion often brings a storage problem for transition matrices associated with these bases. In this paper, we study this problem for conversion between normal and polynomial bases in the extension field $\mathbb{F}_{q^p}$ over $\mathbb{F}_q$ where $q=p^n$. We construct transition matrices that are of a special form. This provides free storage basis conversion algorithms between normal and polynomial bases, which is crucial from the implementation point of view.

DOI

10.3906/mat-1503-84

Keywords

Finite field representation, conversion of field elements, transition matrix, normal basis, polynomial basis

First Page

96

Last Page

109

Recommended Citation

AKYILDIZ, ERSAN; HAROLD, NDANGANG YAMPA; and SINAK, AHMET (2017) "Free storage basis conversion over finite fields," Turkish Journal of Mathematics: Vol. 41: No. 1, Article 10. https://doi.org/10.3906/mat-1503-84
Available at: https://journals.tubitak.gov.tr/math/vol41/iss1/10