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 .