Applications of the representation of finite fields by matrices (Q1575722)

Let \(q\) be a prime power, \(F_q\) the finite field of order \(q\), \(d\) a divisor of \(q-1\), and \(a\) a \(d\)th power in \(F_q\). The authors describe an elegant probabilistic algorithm to solve the equation \(x^d=a\) in \(F_q\) using the matrix representation of \(F_{q^d}\): Find (probabilistically) an irreducible polynomial \(P\) of degree \(d\) over \(F_q\) with constant coefficient \((-1)^da\) and compute \[ A^{(q^d-1)/(d(q-1))}=xI, \] where \(A\) is the companion matrix of \(P\). The algorithm finds a solution of \(x^d=a\) in an expected number of O\((d\log q)\) operations in \(F_q[A]\).