Abstract: First, a proof of the equivalence is presented among the q-polynomials, matrices of order n and linear functions over finite fields. And then based on the observation that one linear function will have distinct matrix forms under different bases, a generic scheme is extended to determine the relationship between the linear functions and matrices of order n over a finite field quickly. As another important contribution, a new scheme is also designed to determine their linear relation, with the advantage of full generality over available schemes. Finaly the essential reason why the algebraic expression for the Rijndael S-box is so simple is given.

Key words: AES, Rijndael, S-box, finite field, q-polynomial