Free storage basis conversion over extension field

Abstract

Sonlu cisim elamanların gösterimlermin sonlu cisim aritmetiğinin performansı üzerindeçok önemli bir etkisi vardır. Eğer sonlu cisim elamanlarının iyi bir gösterimivarsa ve gösterimler arası dönüşümler biliniyorsa, cisim üzerindeki aritmetik hesaplamalardaha hızlı ve verimli yapılabilir. Bu tezde, GF(q) uzerindeki GF(q^p) cisim genişlemesiüzerinde, Normal baz ve Polinom baz arasında iki taraflı serbest depolama baz dönüşümüçalışılmıştır. Bu dönüşümün özelliği, geçiş matrisinin özel bir formda olması ve girdilerinindepolanması için hafızaya ihtiyaç duyulmamasıdır. Ayrıca geçiş matrisinin tersitam olarak satırlarının permütasyonu alınarak elde edilir. Bu sebeple geçiş matrisinielde etme de kullanılan algoritmanın karma¸sıklığı ile bu matrisin tersini elde etmedekullanılan algoritmanın karmaşıklığı aynıdır.

The representation of elements over finite fields play a great impact on the performanceof finite field arithmetic. So if efficient representation of finite field elements exists andconversion between these representations is known, then it becomes easy to performcomputation in a more efficient way. In this thesis, we shall provide a free storagebasis conversion in the extension field GF(q^p) of GF(q) between Normal basis and Polynomialbasis and vice versa. The particularity of this thesis is that, our transition matrix is ofa special form and requires no memory to store its entries. Also the inverse of thetransition 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 andits inverse is the same.