Finite field arithmetic using quasi-normal bases

DOI10.1016/J.FFA.2006.09.008MaRDI QIDQ2370646zbMATH OpenOpenAlexFDO

Authors Christophe Negre

Publication date 29 June 2007

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ffa.2006.09.008

zbMATH Keywords

exponentiationfinite fieldmultiplicationnormal basis

Mathematics Subject Classification ID

Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30) Polynomials in general fields (irreducibility, etc.) (12E05) Field arithmetic (12E30)

Review text

Efficient multiplication in finite fields requires normal bases of low density: A basis \({\mathcal B}=\{\beta_1,\dots , \beta_n\}\) is called normal if it is fixed under Galois automorphisms. If we express the products \(\beta_i\beta_j\) with respect to the basis \({\mathcal B}\), then the density (sometimes also called complexity) measures the total number of nonzero coefficients in these expressions. Exponentiation is very easy if normal bases are used, and multiplication is rather easy if the density is small. It is well known that the finite field \({\mathbb F}_{q^n}\) is an \({\mathbb F}_q[x]\)-module. If \((n,q)=1\), we can write this module as a direct sum of irreducible submodules. Then all decompositions of \({\mathbb F}_{q^n}\) into submodules are easy to determine. The idea in the paper is to find ``normal bases for these submodules. A basis which is the union of such ``sub-bases is called quasi-normal. Exponentiation of field elements which are expressed with respect to quasi-normal bases is only slightly more complex than in the normal basis case. Therefore, quasi-normal bases of low density seem to be a good alternative to normal bases.

Recommendations

• Optimal normal bases in \(GF(p^ n)\)
• scientific article; zbMATH DE number 1273656
• Elliptic periods for finite fields
• Polynomial and normal bases for finite fields
• A new algorithm for multiplication in finite fields

Cites work

• A modified Massey-Omura parallel multiplier for a class of finite fields
• A public key cryptosystem and a signature scheme based on discrete logarithms
• An efficient optimal normal basis type II multiplier
• An implementation for a fast public-key cryptosystem
• Bit-serial Reed - Solomon encoders
• Density of normal elements
• Elliptic Curve Cryptosystems
• Elliptic curve cryptosystems over small fields of odd characteristic
• scientific article; zbMATH DE number 424718 (Why is no real title available?)
• scientific article; zbMATH DE number 3948147 (Why is no real title available?)
• scientific article; zbMATH DE number 2080690 (Why is no real title available?)
• scientific article; zbMATH DE number 1504805 (Why is no real title available?)
• Low complexity normal bases
• New directions in cryptography
• Optimal normal bases in \(GF(p^ n)\)

Cited in

(13)

• Artin-Schreier extensions of normal bases
• On finite field arithmetic in characteristic 2
• A new criterion on \(k\)-normal elements over finite fields
• Existence of primitive 2-normal elements in finite fields
• Existence and properties of \(k\)-normal elements over finite fields
• Polynomial and normal bases for finite fields
• A survey of some recent bit-parallel \(\mathrm{GF}(2^n)\) multipliers
• Elliptic periods for finite fields
• CONSTRUCTION OF POLYNOMIALS IRREDUCIBLE OVER A FINITE FIELD WITH LINEARLY INDEPENDENT ROOTS
• Direct hardware solution to quadratic equation Z2⊕Z⊕β=0 in Galois fields based on normal basis representation
• On the number of k-normal elements over finite fields
• Pairs of \(r\)-primitive and \(k\)-normal elements in finite fields
• r -primitive k -normal elements in arithmetic progressions over finite fields

This page was built for publication: Finite field arithmetic using quasi-normal bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370646)