Главная страница  Дискретный канал связи 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [ 34 ] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

Наконец* проверим, Что все р"* корней многочлена хр"* ~ х различны. Это вытекает из вида формальной производной:

d [хр" - xVdx ((pi) хр"- - 1 - -Ь

так как ((/?)) = О в поле GF (Q). Следовательно; многочлен xi -х не имеет кратных корней. □

Теперь мы получили обращение теоремы 4.6.9,

Следствие 4.6Л2. Для каждого простого р и положительного целого числа т cyu{ecmeyem поле Галуа с р элементами.

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

Теорема 4.6.13, Для каокдого целого положительного т над каждым конечным полем GF (q) существует хотя бы один простой многочлен степени т.

Доказательство. Так как q - степень простого числа, то q" также является степенью простого числа. Согласно следствию 4.6.12, существует поле с q" элементами. Это поле содержит примитивный элемент а, и, по теореме 4.6.8, минимальный многочлен этого элемента а над GF (q) является простым многочленом степени т. □

Следствие 4.6.14. Для каждого целого положительного т над каждым конечным полем GF (q) существует хотя бы один примитивный многочлен степени т.

Доказательство. Пусть а - примитивный элемент поля GF {q"), и пусть / (х) -- минимальный многочлен элемента а над GF (q). Тогда в поле многочленов по модулю f (х) примитивный элемент а = х является корнем многочлена / (х), так что многочлен X представляет собой примитивный элемент поля. □

В заключение главы рассмотрим вопрос о существовании квадратного корня в поле Галуа.

Теорема 4.6.15. Каждый элемент поля GF (2™) имеет в этом поле квадратный корень. Для нечетных простых р половина ненулевых элементов поля GF (р") имеет квадратный корень в GF (р"). Половина ненулевых элементов поля GF (р™) имеет квадратный корень в расширении GF (р™), а не в GF (р").

Доказательство. Так как нулевой элемент имеет квадратный корень в любом поле, то рассматривать надо только ненулевые элементы поля. Сначала рассмотрим полеС (2") характеристики 2 с примитивным элементом а. Тогда порядок элемента а является



нечетным числом. Каждый элемент поля Р может быть записан в виде а для некоторого i, и поэтому - a/, если i четно, и i/p - а(+")/2, если i нечетно. В любом случает/р является элементом поля GF (2").

Рассмотрим теперь поле GF (q), характеристика которого равна простому нечетному числу р, а примитивным элементом является а = 7+, где у - примитивный элемент расширения GF {(f) (порядка q - \ = {q \) {q - 1)) и q -\- \ четно. Так как q равно степени нечетного простого числа. Любой элемент Р может быть записан в виде a или в виде y<?+i) для некоторого L Тогда если i четно, то -j/p = а/2 и принадлежит полю GF (q), а если i нечетно, то -j/p = t+i) /2 принадлежит полю GF (q), но не полю GF (q), так как i (q + 1)/2 в этом случае не кратно + 1.

ЗАДАЧИ

4.1. Пусть над GF (2) Pi{x)= I и (х) = х* + + х + 1.

а. Найти НОД Ipix), рАх)1

б. Найти многочлены А {х) w В (х), удовлетворяющие равенству

НОД [pi (х), Ра {х)]=А (X) pi (х) + В (X) Ps (X).

4.2.а. Сколько различных приведенных многочленов второй степени вида л: + ал; + 6, ЬфО, имеется над полем GF (16)?

б. Сколько различных многочленов вида {х - а) {х - Р), а, фО, имеется над полем GF (16)?

. в. Доказывает ли это существование неприводимых многочленов над полем GF (16)? Сколько простых многочленов степени два имеется над полем GF (16)?

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

4.4.а. Используя алгоритм Евклида, найти НОД (1573, 308). б. Найти целые числа Л и В, удовлетворяющие равенству

НОД (1573,308) = 1573Л + 308В.

4.5. Доказать, что в кольце Z/(15) целых чисел по модулю 15 многочлен р (х) = х - 1 имеет более двух корней. Этот же многочлен над полем имеет два корня. В каком месте не проходит доказательство теоремы в случае кольца?

4.6. Сколько различных приведенных многочленов над GF (2) делят многочлен х - 1?

4.7. Построить поле GF (5), выписав для него таблицы сложения и умножения.

4.8. Построить таблицы сложения и умножения для полей GF (8) и GF (9). 4.9.а. Доказать, что многочлен р (х) = х-j-2 неприводим над полем GF (3).

б. Каковы возможные (мультипликативные) порядки элементов поля

GF (27)?

в. Чему равен порядок элемента х в поле GF (27), построенном по модулю этого многочлена р (х)?

г. Предполагая, что поле GF (27) построено по модулю данного многочлена р {х), найти (2х + I) (х + 2).

4.10. Вычислить 3"" (mod 5).



4.11. Доказать, что кольца отношений Z Ид) и CF {q) [х]1(р {х)) являются кольцами.

4.12. Многочлен р (х) = + д;-f д; + ( неприводим над полем GF (2). Следовательно, кольцо многочленов по модулю р {х) является полем GF (16).

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

б. Показать, ito многочлену л; + 1 соответствует примитивный элемент этого поля.

в. Найти минимальный многочлен элемента x+ 1.

4.13.а. Построить таблицы сложения и умножения поля GF (2), используя неприводимый многочлен -{- х-{- 1 над GF (2).

б. Повторить задачу п. а для многочлена + х- + 1 н доказать, что эти два поля изоморфны. Иначе говоря, доказать, что второе поле можно получить из первого путем переименования его элементов.

4.14. Таблицы сложения и умножения для поля Gf (2) можно построить по меньшей мере двумя следующими способами:

(i) используя неприводимый многочлен степени 4 над CF (2);

(ii) используя неприводимый многочлен степени 2 над GF (4). Построить эти таблицы, используя второй способ.

4.15. Многочлен р [х) ..= д:о + д; + 1 примитивен над полем GF (2) и может быть использован для построения поля GF (1 048 576), в котором элемента, соответствующий многочлену х, будет примитивным.

а. Каковы подполя этого поля?

б. Сколько из этих подполей не имеют никаких собственных подполей, отличных от GF (2)?

в. Вычислить в этом поле выражение аЬ - !, где а = л- -- д: -f- 1 и Ь= х+ х + х.

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

\г (X) S (х) ] = г (х) s{x)+r (X) S (х)

и что (х) делит г (х) тогда и только тогда, когда а (х) делит г (х).

4.17. Доказать, что в любом поле характеристики 2 любой элемент Р удовлетворяет условию - Р = р.

ЗАМЕЧАНИЯ

Материал данной главы обычен для математической литературы. Свойства полей Галуа описываются во многих книгах по абстрактной алгебре, например в книгах Биркгофа и Маклейна [1953], а также Ван дер Вардена 1950, 1953]. Однако стандартное изложение является формальным, уделяет основное внимание абстрактным свойствам и содержит мало примеров и приложений. В книге Берлекэмпа [1968] подробно рассматриваются те свойства полей Галуа, которые исполиЗуются в теории кодирования.




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [ 34 ] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

0.0225