\myheading{Factorize GF(2)/CRC polynomials}

\leveldown{}

GF(2)/CRC polynomials, like usual numbers, can also be factored, because a polynomial can be a product of two other polynomial (or not).

Some people say that good CRC polynomial should be irreducible (i.e., cannot be factored), some other say that this is not a requirement.
I've checked several CRC-16 and CRC-32 polynomials from \href{https://en.wikipedia.org/wiki/Cyclic_redundancy_check}{the Wikipedia article}.

% TODO \ref{}
The multiplier is constructed in the same manner, as I did it earlier for integer factorization using SAT.
Factors are not prime integers, but prime polynomials.

Another important thing to notice is that replacing XOR with addition will make this script factor integers, because addition in GF(2) is XOR.

Also, can be used for tests, online GF(2) polynomials factorization: \url{http://www.ee.unb.ca/cgi-bin/tervo/factor.pl?binary=101}.

\lstinputlisting[style=custompy, caption=For Z3]{CRC/factor/gf2_factor_z3.py}

See also almost the same solution for my SAT library: \url{\RepoURL/CRC/factor/gf2_factor_SAT.py}

% TODO: style for Bash:
\lstinputlisting[caption=Test]{CRC/factor/gf2_factor_tests.sh}

\lstinputlisting[caption=Results]{CRC/factor/tests.txt}

\myheading{SageMath}

... but.

SageMath can do this way more quickly, and can factor 64-bit polynomials on which my solution stuck.
Also, it can factor 128-bit polynomial used in AES-GCM, with no effort.

\url{\RepoURL/CRC/factor/sagemath/check_irreducible.html}.

(SageMath notebooks I used: \url{\RepoURL/CRC/factor/sagemath/}.)

Alas!
This is a professional mathematical tool.
It probably uses a specially tailored algorithm, which may be way more complex.

Yet again, I wrote my tool for SAT/SMT with no special knowledge, as a newbie.
And it was fun and it helped me to learn Galois fields.

\levelup{}