Given a polynomials $f\in F_q[t]$ we want an algorithm that says if $f$ is irreducible or not.
In the book "Modern Computer Algebra" by von zur Gathen and Jürgen Gerhard, an algorithm for that is proposed (algorithm $14.36$). The issue is not with the algorithm itself, but with the implementation advices.
The book recommends us to compute $t^q\mod f$ as an auxiliary result, and then, use the fast modular composition algorithm to compute $t^{q^n}\mod f$ (being $n:=\deg(f)$), and, in general to compute $t^{q^{n/k}}\mod f$ (being $k$ a prime divisor of $n$).
I understand this recommendation as follows: Let $n=2^k+\sum_{i=0}^{k-1}n_i2^i$ be the binary representation of $n$ ($n_i\in\{0,1\}$) and $s_i:=x^{q^i}\mod f$.
It is clear that $$x^{q^n}\mod f = x^{q^{2^k+\sum_{i=0}^{k-1}n_i2^i}}\mod f=s_{2^k}(s_{\sum_{i=0}^{k-1}n_i2^i})\mod f=s_{2^k}(s_{n_{k-1}2^{k-1}}(\cdots(s_{n_0})\cdots))\mod f$$
So we will only need $\mathcal{O}(\log n)$ fast modular compositions to get the result.
I don't really get why this recommendations are useful, as we have to compute not only $x^q\mod f$, but also $x^{q^{2^i}}\mod f$ for some $i\in\{1,\dots,k\}$. Am I wrong?
Any idea?