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.