0

How would you find primitive elements of the finite field $\mathbb{F}_{2^c}$ for arbitrary integer $c\geq 1$? Is there some general way of doing this? I in fact only want to find one for each $c$ if there happens to be one that is simple to compute.

  • You mean (for each $n$ odd) finding a primitive polynomial $f_n(x)$ whose root is $\zeta_{2^n-1}$ and $\mathbf{F}{2^n} = \mathbf{F}_2[x]/(f_n(x))$. In that case if $gcd(n,m)=1$ then $\mathbf{F}{2^{nm}} = \mathbf{F}2[x,y]/(f_n(x),f_m(y))$ from which you can find the minimal polynomial of $\zeta{2^{nm}-1}$, so it reduces to $n = p^k$ – reuns Jun 29 '17 at 18:54
  • How is your field given? How large is $c$? If $c$ is at most a couple dozen I use a table of primitive polynomials to define the field (when a primitive elements comes free of charge). If $c$ is in the hundreds, then I don't know. As I use a primitive element for building discrete log tables and such, I don't recall ever having wanted to find one. Anyway, if you are given the field using some known irreducible polynomial, and know the factorization of $2^c-1$, then IIRC there are algorithms for this. – Jyrki Lahtonen Jul 01 '17 at 14:39
  • @JyrkiLahtonen $c$ is arbitrarily large. I am looking for an algorithm whose running time can be given as a function of the number of bits needed to represent the field element and the value $c$. I am assuming the field element is just given as a polynomial of degree $c$. –  Jul 01 '17 at 14:55

1 Answers1

0

If you don't require a specific element or polynomial to generate the field you could look at the $(2^{c}-1)^{st}$ cyclotomic polynomial over $\Bbb{F}_2$. Any of its roots should be a primitive root of 1 and generate the multiplicative group of the field with $2^c$ elements.

sharding4
  • 4,917
  • How does one compute that cyclotomic polynomial? –  Jul 01 '17 at 14:55
  • Naively you can factor $x^n-1$ into irreducible factors. Wikipedia and Mathworld give properties that can help to compute the $n^{th}$ cyclotomic polynomial over $\Bbb{Q}$. The polynomial would still need to be factored into irreducibles over $\Bbb{F}_2$ There are probably optimized algorithms in the texts on Computational ANT by Cohen or Pohhst-Zassenhaus. GP/Pari will return the cyclotomic polynomials up to $2^{17}-1$ almost instantaneously. – sharding4 Jul 01 '17 at 15:47