Коды Рида-Соломона всех типов будем обозначать одним символом RSq(n,d). Все они имеют параметры [п, п - d + 1,d]q и являются, так называемым, q-значными МДР-кодами (см. [7]), а именно кодами, которые имеют максимально возможную размерность п - d + 1 при заданных п ж d.

Одна из модификаций кода типа 3 (длины п = q + 1) будет далее использована как основа для построения "системы открытого шифрования", которую мы будем подробно изучать. В частности, мы рассмотрим группу автоморфизмов (определение - ниже) этого кода. Эта группа имеет наиболее сложное строение по сравнению с группами автоморфизмов кодов типов 1. и 2. Поэтому мы сначала достаточно подробно изучим группу автоморфизмов кодов типа 2., а затем в основном без доказательства приведем нужные свойства группы автоморфизмов кода типа 3.

Надо сказать, что коды типа 3., в некотором смысле, являются наиболее интересным среди, определенных ранее трех типов кодов Рида-Соломона. В частности, они имеют наиболее мощную группу автоморфизмов и наибольшую длину и размерность при заданном кодовом расстоянии d. Коды типа 1. используются для построения циклических кодов Боуза-Чоудхури-Хоквингема. Коды RSq(n,d) всех типов могут быть заданы (определены) и несколькими другими способами.

