Computational Complexity of Finite Field Multiplication
Independent thesis Basic level (professional degree)Student thesisAlternative title
Beräkningskomplexitet för multiplikation i ändliga kroppar (Swedish)
The subject for this thesis is to find a basis which minimizes the number of bit operations involved in a finite field multiplication. The number of bases of a finite field increases quickly with the extension degree, and it is therefore important to find efficient search algorithms. Only fields of characteristic two are considered.
A complexity measure is introduced, in order to compare bases. Different methods and algorithms are tried out, limiting the search in order to explore larger fields. The concept of equivalent bases is introduced.
A comparison is also made between the Polynomial, Normal and Triangular Bases, referred to as known bases, as they are commonly used in implementations. Tables of the best found known bases for all fields up to GF(2^24) is presented.
A list of the best found bases for all fields up to GF(2^25) is also given.
Place, publisher, year, edition, pages
Institutionen för systemteknik , 2003. , 105 p.
Datorteknik, Finite Field, Multiplication, Complexity, Polynomial Bases, Normal Bases, Triangular Bases, Multiples.
IdentifiersURN: urn:nbn:se:liu:diva-1968OAI: oai:DiVA.org:liu-1968DiVA: diva2:19295