Polynomial , where each is divisible by some number , is irreducible in when does not divide .
If A is not irreducible then there are some and such as .
But that means that , which means that XOR (since does not divide ).
Let’s assume that . Now let’s take a map (I believe this method is called homomorphism-reduction).
, but , where .
That is possible only when is constant and . Which means that is irreducible.
Note: here denotes where is a homomorphism .