Practical fast algorithm for finite field arithmetics using group rings (Q1766193)

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.