Is there some fast way to determine whether a polynomial divides another in $\mathbb{Z}_2$? Is there some fast way to factor polynomials in $\mathbb{Z}_2$ into irreducible polynomials?
Is there a fast way to find $n$ such that a given polynomial in $\mathbb{Z}_2$ divides $x^n-1$?
Could there be a strategy/checklist to check this as fast as possible?
Please help me.
To check for divisibility is easy: since $\mathbb Z_2$ is a discrete valuation ring, for any two polynomials $f, g$, $f$ divides $g$ iff it divides it over the fraction field $\mathbb Q_2$ and the content of $f$ divides the content of $g$. Testing this is just Euclidean division, which is “fast” enough by any definition.
To factor into irreducibles, you first want to write the Newton polygon of your polynomial; this gives you a first factorization (by Hensel's lemma). Each segment of this polynomial, however, gives you a product of irreducibles; factoring this is then equivalent to factoring over the residue field $\mathbb F_2$. (This is the case of a horizontal segment of the Newton polygon; you can bring a non-horizontal segment to this case by substituting $x \leftarrow c x$, where $c$ has the appropriate valuation).
In total, full factorization over $\mathbb Z_2$ should be at most cubic, which is still probably reasonably fast.