Constructing high order elements through subspace polynomials
Qi Jin Cheng, Shuhong Gao, Daqing Wan · 2012
Every finite field has many multiplicative generators. However, finding one in polynomial time is an important open problem. In fact, even finding elements of high order has not been solved satisfactorily. In this paper, we present an algorithm that for any positive integer c and prime power q, finding an element of order in the finite field in deterministic time (qc)O(1). We also show that there are many weak keys for the discrete logarithm problems in those fields with respect to certain bases.