What are known results regarding the distribution of the powers of a primitive element (generator of the multiplicative group) of a finite field? Specifically, compare the ordered list of ascending powers of the generator with the natural ordering of the field.

If it helps, this is for some research I am doing in cryptography, involving analysis of an algorithm that is dependent on the powers of a multiplicative generator of a finite field of order $2^n$. So I would be happy to see such theorems on just binary finite fields.

  • 1
    $\begingroup$ There is a (somewhat) naturalorder in fields of prime order; if the order is a prime power is there one too? $\endgroup$ – Mariano Suárez-Álvarez Feb 1 '13 at 6:51
  • $\begingroup$ In that case, once we choose a specific irreducible polynomial and take the quotient of the relevant polynomial ring, the natural order becomes clear. I should have said that for prime powers, we must fix what we are modding out by. $\endgroup$ – Favst Feb 2 '13 at 19:47

It is known that subgroups of the multiplicative group of a finite field (i.e. $k^{th}$ powers for some value of $k$ dividing $q-1$) look approximately like a random set in the additive group of the field. The machinery of Fourier analysis on finite abelian groups (in particular the theory of Gauss sums) can be used to make this precise.

The notes in this link might be of use: http://people.cs.uchicago.edu/~laci/reu02/fourier.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.