6.4. Полное разложение многочлена x^n-1

В качестве одного важного примера использования алгоритма разд. 6.1 рассмотрим разложение многочлена над для взаимно простых . В матрице в этом случае тогда и только тогда, когда тогда и только тогда, когда Например, при

С помощью соответствующих перестановок строк и столбцов матрица может быть приведена к виду

Ясно, что базис нуль-пространства матрицы дают многочлены

В общем случае если над то можно положить

где — некоторое множество чисел, замкнутое относительно умножения на по модулю Каждый из таких многочленов имеет некоторый нетривиальный общий делитель с Таким образом, для разложения многочлена нет необходимости выполнять операции над матрицей, а можно обозревать все многочлены Каждый из многочленов имеет некоторый общий делитель с и он может быть найден с помощью алгоритма Евклида. Применяя алгоритм Евклида к различным многочленам мы в конце концов получим разложение на неприводимые множители. В большинстве случаев целесообразно начинать с разложения на круговые многочлены и использовать многочлены и алгоритм Евклида для дальнейшего разложения круговых многочленов на неприводимые множители.