First assume that $p$ is odd. Then we have the following

This is true because the roots of $X^{{p^{d}}}-X$ are exactly the elements of $\mathbb{F}_{{p^{d}}}$ and are all distinct in that field. So for any polynomial $T\in\mathbb{F}_{p}[X]$, the polynomial $T^{{p^{d}}}-T$ has also all elements of $\mathbb{F}_{{p^{d}}}$ as roots, so $X^{{p^{d}}}-X|T^{{p^{d}}}-T$. So as we have seen it is divisible by all irreducible polynomials of degree $d$, so it is divisible by $A$ since $A$ is squarefree. By noting that

is a decomposition with pairwise coprime factors, the claimed identity follows.

Now one can simply choose a random polynomial $T$ of degree less than $2d$. Then it is likely that $B:=\gcd(A,T^{\frac{p^{d}-1}{2}}-1)$ is a non-trivial divisor of $A$. We can then start over with $B$ and $A/B$ instead of $A$.

In this algorithm quite large powers of $T$ need to be computed. It is of course sufficient (and useful) to compute these powers modulo $A$, in order to keep the degree of the appearing polynomials low.

To illustrate this idea, we choose $d=1$. This means that $A$ is made up of different linear factors. Factorization is the achieved by finding zeroes. For this we could split $\mathbb{F}_{p}$ into three disjoint sets $M$, $N$ and $\{0\}$, such that $M\cup N\cup\{0\}=\mathbb{F}_{p}$.Then we construct the polynomial

Obvioulsy it is now sufficient to factor the polynomials $B:=\gcd(A,S)$ and $\frac{A}{B}$. If $M$ and $N$ were chosen wisely, these polynomials have lower degree than $A$. Now what is left is the choice of $M$ and $N$. For the start it might be a good idea to consider the set of quadratic residues in $\mathbb{F}_{p}$, so choosing

where $\left(\frac{x}{p}\right)$ denotes the Legendre symbol. This choice is almost what we want. It is known that $M$ and $N$ are now of equal size and also we know that

But if we want to apply the same method again to $B$ and $\frac{A}{B}$, we need some randomness. To achieve this, we simply do not consider the set of all quadratic residues, but the set

where $t\in\mathbb{F}_{p}$ is some random element. This gives us the polynomial

Actually we have now chosen a random monic polynomial $T$ of degree $1=2d-1$ and are reducing the problem of factoring $A$ to the problem of factoring $B:=\gcd(A,T^{\frac{p-1}{2}}-1)$ and $\frac{A}{B}$, as it was described above.

Let $p=2$. Lemma 1 does not work here because in the proof we use that

which requires $p$ to be odd. However we can find something similar:

This is because $(U\circ T)^{2}=T^{2}+T^{4}+\dots+T^{{2^{d}}}$, so

(we are in characteristic 2). Now this is a multiple of $A$ and the identity follows.

This gives us an algorithm for factorization of $A$ in the same way as above.