Constructing Elements of Large Order in Finite Fields

摘要

An efficient algorithm is presented which for any finite field F_q of small characteristic finds an extension F_(q~s) of polynomially bounded degree and an element α ∈ F_(q~s) of exponentially large multiplicative order. The construction makes use of certain analogues of Gauss periods of a special type. This can be considered as another step towards solving the celebrated problem of finding primitive roots in finite fields efficiently.