Синтез низкоресурсного линейного автомата с заданным характеристическим многочленом

Формулировка задачи о выборе матрицы с заданным характеристическим многочленом, допускающей простую и быструю реализацию умножения вектора на неё для различных вычислительных платформ.
Задан характеристический многочлен $f(x)$, $\deg f=n$, «общего вида» над $GF(q)$, $q>2$. Требуется разработать алгоритм (работающий «быстро» при больших $n$) нахождения матрицы $A$ над полем $GF(q)$ размера $n\times n$, удовлетворяющей условиям:

• $f(x)=\|xE_n-A\|$, где $E_n$ – единичная матрица размера $n\times n$;
• в каждой строке и в каждом столбце должно быть не более трех ненулевых элементов поля $GF(q)$.

Случаи, представляющие особый практический интерес. Матрица трехдиагональная (линейный клеточный автомат), при этом: либо многочлен $f(x)$ неприводим, либо $f(x)=f_1(x)f_2(x)$, где многочлены $f_1(x)$, $f_2(x)$ неприводимы.
Для случая $q=2$ задача уже имеет решение (т.е. алгоритм построения трехдиагональной матрицы по заданному характеристическому многочлену).