Results on the multiplication in finite fields of characteristic three using modified polynomial representation and normal elements in binary fields

Abstract

Bu tezde, karakteristiği üç olan sonlu cisimlerdeki çarpma üzerinde çalışıyoruz. Standart polinom gösterimine alternatif gösterimler elde etmek için, F^3n deki elemanları göstermede Charlier ve Hermite polinomlarını kullanıyoruz. F^3n deki elemanları çarpmak için bu gösterimlerdekiçarpma yöntemlerini veriyoruz. Her bir gösterimde, çarpma ve indirgeme karmaşıklıklarınıhesaplıyoruz ve karmaşıklık sonuçlarını standart polinom gösterimiyle karşılaştırıyoruz. Charlierve Hermite polinom gösterimleri indirgenemez iki terimli polinomlar bulabilmemize olanaksağlamaktadır. Bazı durumlarda, standart polinom gösterimine göre daha az toplama karmaşıklığıolan modüler indirgeme elde etmek için her bir gösterimde indirgenemez iki terimli polinomlarkümesi olduğunu gösteriyoruz. Charlier polinom gösteriminde bir çarpan yapısı ve küp alma işlemini veriyoruz. Hermite polinom gösteriminde cisim elemanlarının çarpımı için matris-vektör çarpım yöntemini inceliyoruz ve bu matris-vektör çarpım yönteminde indirgeme matrisini kullanarak indirgeme karmaşıklığını genelleştiriyoruz. Son olarak, ikilikcisimlerde optimal normal tabanların oluşturulmasına odaklanıyoruz ve bu cisimlerde, optimalnormal taban elemanları ve Hermite polinomları arasında bir bağlantı buluyoruz.

In this thesis, we study on the multiplication in finite fields of characteristic three. We use Charlier and Hermite polynomials to represent elements in F^3n for obtaining alternative representations to the standart polynomial representation. We give multiplication methods in these representations to multiply elements in F^3n. We compute the multiplication and reduction complexities in each representation and compare the complexity results with the ones in thestandart polynomial representation. Charlier and Hermite polynomial representations enable us to find irreducible binomials. We show that in some cases, there is a set of irreducible binomials in each representation to do modular reduction with lower addition complexity than the one in the standart polynomial representation. We give a multiplier architecture in Charlier polynomial representation of finite fields F^3n, where n=2 (mod 3). Then, we examine cubingand inversion operations in this representation. We investigate the matrix-vector product method for multiplication of the field elements in Hermite polynomial representation and we generalize the reduction complexity by using the reduction matrix in this matrix-vector product method. Finally, we focus on the optimal normal basis construction in binary fields and find a connection between optimal normal basis elements and Hermite polynomials in these fields.