1
$\begingroup$

Is there any (fast) algorithm that produces irreducible polynomials over $\mathbb{F}_2$?

EDIT: I look up for a irreducible polynomial generator, that is different from decider algorithm for irreducibility.

EDIT2: By Input $n \in \mathbb{N}$ to the algorithm $A$ we expect $n$ irreducible polynomials over $\mathbb{F}_2$. I need that $A$ always returns same result by a specific input $n$ (I don't want random irr. polynomials generator).

$\endgroup$
4
  • $\begingroup$ Here: $x$ is an irreducible polynomial over $\mathbb{F}_2$. Please review How to Ask. Give more detail as to what is actually to be done by "any (fast) algorithm". $\endgroup$
    – hardmath
    Nov 14, 2015 at 19:03
  • 1
    $\begingroup$ There are some families of polynomials over $\Bbb{F}_2$ that are known to consist entirely of irreducible ones. See this thread. In general producing them is about as difficult (or easy) as producing prime numbers. Pavel Yudaev describes below the equivalent of the sieve of Eratosthenes. I'm not sure that this is what you wanted. May be you need to build a database of such polynomials? If you use these tricks you will often (but not always) get six irreducible polynomials for the price of one. $\endgroup$
    – Jyrki Lahtonen
    Nov 14, 2015 at 21:35
  • 1
    $\begingroup$ Oh. And if you want irreducible polynomials of a certain degree $m$, you can try Berlekamp on $x^{2^m}+x$ :-) $\endgroup$
    – Jyrki Lahtonen
    Nov 14, 2015 at 21:42
  • $\begingroup$ @JyrkiLahtonen Thanks for links. $\endgroup$
    – user0
    Nov 15, 2015 at 5:03

1 Answer 1

Reset to default
1
$\begingroup$

A) If you come across an algorithm that produces minimal polynomials, it will fit. I am not aware of such an algo.

B) Nor sure how fast the following is...

1) $x^2 + x + 1$ is the only irreducible poly of $deg=2$
2) $x^3 + x + 1$ and $x^3 + x^2 + 1$ - all irreducible of $deg=3$
3) for any (next) degree $k$, pick a poly $f$ of degree $k$, try to divide it by $x$, $x+1$ and all irreducible of degree up to $[k/2]$. If no divisor is found, $f$ is irreducible.
4) For your algo to produce the same result, return the first $n$ irreducible polys (of low degrees).

$\endgroup$
3
  • $\begingroup$ The idea of computing the minimal polynomial of a binary matrix is a reasonable idea. It can be carried out in polynomial complexity. The OP seems not to have in mind to specify the degree of an irreducible polynomial but rather a quantity of polynomials to be produced. $\endgroup$
    – hardmath
    Nov 14, 2015 at 23:30
  • $\begingroup$ @hardmath If the OP does not specify the degree, he can pick any degree. Could you elaborate on the idea of computing the minimal polynomial of a binary matrix? I am interested. $\endgroup$
    – Jantar88
    Nov 15, 2015 at 8:16
  • $\begingroup$ Computing the minimal polynomial will only help "randomize" a source of polynomials. It doesn't guarantee irreducibility, so we still need either to find an irreducible factor (or test/reject the sample and try again). However we can compute the minimal polynomial of a binary matrix in polynomial time by looking for linear dependence among "flattened rows" that represent the powers $I,A,A^2,\ldots$. If this is of interest, I will elaborate. $\endgroup$
    – hardmath
    Nov 15, 2015 at 12:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .