Конечные поля

Определение конечного поля

Ранее в 1.3.2 дано определение поля   как коммутативного кольца с единицей, в котором каждый ненулевой элемент имеет мультипликативный обратный элемент. В теории помехоустойчивых кодов весьма важное значение имеют поля, образованные конечным множеством элементов – так называемые конечные поля Галуа (Galois Field), обозначаемые  . В связи с этим дадим их развернутое определение.

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

1. GF.1. Из введенных операций над элементами поля одна называется сложением и обозначается как  , а другая - умножением и обозначается как  .

2. GF.2. Для любого элемента   существует обратный элемент по сложению   и обратный элемент по умножению   (если  ) такие, что   и  . Наличие обратных элементов позволяет наряду с операциями сложения и умножения выполнять также вычитание и деление:  ,  . Поэтому иногда просто говорят, что в поле определены все четыре арифметические операции (кроме деления на 0).

3. GF.3. Поле всегда содержит мультипликативную единицу 1 и аддитивную единицу 0, такие что  , и   для любого элемента поля.

4. GF.4. Для введенных операций выполняются обычные правила ассоциативности  ,  , коммутативности  ,   и дистрибутивности  .

5. GF.5. Результатом сложения или умножения двух элементов поля является третий элемент из того же конечного множества.

Аксиомы GF.1 – GF.5 являются общими для полей как с конечным, так и с бесконечным числом элементов. Специфику же конечного поля определяет аксиома GF.5, где ключевыми являются слова «из того же конечного множества».

Требование конечности множества определяет ряд ограничений как на количество элементов поля  , так и на понятия «сложение» и «умножение».

Конечные поля существуют не при любом числе элементов, а только в том случае, если их количество –простое число   или его степень  , где   – целое. В первом случае поле   называется простым, а во втором – расширением   простого поля.

Очевидно, операции комбинирования элементов конечного поля не могут быть обычными сложением и умножением. Выполнение аксиомы GF.5 для простого конечного поля обеспечивается совершением арифметических операций по модулю числа  , которое носит название характеристики конечного поля. Можно убедиться, что в кольце вычетов по модулю   (см. 5.3.1) каждый ненулевой элемент имеет обратный элемент тогда и только тогда, когда   – простое число [25, 26, 33]. Следовательно, кольцо вычетов по модулю простого числа   является простым полем  . Элементами этого поля являются целые числа  . Операции сложения и умножения в таком поле производятся по модулю  . Пример простейшего двоичного поля   приведен в 5.3.3.

Элементами   расширенного поля   могут быть, например, все многочлены степени   или меньше, коэффициенты которых лежат в простом поле  . Число   называется порядком расширенного поля и определяет количество различных многочленов.

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

Очевидно, любые результаты вычислений в поле после приведения по модулю   должны оставаться обратимыми – только в этом случае наша система образует поле. Для этого используемый полином   должен быть неприводимым в поле  , т.е. его нельзя разложить на множители, используя только многочлены с коэффициентами из  . Это означает также, что   не имеет корней в поле  . Аналогом неприводимого полинома является простое число в поле вещественных чисел.

К сожалению, регулярных методов поиска неприводимых полиномов не существует, они обычно определяются перебором. К настоящему времени имеются подробные таблицы неприводимых полиномов [30, 33].

Особым свойством конечных полей является связь между собой всех ненулевых элементов   и возможность выражения каждого из них через один элемент  , называемый примитивным, как некоторую целую степень этого элемента. Множество   ненулевых элементов расширения   образует циклическую мультипликативную группу (см. 5.3.2), т.е. элементы находятся между собой в соотношении  . Примитивных элементов в   может быть несколько.

