1
$\begingroup$

For some reason I need some primitive polynomial $f$ on $\mathbb{F}_2[x]$ where $\deg f \in [1,10^4]$. (Especially for $\deg f = 10\pm \epsilon, 10^2\pm \epsilon, 10^3\pm \epsilon, 10^4 \pm \epsilon$.) Could someone give information about this? For example, a table or some references are helpful. Thx.

Edit: If $2^{\deg f} - 1 \in \mathbb{P}$ we have that an irreducible polynomial $f$ is primitive immediately. However assuredly primitive polynomial exists for all $\deg f \in \mathbb{Z}^+ $.

$\endgroup$
4
  • $\begingroup$ Is "primitive polynomial" the same as an irreducible polynomial? $\endgroup$ Apr 20, 2014 at 3:32
  • $\begingroup$ To Greg, if $2^{\deg f}-1 \in \mathbb{P}$, then you are right. Or see this: en.wikipedia.org/wiki/Primitive_polynomial_(field_theory) $\endgroup$
    – Lwins
    Apr 20, 2014 at 4:09
  • $\begingroup$ But if $\deg f$ is a power of $10$ then $2^{\deg f} - 1$ is not prime. The factorization is known for $10$, $10^2$, and $10^3$ (see the table at members.iinet.net.au/~tmorrow/mathematics/cunningham/…), but I don't know whether $10^4$ is at all feasible, and that's the main hurdle to finding a provably primitive polynomial of degree $10^4$. $\endgroup$ Apr 20, 2014 at 4:38
  • 1
    $\begingroup$ Ok, I see. So $x^4+x^3+x^2+x+1$ is an example of an irreducible polynomial over $\Bbb F_2$ that is not primitive. $\endgroup$ Apr 20, 2014 at 5:39

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.