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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
LiTH-ISY-Ex, 3402
Keyword [en]
Datorteknik, Finite Field, Multiplication, Complexity, Polynomial Bases, Normal Bases, Triangular Bases, Multiples.
Keyword [sv]
Datorteknik
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:liu:diva-1968OAI: oai:DiVA.org:liu-1968DiVA: diva2:19295
Uppsok
teknik
Available from: 2003-10-21 Created: 2003-10-21

Open Access in DiVA

fulltext(1704 kB)430 downloads
File information
File name FULLTEXT01.pdfFile size 1704 kBChecksum MD5
04506dfc436ab439e631122e8d9707d4dc2d50eca5da6352a008416089af6c81da1a4305
Type fulltextMimetype application/pdf

By organisation
Department of Electrical Engineering
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 430 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

urn-nbn

Altmetric score

urn-nbn
Total: 4490 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf