0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – reuns Jun 29 '17 at 18:54
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 1 '17 at 14:39
  • $\begingroup$ @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$. $\endgroup$ – user66307 Jul 1 '17 at 14:55
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How does one compute that cyclotomic polynomial? $\endgroup$ – user66307 Jul 1 '17 at 14:55
  • $\begingroup$ 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. $\endgroup$ – sharding4 Jul 1 '17 at 15:47

Your Answer

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