Полиномиальная арифметика и поля Галуа

Полиномиальная арифметика

полином представляет собой выражение вида: u(x) = u_nxⁿ + … + u₁x + u₀ , где коэффициенты u_n , …, u₁ , u₀ – элементы некоторой алгебраической системы S, а переменная x может рассматриваться как формальный символ без определяющего значения

Таким образом, вместо того, чтобы представлять информационное слово D, кодовое слово C и остаток от деления R в виде целых чисел (как это делалось нами ранее), мы можем связать их с соответствующими коэффициентами двоичного полинома, выполняя все последующие математические манипуляции по правилам полиномиальной арифметики. Выигрыш от такого преобразования на первый взгляд далеко не очевиден, но не будем спешить, а лучше преобразуем любое пришедшее нам в голову число (например, 69h) в двоичный полином. Запустив «Калькулятор» или любое другое подходящее приложение по вашему вкусу, переведем наше число в двоичный вид

: 69h –> 1101001.

получается следующее: 1x⁶ + 1x⁵ + 0x⁴ + 1x³+ 0x² + 0x + 1. По сути говоря, битовая строка «1101001» является одной из форм записи вышеуказанного полинома – ненаглядной с точки зрения неподготовленного человека, но удобной для машинной обработки. Постойте, но если 69h уже представляет собой полином, то в чем разница между сложением полиномов 69h и 27h и сложением целых чисел 69h и 27h?! Разница несомненно есть. Как еще показал Ницше: фактов нет, а есть одни лишь интерпретации. Интерпретация же чисел и полиномов различна, и математические операции над ними выполняются посовершенно независимым правилам.

Коэффициенты в полиномиальной арифметике строго типизированы и коэффициент при x^k имеет иной тип, нежели при x^m (конечно, при том условии, что k m).

А операции над числами различных типов категорически не допустимы! Все коэффициенты обрабатываются независимо, а возникающий при этом перенос в старший разряд (заем из старшего разряда) попросту не учитывается. Покажем это на примере сложения чисел 69h и 27h:

H) 1101001 (69h)

+0100111 (27h) +0100111 (27h)

------- -------