For some reason I need some irreducible polynomial $f$ on $\mathbb{F}_{2}[x]$ where $\deg f \in [10^3,10^6]$. Could someone give information about this? Thx.

  • 1
    $\begingroup$ Are you just asking for one example? $\endgroup$ – Jason Starr Apr 11 '14 at 11:37
  • 6
    $\begingroup$ $x^{1001}+x^{17}+1$ $\endgroup$ – Felipe Voloch Apr 11 '14 at 12:21
  • $\begingroup$ To Jason Starr, the more, the better. $\endgroup$ – Lwins Apr 12 '14 at 0:14

You might take a look at the paper "A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377'' by Richard P. Brent, Samuli Larvala and Paul Zimmerman published in Mathematics of Computation in 2003 (pages 1443-1452) (I think the article is free online here). They give some specific examples of irreducible polynomials over $\mathbb{F}_{2}[x]$ of the form $x^{p} + x^{s} + 1$ for several prime numbers $p$ between $10^{5}$ and $10^{6}$. This is at the top end of the range you're looking for - they also have some references to older papers with smaller degree polynomials.


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.