Free storage basis conversion over extension field

Thesis Type: Postgraduate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Institute of Applied Mathematics, Turkey

Approval Date: 2014




The representation of elements over finite fields play a great impact on the performance of finite field arithmetic. So if efficient representation of finite field elements exists and conversion between these representations is known, then it becomes easy to perform computation in a more efficient way. In this thesis, we shall provide a free storage basis conversion in the extension field F_(q^p) of F_q between Normal basis and Polynomial basis and vice versa. The particularity of this thesis is that, our transition matrix is of a special form and requires no memory to store its entries. Also the inverse of the transition matrix is obtained just by permuting the row entries of the transition matrix. Therefore the complexity of the algorithm for obtaining both the transition matrix and its inverse is the same.