Recently, I've been trying to implement the Cantor-Zassenhaus algorithm in C++ over $\mathbb{F}_2$. According to this lecture, the algorithm is basically:
Input is polynomial $f\in\mathbb{F}_q$ with degree $n=rd$ which has $r$ irreducible factors of degree $d$.
Generate a random polynomial $a$ with degree less than $n$.
Let $m=\frac{p^d-1}{2}$
Compute $a'=a^m+1$
If $gcd(a', f)\neq1$, then $gcd(a',f)$ is one of the factors.
Something I don't understand is, why is that particular value for $m$ chosen in the algorithm? Also, $p^d-1$ is not divisible by 2 when $p = 2$. So how could I modify the algorithm so that it still works for the $p = 2$ case?