index , prev , next

f8_i2.ref

13.Действия над полиномами

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

an x^n + ... + a2 x^2 + a1 x + a0

определяется своими коэффициентами an, ... , a2, a1, a0 , то естественно представлять полином в поле зрения в виде

(е.n) ... (e.2) (e.1) (e.0)

где е.i - объектное выражение, определяющее коэффициент аi .

З А Д А Ч А. Написать функции сложения, вычитания, умножения двух многочленов с целыми коэффициентами.

З А Д А Ч А. Написать функции сложения, вычитания, умножения и деления с остатком для кольца многочленов с рациональными коэффициентами (рациональное число задается парой целых чисел). Коэффициенты многочленов можно выбирать из произвольного кольца.

П Р И М Е Р. Написать функции сложения, умножения и деления с остатком для многочленов с коэффициентами из поля Z2 . (Так как в поле Z2 выполняется равенство 1 + 1 = 0, то операция вычитания совпадает со сложением.)

Р Е Ш Е Н И Е. Многочлен, у которого аn = 1, a остальные n коэффициентов равны 0 или 1, будем представлять в поле зрения в виде последовательности из n+1 символов, каждый из которых может принимать значения 0 или 1. Нулевой многочлен будем представлять в виде пустого выражения.

Функция сложения двух многочленов описывается функциями Z2X_Add, Z2X_Add1, Delete0 ( f8_i2.ref ). Функция Delete_0 убирает впередистоящие нули,Z2X_Add1 - осуществляет сложение. Функция Z2X_Mul умножает два многочлена. Эта функция моделирует "умножение столбиком".

Напишем функцию Z2X_Div деления с остатком двух многочленов. Деление всегда возможно, т.к. старший коэффициент равен 1. Вспомогательная функция Z2X_Div1 отщепляет от делимого столько символов, какова длина делителя. Функция Z2X_Div2 осуществляет фактически "деление столбиком", обращаясь каждый раз к функции Z2X_Div3 для проверки окончания вычислений.

С многочленами тесно связаны поля, состоящие из q = р^n элементов, n> 1.

Конструкция поля GF(q), состоящего из q элементов, аналогична конструкции поля Zp. Только вместо простого числа р выбирается некоторый неприводимый многочлен р(х), степени n c коэффициентами из поля Zp.

Элементами поля GF(q) являются всевозможные остатки от деления многочленов на многочлен р(х), т.е. классы вычетов по модулю многочлена р(х). В качестве результата операции в поле GF(q) берется остаток от деления на р(х) результата обычной операции над многочленами.

В качестве иллюстрации действий в поле GF(q) мы напишем функции при р = 2.

Так же как и в примере модулярной арифметики (book10.htm), неприводимый многочлен р(х) закапывается в копилке под именем "РХ".

Обозначим функции сложения, умножения, деления и нахождения обратного элемента через F8_Add, F8_Mul, F8_Div, F8_Inv. Форматы обращений пусть будут такими же, как и для функций модулярной арифметики (f8_i2.ref).

Отметим, что эти функции очень похожи на функции z_p.ref.

З А Д А Ч А. Написать функции для вычислений в GF(q) для произвольного простого числа q. Естественно, прийдется использовать функции Fp_Add, ...

З А Д А Ч А. Написать функцию, которая по простому числу р и натуральному числу n строит неприводимый многочлен р(х) степени n.

index , prev , next