Polynomial basis multiplication over \(\text{GF}(2^m)\) (Q850783): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Structure of parallel multipliers for a class of fields \(GF(2^ m)\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Montgomery multiplication in \(\text{GF}(2^ k)\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4301239 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4718481 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mastrovito multiplier for all trinomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Low complexity bit-parallel multipliers for a class of finite fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Montgomery multiplier and squarer for a class of finite fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bit-parallel finite field multiplier and squarer using polynomial basis / rank | |||
Normal rank |
Latest revision as of 22:45, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Polynomial basis multiplication over \(\text{GF}(2^m)\) |
scientific article |
Statements
Polynomial basis multiplication over \(\text{GF}(2^m)\) (English)
0 references
6 November 2006
0 references
The purpose of this survey is, in the authors' words, ``to describe, analyze and compare various \(\text{GF}(2^m)\) multipliers''. Efficient hardware and software implementations of the multiplication in binary finite fields \(\text{GF}(2^m)\), with \(m\) large, are crucial in applications such as Cryptography. The authors argue that ``multiplication methods that use polynomial base representations are very efficient in comparison to the best methods using other basis representations''. Section 2 of the paper introduces to the problem of polynomial basis multiplication of two \(\text{GF}(2^m)\) elements and its two main stages: multiplication of two degree \(m-1\) polynomials \(a(x), b(x)\) and reduction of the product \(d(x)\) modulo the degree \(m\) irreducible polynomial \(\omega(x)\) defining \(\text{GF}(2^m)\), to obtain a field element \(c(x)\). In Section 3 the authors calculate the space and time complexity of these two arithmetic operations. Particular attention is paid to the cases \(\omega(x)\) an equally spaced polynomial and \(\omega(x)\) an \(r\)-nomial, cases that provide better complexity in the modular reduction. Section 4 of the paper reviews the matrix vector product techniques. An approach is to reduce the polynomial \(d(x)\) using an \((m \times m-1)\) reduction matrix, defined in terms of \(\omega(x)\). A second approach is to simultaneously perform the polynomial multiplication and the reduction operation using the so-called (\(m\times m\)) Mastrovito matrix, whose entries are function of the coefficients of \(\omega(x)\) and the polynomial \(a(x)\) (the multiplicand), see [\textit{E. D. Mastrovito}, Applied algebra, algebraic algorithms and error-correcting codes, Proc. 6th Int. Conference, AAECC-6, Rome/Italy 1988, Lect. Notes Comput. Sci. 297--309 (1988; Zbl 0673.94024)]. Tables with complexities for both techniques are provided. Finally the Montgomery multiplication method is explained in Section 5. The Montgomery multiplication [see \textit{C. K. Koc} and \textit{T. Acar}, Des. Codes Cryptogr. 14, No. 1, 57--69 (1998; Zbl 0887.11054)] calculates \(c(x)=a(x)b(x)r(x)^{-1} \bmod \omega(x)\), where \(r(x)\) is a fixed polynomial (Koc and Acar take \(r=x^m\)). The special case where \(\omega(x)\) is an irreducible trinomial gives good space and time complexity.
0 references
finite fields
0 references
binary fields
0 references
polynomial basis
0 references
modular multiplication
0 references
matrix reduction
0 references
Montgomery multiplication
0 references