Subquadratic-time algorithms for normal bases

Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30) Number-theoretic algorithms; complexity (11Y16) Computational methods for problems pertaining to field theory (12-08) Separable extensions, Galois theory (12F10) Randomized algorithms (68W20)

Abstract: For any finite Galois field extension

m a t h s f K / m a t h s f F

, with Galois group

G = m a t h r m G a l (m a t h s f K / m a t h s f F)

, there exists an element

a l p h a i n m a t h s f K

whose orbit

G c d o t a l p h a

forms an

m a t h s f F

-basis of

m a t h s f K

. Such a

a l p h a

is called a normal element and

G c d o t a l p h a

is a normal basis. We introduce a probabilistic algorithm for testing whether a given

a l p h a i n m a t h s f K

is normal, when

G

is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether

a l p h a

is normal can be reduced to deciding whether

s u m_{g i n G} g (a l p h a) g i n m a t h s f K [G]

is invertible; it requires a slightly subquadratic number of operations. Once we know that

a l p h a

is normal, we show how to perform conversions between the power basis of

m a t h s f K / m a t h s f F

and the normal basis with the same asymptotic cost.

Review text

In a finite Galois extension \(K/F\) with Galois group \(G=\mathrm{Gal}(K/F)\), an element \(\alpha\in K\) is called \textit{normal} if its Galois orbit \(\alpha^G\) forms an \(L\)-basis of \(K\). Under the assumption that \(K\) is represented \(K=L(\xi)\) with a power basis \(1,\xi,\xi^2,\ldots\), and the elements of \(G\) are given through their action on \(\xi\), and that \(G\) is abelian or metacyclic, the authors give a Monte-Carlo algorithm to test whether a particular element \(\alpha\in K\) is normal. This algorithm runs in time \(\tilde{\mathcal O}(n^e)\) for \(e<1.99\). (The soft-O notation \(\tilde{\mathcal O}\) leaves out logarithmic factors.) The concrete value for \(e\) is \(3/4\cdot\omega(3/4)\), where \(\omega(3/4)\) stems from the cost of multiplying by a \(n\times n^{3/4}\) matrix. This extends their prior result [\textit{M. Giesbrecht} et al., in: Proceedings of the 44th international symposium on symbolic and algebraic computation, ISSAC '19, Beijing, China, July 15--18, 2019. New York, NY: Association for Computing Machinery (ACM), 179--186 (2019; Zbl 1467.11124)] from abelian to metabelian Galois groups. They also show that they can perform basis conversion between the power basis and \(\alpha^G\) in the same (Monte-Carlo) complexity.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Subquadratic-time algorithms for normal bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040602)