Арифметика остатков 1. Чётные и нечётные числа Все знают, что числа бывают чётные и нечётные. Чётные делятся на 2 без остатка, а нечётные дают остаток 1. Другими словами, чётные числа имеют вид 2k для целых k, а нечётные 2k + 1, тоже при целых k. Скажем, число 0 чётное (0 = 2 · 0), а число −3 нечётное (−3 = 2 · (−2) + 1). Несложно проверить, что сумма двух чётных или двух нечётных чисел чётна, а сумма чётного и нечётного числа нечётна: + Ч Н Ч Ч Н Н Н Ч × Ч Н Ч Ч Ч Н Ч Н Например, если мы складываем чётное и нечётное число, то получаем 2k + (2l + 1) = 2(k + l) + 1, то есть нечётное число. А если мы умножаем два нечётных числа, то получаем (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1, то есть нечётное число. I Папа с сыном играют в такую игру: каждый пишет на бумажке число, не говоря его другому, потом они открывают эти числа, и если сумма чётная, выигрывает папа, а если нечётная, то сын. Честная ли это игра? Тот же вопрос, если вместо суммы чисел берётся их произведение. J Среди целых чисел чётные и нечётные встречаются одинаково часто: если мы возьмём большой интервал подряд идущих чисел, то количество чётных и нечётных в этом интервале будет почти одинаково (отличаться максимум на 1) I Почему? J Если заменить в таблицах буквы Ч и Н на 0 и 1, взяв нуль и единицу в качестве представи- телей классов чётных и нечётных чисел, то получатся почти что обычные таблицы сложения и умножения: + 0 1 0 0 1 1 1 0 × 0 1 0 0 0 1 0 1 Разница с обычными только в одном месте: 1 + 1 = 0. 2. Деление на 3 и остатки Попробуем составить аналогичные таблицы сложения и умножения для чисел, делящихся и не делящихся на 3. Тут сразу же возникает проблема: мы не знаем, что сказать про сумму двух чисел, не делящихся на 3. Она может делиться на 3 (например, 1 + 5 = 6), а может и не делиться (например, 2 + 5 = 7). Дело в том, что не делящиеся на 3 числа могут быть двух видов: одни дают остаток 1 (имеют вид 3k + 1 при целом k), а другие дают остаток 2 (имеют вид 3k + 2). 1 I К какому типу относится число 1000? А число −1? Найдите соответствующие значения k. J I Покажите, что все три типа чисел (делящиеся на 3, дающие остаток 1 и дающие остаток 2) встречаются одинаково часто: в большом отрезке подряд идущих чисел их количества отличаются максимум на 1. J Теперь можно составить аналогичную таблицу сложения и умножения остатков по модулю 3: + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 × 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 Каждую клеточку в этой таблице несложно проверить. Например, (3k + 1) + (3l + 2) = 3(k + l) + 3 = 3(k + l + 1) + 0 и (3k + 2)(3l + 2) = 9kl + 6k + 6l + 4 = 3(3kl + 2k + 2l + 1) + 1. I Папа с сыном играют в такую игру: каждый пишет на бумажке число, не говоря его другому, потом они открывают эти числа, и если сумма не делится на 3, выигрывает папа, а если делится, то сын. Честная ли это игра? J Аналогичные таблицы можно составить не только для деления на 2 и 3, но и для любого числа. Но сначала мы дадим более формальные определения. 3. Деление с остатком Говорят, что целое число a делится на целое число b, если a = bk для некоторого целого числа k. В этом случае говорят также «a кратно b», и «b является делителем числа a». В этом определении можно было бы сказать: «если частное a/b целое», но этим бы исключался случай b = 0, который формально допустим по нашему определению. Правда, особого смысла в нём всё равно нет: единственное число, которое делится на 0, это число 0. Определение допускает также отрицательные a и b: скажем, число −6 делится на −2 (а также и на 2), всего у него 8 делителей, если считать и положительные, и отрицательные. I Что это за делители? J Впрочем, обычно, говоря о количестве делителей у положительного целого числа, имеют в виду только положительные делители (считая единицу и само число). I Сколько (положительных) делителей у числа 30 = 2 · 3 · 5? у числа 210 = 2 · 3 · 5 · 7? J I Придумайте (положительное целое) число, у которого было бы ровно 6 (положительных) де- лителей. Тот же вопрос для 7 делителей. J I Говорить о кратных можно не только для целых чисел, но и для отрезков: один отрезок кратен другому, если второй укладывается в первом целое число раз, то есть если отношение (длина пер- вого)/(длина второго) целое. Докажите, что два отрезка имеют общую меру (отрезок, которому они оба кратны) тогда и только тогда, когда они имеют общее кратное. J I Найдите наименьшее общее кратное отрезков длиной 15/6 и 21/10. J I Могут ли два отрезка не иметь общего кратного? J Если два числа a и b делятся на третье число c, то и их сумма a + b и разность a − b делятся на это c. В самом деле, если a = kc и b = lc, то a + b = (k + l)c и a − b = (k − l)c. Для делимости произведения достаточно делимости одного из сомножителей: если a делится на c, то и ab делится на c, каково бы ни было (целое) b. В самом деле, если a = kc, то ab = k(bc) = (kb)c. 2 Множество целых чисел называют идеалом, если вместе с любыми двумя числами оно содержит их сумму и разность, и вместе с любым числом оно содержит все его кратные. Используя эту терминологию, можно сказать, что для любого c множество всех кратных числа c является идеалом. I Докажите, что произведение любых трёх последовательных целых чисел делится на 3. J I Докажите, что число a 3 − a делится на 3 при любом целом a. J I Докажите, что сумма 84 + 85 + 86 + 87 + 88 + 89 + 90 делится на 7 и на 87. J I Найдите трёхзначный и семизначный делители числа 103103103. J I Какие из следующих утверждений верны: (1) если a делится на c, а b не делится на c, то a + b не делится на c; (2) если a не делится на c и b не делится на c, то a + b не делится на c; (3) если a не делится на c и b не делится на c, то ab не делится на c? Докажите верные и приведите контрпримеры к неверным. J I Известно, что a, b, , c, d — положительные целые числа, и ab = cd. Докажите, что если a делится на c, то d делится на b. J I Числа a и b целые, причём 2a + 3b делится на 7. Докажите, что a + 5b также делится на 7. J I Положительное целое число a чётно, но не делится на 4. Покажите, что количество (положи- тельных) чётных делителей a равно количеству (положительных) нечётных делителей a. J I Докажите, что произведение любых k подряд идущих целых чисел делится на k! = 1·2·3·. . .·k.J Теперь определим деление с остатком. Пусть b — целое положительное число. Деля на b с остат- ком, мы связываем предметы в пачки по b в каждой, пока это возможно: количество полных пачек называется частным (говорят ещё «неполное частное», чтобы отличать от частного как дроби), и сколько-то предметов останется, их количество и называют остатком Формально: разделить целое a на целое положительное b означает найти такое целое q (частное) и такое целое r (остаток), что a = b · q + r; 0 6 r < b. Ограничения на r понятны: остаётся сколько-то предметов (возможно, ни одного), но меньше b, иначе возникла бы ещё одна целая пачка. Теперь можно сформулировать теорему: деление с остатком всегда возможно, притом един- ственным образом. Не очень понятно, что тут доказывать (неужели это не очевидно, если подумать о связывании предметов в пачки?). Тем не менее для педантов можно привести такое доказательство. Единственность. Если a = bq + r = bq0 + r 0 , то r − r 0 = b(q 0 − q) и потому r − r 0 делится на b. Но оба числа r, r0 находятся в интервале 0, 1, . . . , b − 1, так что их разность (если из большего вычесть меньше) не больше b − 1, и может делиться на b, лишь если равна нулю. Поэтому r = r 0 , откуда и b = b 0 . Существование можно доказать индукцией по a. Для a = 0 частное и остаток равны нулю: 0 = 0· b+ 0. Если a = bq+r, то a+ 1 = bq+ (r+ 1). При этом r+ 1 6 b, так как r < b. Если r+ 1 < b, то для a + 1 получаем частное q и остаток r + 1. Если же r + 1 = b, то a + 1 = bq + b = b(q + 1) + 0, получаем частное q + 1 и остаток 0. Программистам будет ближе другое доказательство существования: q:=0; r:=a; {a=bq+r; r>=0} пока (r>=b): q:=q+1; r:=r-b; {a=bq+r; r>=0; r 0 являются, как говорят, инвариантом цикла, они выполняются после любого числа итераций. В самом деле, начальные значения q = 0 и r = a удовлетворяют условию a = qa + r; итерация цикла происходит при r > b и потому r 3 после уменьшения на b остаётся неотрицательным, а условие a = bq + r не нарушается, если увеличить q на единицу и одновременно уменьшить r на b. Выход из цикла происходит, когда условие нарушается, то есть r < b (в дополнение к инварианту) — что и требуется определением остатка. Внимательные читатели, наверно, уже заметили ошибку в рассуждении: оно годится лишь при a > 0, поскольку иначе инвариант r > 0 будет нарушен. Собственно, и индуктивное рассуждение годилось тоже только при a > 0. Так что для отрицательных a возможность деления с остатком надо доказывать отдельно. Пусть a = −a 0 , разделим a 0 на b с остатком: a 0 = bq0 + r 0 . Если r 0 = 0, то a = −a 0 = b(−q 0 ) + 0, так что можно взять q = −q 0 и r = 0. Если r 0 > 0, то можно записать a = −a 0 = −bq0 − r 0 = b(−q 0 − 1) + (b − r 0 ), так что можно взять q = −q 0 − q и r = b − r 0 : поскольку мы предположили, что 0 < r0 < b, то 0 < b − r 0 < b, и r попадает в нужный диапазон. Аналогичная проблема возникает во многих языках программирования: целочисленное деление a на b даёт неполное частное в нашем смысле лишь при a > 0, а, скажем, −7 div 3 оказывается равным −2, а не −3, как требует наше определение. Тем не менее математически наше опре- деление удобнее, так как при этом сохраняется общая формула для чисел с данным остатком: скажем, числа 3k + 1 при всех целых k при делении на 3 дают остаток 1 (и частное k). I Можно ли разрезать шахматную доску 8 × 8 на прямоугольники 3 × 1? J I Найти число вида 100 ∗ ∗∗ (звёздочки обозначают некоторые цифры), которое делится на 547. J I Книги на столе пытались связывать в пачки по 2, по 3, по 4 и по 5 книг, и каждый раз оставалась одна лишняя. Сколько книг было на столе? (Известно, что их было больше одной и не больше 100.) J I Число a даёт остаток 6 при делении на 12. Может ли оно давать остаток 12 при делении на 20? J| 4. Сравнения по модулю Если два числа a и b дают одинаковые остатки при делении на положительное число N, то говорят, что они сравнимы по модулю N, и пишут a ≡ b (mod N). Эквивалентное определение: a и b сравнимы по модулю N, если разность a − b делится на N. (В самом деле, если они дают одинаковый остаток r, то a = kN + r, b = lN + r, и a − b = kN − lN = (k − l)N. Наоборот, если a − b = mN, и b даёт остаток r, то b = lN + r и a = (a − b) + b = mN + lN + r = (m + l)N + r, то есть a даёт тот же остаток r.) Можно сказать, что при данном N все целые числа разбиваются на N классов в зависимости от остатков по модулю N: два числа в одном классе сравнимы, а числа в разных классах — нет. I Докажите, что числа a 2 и b 2 дают одинаковые остатки при делении на a − b, если a и b — положительные целые числа, и a > b. J Важное свойство сравнений: чтобы узнать, в какой класс попадет сумма или произведение двух чисел, достаточно знать, в каком классе лежат слагаемые или сомножители: если одно из слага- емых (один из сомножителей) изменить на кратное N, то сумма (произведение) тоже изменится на кратное N. В самом деле, если к одному из слагаемых прибавить kN, то к сумме тоже прибавится kN, аналогично для разности. С произведением: (a + kN)b = ab + kbN ≡ ab (mod N). Благодаря этому свойству в выражении, содержащем операции сложения и умножения (или воз- ведение в целую степень, которое сводится к многократному умножению), можно заменять слага- емые или сомножители на сравнимые по модулю N — если результат нам важен лишь по модулю 4 N. Например, можно найти 2 100 mod 7 (остаток от деления 2 100 на 7): поскольку 2 3 = 8 ≡ 1 (mod 7), то 2 99 ≡ (23 ) 33 ≡ 1 33 = 1 (mod 7), так что 2 100 ≡ 2 99 · 2 ≡ 1 · 2 = 2 (mod 7). I Какой остаток даёт число 100100 при делении на 99? J I Найдите две последние цифры числа 991000 . J Сравнения по модулю (пусть не под таким названием) часто встречаются в быту. Скажем, ци- ферблат показывает количество прошедших часов по модулю 12, а также количество минут по модулю 60. Измеряя углы в градусах, мы фактически измеряем число градусов по модулю 360. I Как построить угол в 1 ◦ , если задан угол в 19◦ ? J Последняя цифра (для положительного целого числа) сравнима в этим числом по модулю 10, а две последние цифры — по модулю 100. В музыке двенадцать полутонов составляют целую октаву, и потом названия нот (до, до диез и так далее) повторяются. Известный признак делимости на 9 (число делится на 9 тогда и только тогда, когда его сумма цифр делится на 9) можно обобщить и сказать, что число и его сумма цифр сравнимы по модулю 9. Это легко следует из наших рассуждений. Скажем, для четырёхзначного числа: abcd = 1000a + 100b + 10c + d ≡ 1a + 1b + 1c + 1d = a + b + c + d (mod 9), поскольку 10 ≡ 1 (mod 9) и, следовательно, 102 , 103 ,. . . все сравнимы с 1 по модулю 9. I Придумайте признак делимости на 11, использующий знакопеременную сумму цифр. J Если мы хотим представить себе наглядно числа по модулю N, можно вообразить кольцевое шоссе длиной в N километров: на нём километровые столбы будут 0, 1, 2, . . . , N − 1, далее идёт столб N, который на том же месте, где 0, затем N + 1 на том же месте, где 1, и так далее. Можно пойти в другую сторону и поставить столб −1 на том же месте, где N −1: это соответствует тому, что (N − 1) ≡ (−1) (mod N). Для действительных (не целых) чисел равенство дробных частей можно назвать сравнением по модулю 1. Точнее говоря, целой частью числа x называют наибольшее целое число, не превос- ходящее x; целую часть обозначают обычно bxc. Разницу x − bxc называют дробной частью и иногда обозначают {x}. Числа с одинаковой дробной частью отличаются на целое число единиц; можно сказать, что они «сравнимы по модулю 1». Обратите внимание, что с отрицательными числами та же ситуация: b−2.3c = −3 и {−2.3} = 0.7. I Нарисуйте на плоскости пары (x, y), для которых bxc = byc. Тот же вопрос для условия {x} = {y}.J

Степень вершин

Определение 1.9. Степенью вершины   для неориентированного графа называется количество ребер, инцидентных этой вершине. Вершина степени   называется изолированной. Вершина степени   называется висячей. Обозначается степень вершины:   .

Определение 1.10. Полустепенью исходавершины   для орграфа называется количество дуг, для которых   является начальной вершиной, обозначается:   . Полустепенью захода вершины   называется количество дуг, для которых   является конечной вершиной, обозначается:   . Если   , то вершина   называется истоком. Если   , то вершина v называется стоком.

Теорема 1.1 (Эйлера). Сумма степеней вершин графа равна удвоенному количеству ребер:

 .

Доказательство.

При подсчете суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого. ,

Следствие 1.1. Число вершин нечетной степени четно.

Доказательство.

По теореме Эйлера сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число. ,

Следствие 1.2. Сумма полустепеней вершин орграфа равна удвоенному количеству дуг:

 .

Доказательство.

Сумма полустепеней вершин орграфа равна сумме степеней вершин графа, полученного из орграфа забыванием ориентации дуг. ,

Построение кода Прюфера свободного дерева

Вход: Дерево T(V,E) в любом представлении, вершины дерева занумерованы

числами 1 ..р произвольным образом.

Выход: Массив А : array [l..p - 1] of l..p — код Прюфера дерева Т.

for г from 1 to р - 1 do

v\ = min{k е V | d(k) = 1} { выбираем вершину v — висячую вершину с

наименьшим номером }

A[i]: = Г(ь) { заносим в код номер единственной вершины, смежной с v }

V: = V — v { удаляем вершину v из дерева }

end for

По построенному коду можно восстановить исходное дерево с помощью алго-

ритма 9.2.

304 Глава 8. Связность

Алгоритм 9.2 Распаковка кода Прюфера свободного дерева

Вход: Массив А : array [1..р — 1] of 1..р — код Прюфера дерева Т.

Выход: Дерево T(V, Е), заданное множеством рёбер Е, вершины дерева

занумерованы числами 1 ..р.

Е: = 0 { в начале множество рёбер пусто }

В: = 1..р { множество неиспользованных номеров вершин }

for г from 1 to р — 1 do

v : = min [к Е В \ \/ j ^ i (к Ф А[?'])}{ выбираем вершину v — неиспользован-

ную вершину с наименьшим номером, который не встречается в остатке кода

Прюфера }

Е-. — Е+ (v, А[г\) { добавляем ребро (г>, А[г\) }

В : = В - v { удаляем вершину v из списка неиспользованных }

end for

Пример Для дерева, представленного на рис. 9.10, код Прюфера 7,9,1,7,2,2,7,

1,2,5,12. На этом рисунке числа в вершинах — это их номера, а числа на рёбрах

указывают порядок, в котором будут выбираться висячие вершины и удаляться

рёбра при построении кода Прюфера.

ОБОСНОВАНИЕ КОД Прюфера действительно является представлением свободно-

го дерева. Чтобы убедиться в этом, покажем, что если Т' — дерево, построенное

алгоритмом 9.2 по коду А, который построен алгоритмом 9.1 по дереву Т, то Т"

изоморфно Т, X" ~ Т. Для этого установим отображение / : 1 ..р —>• 1 ..р между

номерами вершин в деревьях Т и X" по порядку выбора вершин в алгоритмах:

если вершина v выбрана па г-м шаге алгоритма 9.1, то вершина f(v) выбрана на

г-м шаге алгоритма 9.2. Заметим, что Dom / = 1 ..р, поскольку висячие вершины

есть в любом дереве и удаление висячей вершины оставляет дерево деревом. Да-

лее, I m / = 1 ..р, поскольку па г-м шаге алгоритма 9.2 использовано г — 1 число

из р чисел и остаётся р — г + 1 чисел, а в хвосте кода Прюфера занято не более

р — г чисел. Более того, Vv ( f ( v ) = v). Действительно, номера вершин, которые

являются висячими в исходном дереве, не появляются в коде Прюфера (кроме,

может быть, одной висячей вершины с наибольшим номером), а номера вершин,

9.3. Представление деревьев в программах 305

которые пе являются висячими, обязательно появляются. Поскольку при выбо-

ре первой вершины v в алгоритме 9.1 все вершины с меньшими номерами пе

являются висячими, их номера будет присутствовать в коде и, значит, не мо-

гут быть использованы па первом шаге алгоритма 9.2. Таким образом, па первом

шаге алгоритм 9.2 выберет ту же вершину v. Но после удаления вершины v па

втором шаге снова имеется дерево, к которому применимы те же рассуждения.

Итак, / — тождественное и, значит, взаимно-однозначное отображение. Заметим

теперь, что для определения г-го элемента кода па г-м шаге алгоритма 9.1 исполь-

зуется, а затем удаляется ребро (и, Л [г]) и в точности то же ребро добавляется в

дерево Т' на г-м шаге алгоритма 9.2. Следовательно, / — взаимно-однозначное

отображение, сохраняющее смежность и Т ~ Т'. •

З А М Е Ч А Н И Е

Код Прюфера — наиболее экономное по памяти представление дерева. Его можно немного

улучшить, если заметить, что существует всего одно дерево с двумя вершинами — К2,

а потому информацию о «последнем ребре» можно не хранить, она восстанавливается

однозначно.