4.3. Базовые алгоритмы лево-циркулянтного преобразования

Попытаемся прежде всего достаточно детально представить-общий метод, с тем чтобы алгоритмы для трех указанных значений получились просто, как его очевидное следствие.

Отправной точкой является выражение (4.45), в котором К остается неопределенным до самого конца вывода. Факторизация приведена в табл. 4.1, где указаны множители из (4.40). Зная находим по двухфазной схеме, основанной на полиномиальном варианте китайской теоремы об остатках: [4.7]. На фазе 1 вычисляем для всех из (4.40)

Эта часть основана целиком на результатах, вывод которых приведен в приложении и которые представлены в табл. П.1, П.2. На

фазе 2 для формирования из используется полиномиальный вариант алгоритма Гарнера [4.7]. Для этого требуются вспомогательные функции введенные ниже. Их использование при формировании будет видно из (4.50):

Если степень равна 1, т. e. , вычисление тривиально. Из видно, что в этом случае

Теперь можно вычислить любые удовлетворяющие (4.47) и, следовательно, (4.51). Выбирая наименьшую степень, получаем

Разобрав принципы вывода алгоритмов, обратимся теперь к частным случаям. Чтобы установить общую картину, будем придерживаться сформулированных принципов даже при рассмотрении случая самого низкого порядка когда вывод мог быть много проще.