1.5.Код Боуза-Чоудхури-Хоквингема. Предположим, что поле Fr,r = р1 , где число V делит I (11), является подполем поля F,;. q = р1. В этом случае мы будем рассматривать г-значным подкод кода RSq(n,d), п = q - 1, который состоит из всех векторов RSq(n,d), координаты которых принадлежат полю F,.. Этот код называют кодом Боуза-Чоудхури-Хоквингема (обозначение: BCHr(n,d)). Он имеет параметры [q - 1,d. k],,. где d > d, к > q - 1 - (d - 1 - ["])/,. По поводу этих оценок и замечательных свойств кода BCHT(n,d) см. книгу [7].

Следует обратить внимание на то, что размерности кода RSq(n,d) и кода BCHr(n,d) вычисляются над разными полями: размерность первого - над F,;. а размерность второго - над его подполем F,..

1.6.Группа автоморфизмов кода RSq(n,d), п = q. Если переставить координаты кодового вектора а кода К., то полученный вектор а может как принадлежать так и не принадлежать коду К.. Если перестановка координат а такова, что ст(а) = a G К. для всех а € к-, то она называется автоморфизмом кода К.. Очевидно, что если а - другой автоморфизм, то произведение а а также является автоморфизмом. Поэтому все автоморфизмы кода К, образуют группу Ек, которая называется группой автоморфизмов кода К,. Заметим, что на множестве перестановок координат векторов пространства F™ можно естественным образом определить операцию •, по отношению к которой все они образуют группу Sn порядка п\, называемую симметрической группой.

Перестановку а удобно представлять себе в виде перестановочной матрицы IV = Г = 7i,j, которая реализует эту перестановку в виде матричного умножения. А именно, элемент матрицы -jij равен 1 тогда и только тогда, когда координата с номером % переходит посредством действия а в координату с номером ./. Во всех остальных случаях -jij = 0. Таким образом, матрица Г представляет из себя матрицу, у которой в любой строке и в любом столбце имеется ровно одна 1. Перестановочная матрица Г реализует перестановку а координат вектора а в виде матричного умножения следующим образом ст(а) = аГ. Матричная группа автоморфизмов G = Gjc образована всеми матрицами IV, у которых а € Ек.

Если Г 6 Ск: а матрица В является проверочная матрица кода К., то В-Г, очевидно, также является проверочной матрицей этого кода К.. Поэтому она может быть представлена в виде В Г = h В, где невырожденная матрица h размера п - k х п - к является матрицей перехода от одного базиса пространства строк матрицы В к другому В1. Последнее высказывание на языке матриц записывается как раз в виде В = h - В.

Интересно отметить, что указанное отображение Г -> h реализует гомоморфизм матричной группы Gk, автоморфизмов кода К, (матрицы размера п х п) в матричную группу, образованную матрицами h размера п - к х п - к. Ядро J (к.) этого гомоморфизма образуют элементы Г, которые оставляют на месте все векторы кода К.. Поэтому матрицы h, на которые отображается группа С\: посредством соответствия В Г = h В, изоморфна факторгруппе Gк/-f(к-). Так как далее мы ограничимся рассмотрением только кодов, у которых ядро J (К.) тривиально (состоит из одного элемента), то мы всегда будем полагать, группа образованная матрицами h изоморфна группе Gjc- К таким кодам относятся коды RSq(n, d) и коды BCHq(n, d). Доказательство этого утверждения в более общей форме см. ниже (Лемма 2).

Рассмотрим ансамбль (множество) Вк, кодов, определяемых проверочными матрицами из множества Ш = {В ГГ G Sn}. где В - одна, не важно какая, матрица вида (4). Число 4q(n,d) различных

(как множеств) кодов К, = RSq(n,d) в ансамбле Вк, (по другому, кодов с проверочной матрицей вида (4)), как нетрудно видеть, равно

4q(n,d) = j-;,(6)

где К. = RSq(n,d) - один из фиксированных кодов Рида-Соломона с проверочной матрицей (4).

Как мы видим, число различных кодов Рида-Соломона полностью определяется порядком его группы автоморфизмов. К настоящему времени группа автоморфизмов Gjc кода К. = RSq(n,d) не вычислена. Можно только утверждать, в Gnsq(n,d) входят подстановочные матрицы, которые реализуют подстановку х -> ах, а G F,; \ {0} = F*, элементов поля F,; в себя. Эти матрицы образуют группу, которая изоморфна, так называемой, мультипликативной группе поля Fg. Эта группа является циклической, поэтому и коды Рида-Соломона также как и коды Боуза-Чоудхури-Хоквингема с помощью соответствующей нумерации множества 21 могут быть сделаны циклическими. На этом здесь останавливаться не будем (см. [7]).

1.7. Число проверочных матриц кода RSq(n,d). Если h - невырожденная матрица размера d - 1 х d - 1, то, как нетрудно видеть, проверочные матрицы В и hB определяют один и тот же код RSq(n, d). В качестве задачи для самостоятельного доказательства приведем следующее утверждение. Матрицы В и hB различны, если h ф Е (единичная, матрица). Отсюда следует, что число различных проверочных матриц, которые определяют один и тот же код RSq(n,d), равно iV-i, где Л,;.„ - число невырожденных квадратных матриц h размера s х s.

Лемма 1. Число N,,.s равно

Nq,s = (qs - Ш -q)---(qs- g""1).(7)

Доказательство. Первую строку невырожденной матрицы h над полем Fg размера s х s можно выбрать qs - 1 способами - все векторы длины s, исключая нулевой. Вторую строку - qs - q способами - все векторы, которые не пропорциональны первой строке. Третью строку - qs - q2 способами - все векторы, которые не входят в подпространство размерности 2 пространства Fg, натянутое на первые две строки. И так далее. Наконец, последнюю строку h можно выбрать qs - г/* 1 способами - все векторы которые не принадлежат s - 1-мерному пространству натянутому на первые s - 1 строк h. Отсюда вытекает лемма 1.

Заметим, что вычислить число различных матриц достаточно просто; вместе с тем вычислить число различных кодов RSq(n,d) значительно сложнее.

1.8. Обобщенные коды RSq(n, d), п = q+1 Рида-Соломона. Нам удобно рассмотреть несколько более широкий по сравнению с RSq(n, d) класс кодов, который мы будем называть обобщенные коды Рида-Соломона и обозначать их тем же символом RSq(n,d).

Пусть Fq = Fg U оо - поле, к которому добавлен элемент оо. Рассмотрим матрицу

где ctj G F, ctj ф on при j ф % и при ctj = 00 соответствующий столбец матрицы С имеет вид (О,... ,0,Zj)T.

Также как для обычного код Рида-Соломона, обобщенный код длины п = q + 1 имеет кодовое расстояние равное d и размерность п - d+l. Это доказывается почти точно также как и для обычного кода.

Матрица С, очевидно, может быть представлена в виде С = В D. где D = diagui. z->.... , zn), Zj G F?\{0}, - диагональная матрица ж В - проверочная матрица кода Рида-Соломона типа 3. Преобразованная матрица С будет выступать далее как проверочная матрица системы открытого шифрования. В этой связи значительный интерес представляет строение группы обобщенных автоморфизмов кода Рида-Соломона с проверочной матрицей В, к изучению которой мы переходим.

Обобщенный код BCHr(n,d) определяется аналогично тому, как это было сделано в разделе 1.5: BCHr(n,d) = RSq(n,d) Г) F™, т.е. коду BCHr(n,d) принадлежат все векторы кода RSq(n,d), координаты которых принадлежат подполю F,. поля F,;. Обобщенные коды BCHr(n,d) включают в себя и, так называемые, кода Гоппы (см. [7]).

Код можно задать и с помощью своей проверочной матрицы над полем F,. размера п - к х п, где к - размерность (над F,.) кода BCHr(n,d). Эта матрица также может иметь вид (8). Определить размерность к даже в частных случаях обобщенных кодов BCHr(n,d) в отличии от размерности любого кода RSq(n, d) очень нетривиально. В общем случае сделать это не представляется возможным.

1.9. Группа обобщенных автоморфизмов кода RSq(n,d), п = q+1, Рида-Соломона. . Если в качестве обычных автоморфизмов кода К. выступали перестановочные матрицы Г, то в качестве обобщенных автоморфизмов выступают матрицы вида Л = Г • D, где D - невырожденная диагональная матрица, которые носят название унипотентных. Другими словами, Л - перестановочная матрица, у которых ненулевыми элементами являются ненулевые элементы поля Fg.

Унипотентные матрицы сохраняют расстояние Хемминга. А именно, d(a, b) = </(аЛ. ЬЛ). Как будет видно ниже, это свойство позволяет использовать эти матрицы в системе открытого шифрования. Нашей основной целью является получение нетривиальных нижних верхних оценок порядка группы обобщенных автоморфизмов кода RSq(n,d) и затем оценок для числа различных кодов RSq(n,d).

Теперь переформулируем для обобщенных автоморфизмов некоторые из определений раздела 1.6.

Если унипотентная матрица А такова, что аА = a G К. для всех a G /С, то она называется обобщенным автоморфизмом кода К,. Очевидно, что если А - другой автоморфизм, то произведение А • А также является автоморфизмом. Поэтому все обобщенные автоморфизмы кода К, образуют группу Sjc, которая называется группой обобщенных автоморфизмов кода К,. Элементами группы Зк являются, так называемые, унипотентные матрицы размера п х п. Также как в разделе 1.6 можно рассмотреть представление *.: группы обобщенных автоморфизмов Зк в виде невырожденных матриц над Fg размера п - к хп - к. А именно, элементу А из Зк сопоставим матрицу h = На, которая определяется соотношением

НА В = В • Л.(9)

Произведение А • А двух элементов из В/с соответствует произведение </(А • А) = by На двух элементов из Нк- Заметим, что порядок следования сомножителей в Нк обратный по сравнению с В/с. Поэтому рассматриваемое отображение является гомоморфизмом д : А -> На группы В/с в группу матриц размера п - к х п - к над полем Fg.

Лемма 2. Для кода К. = RSq(n,d) гомоморфизм g является изоморфизмом, т.е Нк =

Доказательство. Ядро гомоморфизма g тривиально. Это следует из-за того, что матрица В не содержит пропорциональных столбцов и поэтому /> ф В А для любой неединичной унипотентной матрицы А. Поэтому среди неединичных унипотентных матриц А не существует такой, что а = аА для всех а € RSq(n,d). Лемма доказана.

Теорема 1. Порядок группы Вк; автоморфизмов кода Рида-Соломона К, = RSq(n,d) не превосходит :\*,;.,/.... , где NqiS - число невырожденных квадратных матриц Н размера s х s над полем Fq.

Доказательство. Как следует из леммы 2 Нк = \Нк,\- Поэтому Нк < Nq<nk, k = п - d+1, ибо, очевидно, что *.: не превосходит числа всех матриц размера d - 1 х d - 1 над полем F,;. Теорема доказана.

Хотя оценка для числа В/с во многих случаях, по-видимому, весьма грубая, ничего лучшего не известно.

Рассмотрим ансамбль (множество) Ак, К, = RSq(n,d), кодов, определяемых проверочными матрицами из множества Ш = {/>AA G i",,.n}. где В - одна, не важно какая, матрица вида (4), а (.,,.„ - множество всех унипотентных матриц над полем Fg. Заметим, что ансамбль Ак, совпадает с множеством кодов, проверочные матрицы которых имеют вид (8). Кроме того, нетрудно установить, что Г,;.„ = nl(q - 1)™. Нас будет интересовать число различных кодов в ансамбле Ак,-

По тем же соображениям, что приведены в разделе 1.6, для числа Aq(n,d) различных обобщенных кодов Рида-Соломона К = RSq(n,d) в ансамбле Ак имеет место равенство

Aq{n,d) = nl{q~l)n.(10)

К сожалению, группа Зк обобщенных автоморфизмов кода Рида-Соломона не известна. Поэтому мы не можем воспользоваться равенством (10) для вычисления числа Aq(n,d).