We do not give here a proof and we refer to Theorem 9.5 in [vzGG99]. However, roughly speaking, Algorithm 7 consists essentially in

*c*multiplications (where*c*is a constant) to compute*g*(by virtue of Theorem 9),- one multiplication to compute
*q*, - one multiplication to compute
*r*.

If several divisions by a given *b* needs to be performed
then we may precompute the inverse of
*rev*_{m}(*b*)
modulo some powers
*x*, *x*^{2},... of *x*.
Assuming that *R* possesses suitable primitive roots of unity,
ee can also save their DTF.

2004-04-27