Formulas for cube roots in \(\mathbb F_{3^m}\) (Q868380): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 15:13, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Formulas for cube roots in \(\mathbb F_{3^m}\) |
scientific article |
Statements
Formulas for cube roots in \(\mathbb F_{3^m}\) (English)
0 references
2 March 2007
0 references
The paper studies some properties of cube roots in a finite field of characteristic three. The authors argue the interest of characteristic three fields in pairing-based cryptographic protocols and they point out that ``the fastest algorithms known for pairing computations\dots requires the evaluation of cube roots in \(F_{3^m}\)''. Let \(F_{3^m}\) be represented as \(F_3(x)=F_3[X]/(f)\), with \(f(X)\in F_3[X]\) an irreducible trinomial. Expressing the elements of \(F_{3^m}\) in the polynomial basis \(\{1,x,\dots, x^{m-1}\}\), the computation of cube roots reduces to multiplications by \(x^{1/3}, x^{2/3}\). These multiplications would be more efficient if \(x^{1/3}, x^{2/3}\) have low Hamming weight. The paper determines the Hamming weight of \(x^{1/3}\). Let \(f(X)=X^m+aX^k+b\) be the irreducible trinomial. Section 2 deals with the case \(m\not \equiv -k \bmod 3\). Several theorems give the value \(w(x^{1/3})\) in terms of the congruences of \(m\) and \(k\) modulo 3. A similar study is accomplished in Section 3 when \(m\equiv -k \bmod 3\). Theorem 7 shows that in this case \(w(x^{1/3})\in \{(m/d)-2, (m/d)-1, m/d \}\), where \(d=\text{gcd} (m,k)\). The proof of this result is divided in three cases and it is accompanied with eight Tables. A further Table listing \(w(x^{1/3})\) for all irreducible trinomials of degrees \(m\in [2,56]\) is given as an Appendix.
0 references
cube roots
0 references
finite field arithmetic
0 references
characteristic three
0 references
Hamming weigth
0 references
trinomials
0 references