Free storage basis conversion over extension field

Download
2014
Harold, Ndangang Yampa
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.

Suggestions

On multiplication in finite fields
Cenk, Murat; Özbudak, Ferruh (2010-04-01)
We present a method for multiplication in finite fields which gives multiplication algorithms with improved or best known bilinear complexities for certain finite fields. Our method generalizes some earlier methods and combines them with the recently introduced complexity notion (M) over cap (q)(l), which denotes the minimum number of multiplications needed in F-q in order to obtain the coefficients of the product of two arbitrary l-term polynomials modulo x(l) in F-q[x]. We study our method for the finite ...
Efficient multiplications in F(5)5n and F(7)7n
Cenk, Murat; Özbudak, Ferruh (2011-08-15)
Efficient multiplications in finite fields of characteristics 5 and 7 are used for computing the Eta pairing over divisor class groups of the hyperelliptic curves Lee et al. (2008) [1]. In this paper, using the recent methods for multiplication in finite fields, the explicit formulas for multiplication in F(5)5n and F(7)7n are obtained with 10 multiplications in F(5)n for F(5)5n and 15 multiplications in F(7)n for F(7)7n improving the results in Cenk and Ozbudak (2008) [4], Cenk et al. (2009) [5], Lee et al...
Additive polynomials and primitive roots over finite fields
Özbudak, Ferruh (2001-01-01)
We prove existence of primitive roots with a prescribed nonzero image using the arithmetic of algebraic function fields for a class of polynomials over sufficiently large finite fields.
Character sums of quadratic forms over finite fields and the number of rational points for some classes of artin-schreier type curves
Coşgun, Ayhan; Doğanaksoy, Ali; Department of Mathematics (2017)
Exponential sums of quadratic forms over finite fields have many applications to various areas such as coding theory and cryptography. As an example to these applications, there is an organic connection between exponential sums of quadratic forms and the number of rational points of algebraic curves defined over finite fields. This connection is central in the application of algebraic geometry to coding theory and cryptography. In this thesis, different facts and techniques of theory of finite fields are co...
Storage free basis conversion over composite finite fields of odd characteristics
Sial, M Riaz; Akyıldız, Ersan (null; 2013-09-19)
We study the Finite Fields of type Fq, q = p2pn from the efficient implementation point of view. We found that we can represent these fields with irreducible polynomials in the form f(x) = xp − x − a. By using this representation we have found a way of constructing normal basis for the field, together with transmission matrix between normal basis and algebraic basis (Polynomial Basis) of Fq and vice versa. The key point is that this matrix and its inverse can be computed very efficiently without any memory ...
Citation Formats
N. Y. Harold, “Free storage basis conversion over extension field,” M.S. - Master of Science, Middle East Technical University, 2014.