On the arithmetic operations over finite fields of characteristic three with low complexity
Finite fields of sizes \(3^n\) have recently been used for cyptographic purposes, where the field operations need to be implemented efficiently. The most important such operation is multiplication, which can be split into polynomial multiplication and reduction modulo a generating polynomial. The number of nonzero coefficients of this generating polynomial should be as small as possible, since this determines the efficiency of reduction. This article begins with details of representing finite fields of characteristic 3 using Hermite polynomials. The explicit simple form of the Hermite polynomials in \({\mathbb F}_{3}\) is derived. A formula for the result of polynomial multiplication of two Hermite polynomials is given and calculations with polynomials of 2,3 and 4 terms are carried out explicitly. In theorem 2, the authors state the complexity of multiplication and addition when the Hermite polynomial representation and a divide-and-conquer idea are used. The authors derive the form of sums of two Hermite polynomials which can be irreducible for certain degrees and which have the smallest reduction complexity. Then a comparison of these sums as reduction polynomial with the irreducible polynomial \(f(x) = x^n + x^2 + 2\) is made. In theorem 3, the authors give the number of additions and scalar multiplications of reduction modulo such a sum of two Hermite polynomials. These numbers are compared to the numbers which arise when the standard polynomial is used. Finally, the authors discuss the product of two polynomials expressed as matrix vector product, again in the context of Hermite polynomial representation in \({\mathbb F}_{3}\).
- scientific article; zbMATH DE number 1979307
- Efficient Multiplication in $\mathbb{F}_{3^{\ell m}}$ , m ≥ 1 and 5 ≤ ℓ ≤ 18
- Polynomial Multiplication over Binary Fields Using Charlier Polynomial Representation with Low Space Complexity
- On multiplication in finite fields
- On hardware and software implementation of arithmetic in finite fields of characteristic 7 for calculation of pairings
- Batch Binary Edwards
- Bit-parallel finite field multiplier and squarer using polynomial basis
- Comments on "A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Field"
- Efficient \(p\)th root computations in finite fields of characteristic \(p\)
- Elliptic periods for finite fields
- Finding optimal formulae for bilinear maps
- Handbook of Elliptic and Hyperelliptic Curve Cryptography
- scientific article; zbMATH DE number 1349933 (Why is no real title available?)
- scientific article; zbMATH DE number 1942431 (Why is no real title available?)
- scientific article; zbMATH DE number 1979307 (Why is no real title available?)
- Low Complexity Cubing and Cube Root Computation over $\F_{3^m}$ in Polynomial Basis
- Modified Redundant Representation for Designing Arithmetic Circuits with Small Complexity
- On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields
- Polynomial basis multiplication over \(\text{GF}(2^m)\)
- Software Implementation of Finite Fields of Characteristic Three, for Use in Pairing-based Cryptosystems
- The combinatorics of associated Hermite polynomials
- The Magma algebra system. I: The user language
This page was built for publication: On the arithmetic operations over finite fields of characteristic three with low complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2349632)
