Given the polynomials $f,g,h\in A[t]$ such that $\deg(h),\deg(g)<\deg(f)=n$ where $f\not=0$ is monic and $A$ is a commutative ring with unity, the problem is to compute the polynomial $g(h)\mod{f}$.
In the book "Modern Computer Algebra" by von zur Gathen and Jürgen Gerhard, an algorithm for that is proposed (algorithm $12.3$)
The last step of the algorithm consists on computing the polynomial $\sum_{i=0}^{m-1}r_i(h^m)^i\mod{f}$.
where $r_i$ are some polynomials involving $g$ and $h$ and $m:=\lceil n^{1/2}\rceil$.
The issue with that is that the book recomends to do that with the help of the Horner's rule, and I really don't know how Horner's rule can be applied here, as we are not evaluating a polynomial and in general $\deg f\not=1$.
Any idea?
It looks to me like you are evaluating a polynomial here, just at another polynomial!
If $\sum_{i=0}^{m-1} r_i Y^i$ is a polynomial that we are "evaluating" at $h^m$ then we can do this as written with around $m^2$ polynomial multiplications, assuming $h^m$ is already computed (by binary powering maybe). But writing it as $\sum_{i=0}^{m-1} r_i Y^i = Y(Y(\cdots Y(Y(r_{m-1}) + r_{m-1}) + \cdots) + r_1) + r_0$ we have only $m$ polynomial multiplications when $h^m$ (which is computed in advance) is substituted for $Y$.
Side note: Horner's method also saves a constant factor of 2 vs. computing $\sum_{i=0}^{m-1} r_i Y^i$ from the degree 0 term upwards, saving each $Y^i$ as you go, here two multiplications are needed for each index $i$, one to find $Y^i$ from $Y^{i-1}$ and $Y$ and one to multiply by the coefficient $r_i$.