Краткий план. Введение в алгебру полиномов. Наибольшие общие делители полиномов над полем (стр. 8 из 8)

Третий элемент второго столбца означает, что

. Два последние столбца, состоящие только из нулей, обуславливают на выходе вектор при h=3. Соответствующий полином будет .

Из вида матрицы Q-I при h=3 видно, что векторы

и удовлетворяют условию . Так как эти вычисления дали только два линейно независимых вектора, то должен иметь только два неприводимых сомножителя над GF(13).

Теперь нужно переходить к третьему шагу алгоритма Берлекампа, в котором непосредственно найдутся эти сомножители. Этот шаг состоит в нахождении

для всех . Здесь и . После вычислений получаем при и при . Непосредственная проверка показывает, что полиномы найдены правильно.

Но если p достаточно велико, то алгоритм имеет огромную трудоёмкость, связанную с вычислением НОДов для всех

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