Practical fast algorithm for finite field arithmetics using group rings (Q1766193): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Normalize DOI. |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Juan G. Tena Ayuso / rank | |||
Property / reviewed by | |||
Property / reviewed by: Juan G. Tena Ayuso / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: NTL / 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.32917/hmj/1150998162 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1510999608 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q128870958 / rank | |||
Normal rank | |||
Property / DOI | |||
Property / DOI: 10.32917/HMJ/1150998162 / rank | |||
Normal rank |
Latest revision as of 19:42, 30 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Practical fast algorithm for finite field arithmetics using group rings |
scientific article |
Statements
Practical fast algorithm for finite field arithmetics using group rings (English)
0 references
28 February 2005
0 references
Computations in large finite fields, common in Cryptography or Computer Algebra, demand algorithms able to efficiently perform the arithmetic operations of multiplication, power and inversion. Such algorithms depend strongly on the representation of the field elements or equivalently on the choice of basis in a field extension \(\mathbb F_{q^d}| \mathbb F_q\): polynomial, normal, etc. Depending on the operations to perform, the field size, the characteristic of the field or the type of implementation one algorithm or another can be more advantageous. For instance using a normal basis the computation of the Frobenius (\(q\)th power operation) has negligible cost. \textit{S. Gao} et al. [J. Symb. Comput. 29, 879--889 (2000; Zbl 0997.11112)] proposed a method based on the representation of \(\mathbb F_{q^d}\) as a subring of a certain group ring. The present paper gives a software implementation of this idea. Section 2 of the paper studies a modified version of the construction of Gao et al. where \(\mathbb F_{q^d}\)\, is represented as a quotient of the cyclic group ring \(\mathbb F_q[t]/(t^m-1)\), (with \(m\) the multiplicative order of a generator of \(\mathbb F_{q^d}\) over \(\mathbb F_q\)). The operations are then computed in this group ring using the polynomial basis \(\{t^i \mid i=0,\dots, m-1\}\). Details of the software implementation are given in Section 3 and in Section 4 the authors compare the speed of their method (implemented in C and only for \(p=q\), and \(d=m-1\), i.e. \(q\) a generator of \((\mathbb{Z}/(d+1))^{*}\)) with that of the NTL method (Number Theory Library, http://shoup.net/ntl). The tables provided give a sample of numeric results showing that for \(p=q>2\) the running time of the new method is better than that of NTL. The drawback is that for \(p=q=2\)\, the situation is reverse.
0 references
finite fields
0 references
algorithms
0 references
running time
0 references