Быстрое параллельное вычисление степеней в факторкольце многочленов над конечным полем

Показывается, что вычисление степеней в фактор-кольце многочленов от одной переменной над конечным полем сводится к умножению матриц над этим полем, и на основе этого доказывается следующая оценка сложности: если $F=GF(q)$, $\omega(F)$ – показатель матричного умножения над $F$, $\alpha>\omega(F)$, $f\in F[x]$, $\deg f=n$, то возведение в $m$-ю степень в кольце $F[x]/f$ возможно с временной сложностью
$$ O((\log_2(qn\log_qm))\log_2n) $$
на
$$ O\biggl(\frac{\max(q,\sqrt{\log_qmn^{\alpha-2}},\log_qm)}{\log_2(qn\log_qm)}\frac{n^2}{\log_2n}\biggr) $$
процессорах. Библиогр. 11 назв.