Formulas for cube roots in \(\mathbb F_{3^m}\) (Q868380): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
ReferenceBot (talk | contribs)
Changed an Item
 
(5 intermediate revisions by 4 users not shown)
Property / author
 
Property / author: Alfred J. Menezes / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Juan G. Tena Ayuso / rank
Normal rank
 
Property / author
 
Property / author: Alfred J. Menezes / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Juan G. Tena Ayuso / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.dam.2006.06.004 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1981209126 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4409129 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Advances in Cryptology - ASIACRYPT 2003 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4737495 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial and normal bases for finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hardware Acceleration of the Tate Pairing in Characteristic Three / rank
 
Normal rank
Property / cites work
 
Property / cites work: Software Implementation of Finite Fields of Characteristic Three, for Use in Pairing-based Cryptosystems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient Hardware for the Tate Pairing Calculation in Characteristic Three / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3136478 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4425740 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 14:25, 25 June 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
    0 references
    0 references
    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

    Identifiers