3.1.4. Вычисления, использующие схему: (вычисление значений) - интерполяция

Для наших дальнейших рассуждений нам понадобится следующее. Полином — область целостности, называется простым, если из условия следует, что или или является обратимым. [Полином называется обратимым, если существует другой полином такой, что Полином — область целостности, называется неприводимым, если из условия следует, что или или является полиномом нулевой степени, т. е. принадлежит J. Очевидно, что всякий простой полином является неприводимым, но обратное утверждение в общем случае неверно. Заметим, что если J — поле, то все обратимые полиномы являются полиномами нулевой степени (константами); значит, в этом случае, для того чтобы полином был прост, необходимо, чтобы хотя бы один из полиномов был константой, т.е. над полем понятия неприводимого и простого полинома совпадают.

Пример. неприводим над

1) не будет простым над b, поскольку ни 3, ни не являются обратимыми в кольце однако этот полином неприводим над

1 неприводим над Z, Q или но приводим над неприводим над Q, поскольку

Точно как же, как мы определили в Z, мы можем теперь определять отношение эквивалентности в где 3 — поле.

Пусть — нормированный полином степени Тогда для любого мы имеем

Остаток в приведенных соотношениях обозначается или, эквивалентно, Если то делит без остатка и мы пишем

Определим теперь отношение эквивалентности или в кольце следующим образом:

Читатель должен проверить, что это — отношение эквивалентности. Мы затем определяем или просто каждый класс эквивалентности, обозначаемый или просто имеет единственный представитель в а именно Определим сложение и умножение классов эквивалентности формулами

Легко показать, что определенные таким образом операции превращают в кольцо (аналог теоремы 2.3.11.).

Мы можем рассматривать 3 как подмножество кольца отождествляя с [Это может быть сделано, потому что если для в 7, то полином должен делить однако так что полином должен быть нулевым, следовательно, в 3. Таким образом функция, которая отображает а из 3 на из взаимно однозначна, и мы можем отождествлять а с Следовательно, каждый элемент кольца — это элемент кольца J плюс -кратное элемента Если мы положим то каждый элемент кольца имеет вид где - принадлежит 3 для всех i; это то же самое, что сказать, что каждый элемент кольца — это единственная -линейная комбинация элементов 1, а, Поэтому удобно представлять элементы

кольца как полиномы кольца вычисленные в точке , где поскольку

Если мы представляем элементы кольца (также обозначаемого ) как полиномы от а, то сложение и умножение в совпадают со сложением и умножением значений полиномов, вычисленных в точке а. Более того, при умножении в полезно иметь таблицу, выражающую степени а между в терминах полиномов от а степени (Значение этого факта мы оценим позже.)

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

Тогда сложение и умножение — те же, что и для полиномов; например,

Чтобы выразить этот результат в виде полинома от i степени 1, используем то, что и получим

Более того, заметим, что — поле, потому что если а или то

Поэтому выглядит точно так же, как С.

Пример. Рассмотрим нормированный полином , который неприводим над и пусть . Тогда множество содержит элементы . Все операции на этих элементах выполняются по модулю , т.е. все они выполняются по правилам кольца а результаты заменяются их остатками от деления на Так,

Заметим также, что

так что Таким образом, мы построили поле с 4 элементами.

Теорема 3.1.9. Если J — поле, то коммутативное кольцо с единицей. Оно является полем тогда и только тогда, когда полином неприводим в

Доказательство. Доказательство аналогично доказательству теоремы 2.3.11. Например, тот факт, что удовлетворяет аксиомам коммутативного кольца с единицей, следует из того, что удовлетворяет тем же самым аксиомам.

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

Из приведенных рассуждений видно, что мы имеем способ построения новых полей. Мы просто берем неприводимый полином и рассматриваем — вот вам и поле.

Поле вида называется простым расширением поля J, и ниже мы увидим некоторые приложения таких полей.

Как мы уже видели при изучении целых чисел, если мы хотим вычислить окончательный результат, выражения с целыми аргументами, часто легче воспользоваться окольным путем; то же самое верно для вычисления значений выражений с полиномиальными аргументами. Предположим, например, что мы хотим вычислить окончательный результат выражения над где J — полей . Если работа над «трудна», то мы можем работать над полями для различных к, где очевидно, — неприводимый полином, а . В этом случае, однако, мы должны знать границу для например, если мы знаем, что , то индекс к пробегает значения . Более того, заметим, что в результате нашего выбора полиномов поле совпадает с J для любого k, и, таким образом, вычисления не представляют труда.

Окольный подход работает следующим образом. Для мы сначала вычисляем а затем

при условии, что мы выбрали точки а так, что выражения определены, получаем Окончательный результат получается тогда при помощи интерполяции по выбранным точкам и удовлетворяет условию . (См. рис. 3.1.1.)

Рис. 3.1.1. Окольная схема вычисления выражения, использующая схему: (вычисление значения)-интерполяция.

Пример. Работая над вычислим произведение полиномов используя схему, представленную на рис. 3.1.1. Заметим, что степень полинома меньше или равна 3, следовательно, мы должны вычислять значения в 4 точках, т.е. . Полагая и вычисляя над получаем следующие точки:

Имея 4 пробные точки, применяем алгоритм GCRA11-Interpolation :

и получаем что совпадает с ответом, полученным ранее.

Проверка: над

Следует отметить, что мы могли воспользоваться алгоритмом GCRAn-Interpolation, потому что работали в поле. Наш подход должен быть несколько изменен, если 3 — только область целостности, и это — тема последующего обсуждения.

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

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

для наименьшего неотрицательного решения. [Если мы знаем границу для абсолютных значений коэффициентов полинома , то будем искать наименьшее по абсолютной величине решение.]

Пример. Мы хотим вычислить над . Мы отмечаем, что все коэффициенты произведения не превосходят 40, и, поскольку мы будем использовать только эти три модуля. Для мы получаем

Для произведение равно

Наконец, для мы имеем

Итак, мы знаем, как выглядит для различных модулей. Чтобы восстановить сам мы должны решать систему

Ясно, что , где коэффициенты получаются решением следующих 4 систем:

Применяя 4 раза греко-китайский алгоритм, получаем Другими словами, ответ правильный.

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

где — это полиномы

Чтобы восстановить заметим, что для полиномов

Из сделанных замечаний следует, что если модули (данных систем сравнений) попарно взаимно просты и мы полагаем

то система полиномиальных сравнений имеет два однозначно определенных решения, одно из которых — решение с наименьшими неотрицательными коэффициентами, а второе — решение с наименьшими по абсолютной величине коэффициентами. Любое из этих решений получается применением GCRAk (греко-китайского алгоритма, обсуждавшегося при изучении целых чисел). Ясно, что время работы этого процесса