liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Computational Complexity of Finite Field Multiplication
Linköping University, Department of Electrical Engineering.
2003 (English)Independent thesis Basic level (professional degree)Student thesisAlternative title
Beräkningskomplexitet för multiplikation i ändliga kroppar (Swedish)
Abstract [en]

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.
LiTH-ISY-Ex, 3402
Keyword [en]
Datorteknik, Finite Field, Multiplication, Complexity, Polynomial Bases, Normal Bases, Triangular Bases, Multiples.
Keyword [sv]
National Category
Computer Engineering
URN: urn:nbn:se:liu:diva-1968OAI: diva2:19295
Available from: 2003-10-21 Created: 2003-10-21

Open Access in DiVA

fulltext(1704 kB)416 downloads
File information
File name FULLTEXT01.pdfFile size 1704 kBChecksum SHA-1
Type fulltextMimetype application/pdf

By organisation
Department of Electrical Engineering
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 416 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 4431 hits
ReferencesLink to record
Permanent link

Direct link