Practical fast algorithm for finite field arithmetics using group rings
Makoto Matsumoto, Shigehiro Tagami · Hiroshima Mathematical Journal · 2004
This paper studies a fast algorithm for finite field arithmetics, by repre- senting a finite field as a residue of a group ring of a finite cyclic group, where the frobenius (q-th power) operation is e‰ciently computable. When the characteristic of the field is greater than 2, our algorithm is often much faster than a standard method (NTL) in computing inverse and power. For example, ours is roughly 23.6 times faster in computing power in F8191136 than NTL. The implementation contains a new scheme for computing powers, which is applicable for any group if the q-th power operation is negligibly fast.