Построение линейных кодов в полях алгебраических функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА

ПОСТРОЕНИЕ ЛИНЕЙНЫХ КОДОВ В ПОЛЯХ АЛГЕБРАИЧЕСКИХ ФУНКЦИЙ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Напра си

Глухов Михаил Михайлович

МОСКВА-2005

Работа выполнена на кафедре дискретной математики Института криптографии связи и информатики Академии ФСБ России.

Научный руководитель:

доктор физико-математических наук,

профессор Степанов Сергей Александрович.

Официальные оппоненты:

доктор физико-математических наук,

профессор Гашков Сергей Борисович; кандидат физико-математических наук, доцент Применко Эдуард Андреевич.

Ведущая организация:

Институт информационных наук и технологий безопасности Российского государственного гуманитарного университета.

Защита диссертации состоится года в 11 часов

на заседании диссертационного совета Д501.001.44 Московского государственного университета им. М.В.Ломоносова по адресу: 119992, г.Москва, ГСП-2, Ленинские горы, МГУ, 2-ой учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан

года.

Ученый секретарь диссертационного совета,

профессор Трифонов Н.П.

жн

г9ш

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория помехоустойчивого кодирования, или теория корректирующих кодов возникла в середине прошлого века в связи с практической потребностью повышения достоверности приема информации, передаваемой по реальным каналам связи. Первыми работами по теории помехоустойчивого кодирования явились классические работы К. Шеннона "Математическая теория связи", 1948 г. и "Связь при наличии шума", 1949 г.

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

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

Первыми работами в этом направлении являются работы В.Д.Гоппы (см. [3]), в которых он предложил строить коды на точках алгебраических кривых, определенных над конечным полем. Позднее это направление развивалось многими авторами. В 1984 г. появился обзор [1] С.Г.Влэдуца и Ю.И.Манина работ по кодам на модулярных кривых. В настоящее время имеется ряд монографий, посвященных методам построения и исследованию свойств алгебро-геометрических кодов (см. [2], [8], [9]).

В.Д.Гоппа показал, что его конструкция позволяет строить асимптотически длинные коды, информационная мера которых достигает известной границы ВаршамовагГилберта. Затем М.А.Цфасман [7], а также С.Г.Влэдуц и Т.Цинк заметили, что среди таких кодов существуют коды с информационной мерой, превосходящей указанную границу, которая до этого долгое время оставалась не улучшаемой (см. [10]). При этом для построения кодов использовались алгебраические кривые с большим числом точек над заданным конечным полем К, т.е. с большим числом /¿"-рациональных точек.

Для числа N всех /Г-рациональных точек на алгебраической кривой имеется известная оценка Вейля |JV-(g+l)|<20,y5, где д - род кривой, K=GF{q). В 1991 году С.А.Степановым (см. [41) были указаг ны кривые, на которых эта оценка достигается. Идея С.А.Степанова использована автором для построения широкого класса кривых с большим, хотя и не достигающим оценки Вейля, числом К- рациональных точек. Этот класс кривых над полем K=GF(qn) характеристики р содержит суперэллиптические кривые, заданые уравнением

„ , Vs = /(*), (*)

с многочленом f(x) вида:

I. (ух + (^)<("-1,/2)а (ух + У,

где а, 6, п, s 6 N, 2 /п, п > 1, а + Ь = s, (а, s) = 1, ц 6 К*, - 1.

И. + (^)«п/2-1)в (у* + (дх)«"/г+1)Ь, где а, Ь,п, s € N, п - четно, п > 2, а + Ь = s, (а, s) = 1, fj, € К*, s\q — 1.

/ »/а \4/2

III. I /хх 4- (/ix)9 1 , где s, n € N, s, n - четны, /х € iff*, — 1, и кривые Артина-Шрейера, заданные уравнением

yp'~y = f(x), (**)

с многочленом f(x) вида:

где n, a G N, п - нечетно, п > 1, ц £ К*, р* - l|g - 1.

V. (/хх)'п/2+,+1-(Мх)'п/2-1+1, где п, s € N, п - четно, п > 2, ц е К*, р" - 1|q - 1.

Такие кривые мы будем называть, соответственно, кривыми типа I-V. Некоторые из этих кривых уже использовались для построения хороших кодов с помощью расслоенных произведений (см. [6]).

Представляется актуальной задача подробного изучения геометрических кодов на указанных кривых, или же в полях алгебраических функций определяемых теми же уравнениями. Эти поля мы также будем называть полями типа I-V.

Цель диссертационной работы. Подробно исследовать алгебраические кривые и поля алгебраических функций типов I-V, алгебро-геометрические коды на этих кривых и в указанных полях алгебраических функций над полем К = GF(qn).

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

Научная новизна результатов. Все основные результаты диссертации являются новыми. Получены следующие результаты.

1. Описаны неприводимые над полями GF(q), GF(qn) делители многочленов I-V, в нетривиальных случаях найдены формулы числа таких делителей заданной степени.

2.Описаны ЛГ-рациональные точки кривых типов I-V.

3. Для простых дивизоров полей алгебраических функций типов I-V найдены их степени, относительные степени, индексы ветвления.

4. Доказаны теоремы о сужении возможности выбора пар дивизоров без нарушения эквивалентности определяемых ими кодов.

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

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

Апробация результатов. Результаты диссертации докладывались на II Международной конференции "Теория чисел и ее приложения" (Тула, 1997 г.), на VII Международном семинаре "Дискретная математика и ее приложения "(Москва, 2001 г.), на V Международной конференции "Алгебра и теория чисел: современные проблемы и приложения"(Тула, 2003 г.), на конференции Академии ФСБ и Института криптографии, связи и информатики, посвященой памяти ак. А.Н. Колмогорова (Москва, 2003 г.).

Публикации. Основные результаты диссертации опубликованы в семи работах, список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, разбитых на параграфы, и заключения. Общий объем диссертации составляет 115 страниц. Список литературы включает 49 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Введение.

Во введении даны пояснения по актуальности темы, сформулированы задачи и основные результаты диссертации.

Глава 1. Вспомогательный материал

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

Под полем алгебраических функций F = К(х,у) будем понимать простое алгебраическое расширение поля рациональных дробей

К{х) над фиксированным полем К. Кольцом дискретного нормирования поля F называется любое подкольцо О поля F, удовлетворяющее условиям: KCOCF , K±0±F , Va€F (а£0 или а-1 € О).

Кольцо О есть максимальное подкольцо в F, и является локальным кольцом главных идеалов. Его максимальный идеал Р состоит из всех его необратимых элементов. Факторкольцо О/Р называется полем вычетов по идеалу Р и обозначается Fp. Естественный эпиморфизм ф:0-*0/Р индуцирует изоморфное вложение поля К в Fp. В связи с этим К отождествляется с ф(К) и считается, что KcFp. Степень расширения \Fp-.K] называется степенью идеала Р и обозначается deg Р. Для элемента оеО образ ф(а)=а+Р обозначается а(Р) и называется значением а на Р. Если degP=l, то Fp отождествляется с К, и потому а(Р)=а+Р считается элементом из К.

По кольцу дискретного нормирования О и его максимальному идеалу Р = Ю однозначно определяется отображение v : F ZUoo: v(a) = к, если а е F* и а = tk-u, где fc 6 Z и u е О*, v(0) = оо (и(а) не зависит от выбора элементов t пи). Следуя [5], мы будем называть указанное отображение v дискретным нормированием, или просто - нормированием, поля F по максимальному идеалу Р кольца О. Кольцо О и его максимальный идеал Р однозначно определяются по нормированию v. А именно: 0={a£F : v(a)>0}, P={a£F : u(a)>0}.

Для описания колец нормирования поля F удобно рассмотреть сначала простейший случай, когда степень расширения [F:K(x)]=1.

В этом случае каждый элемент а £ F однозначно представляется в виде несократимой дроби а = h(x)/g(x), где h(x),g(x) € К[х], (h(x),g(x)) = 1, и условиям 1), 2) определения кольца нормирования удовлетворяет множество

Ор(х) = Щх)/д{х) : Цх),д(х) € К[х], (р(х),д(х)) = 1}

при любом фиксированном унитарном неприводимом над К многочлене р(х) € К[х]. При этом максимальный идеал Рр(х) — р(х)Ор(ху

Кроме колец нормирования вида Ор(х) в К{х) есть еще лишь одно кольцо нормирования. Оно обозначается через О ж и состоит из несократимых дробей вида h{x)/g{x) в которых deg/i(a;) < degg(x). Его максимальный идеал Р^, порождается элементом 1/х и состоит из дробей h(x)/g(x), где deg h(x) < deg^(a;).

Функция нормирования, соответствующая Ор(х), определяется для

а=ШеГ"'- vPÍ*)(a) = ехРр(х) М*) - ехРр(х) 9{х) , где

exPp(z) а(а;) = max{n € N : р(ж)"|а(х)}, a соответствующая кольцу

О«,: ито(а) = deg д(х) - degft(a¡).

Максимальными идеалами степени 1 в поле К{х) являются все идеалы вида Рр(х), где degp(x) = 1, и Р«,. Значение а(Р) дроби

а = е Ор, где а(х) = anx"+...+aix+ao, Ь(х) = bmxm+...+bix+b0,

а„фО, Ьтф0, вычисляется следующим образом: если Р = Рх-С, то а(Р) - если Р=РЖ, то а(Р)=при п=т и а(Р)=0 при п<т.

В случае [-Р:-К"(а;)]>1 любое кольцо нормирования О' поля Р является расширением единственного кольца нормирования О поля К(х), причем О—О' П К(х). Аналогичное соотношение Р=<2 П К{х) выполняется и для максимальных идеалов Р, ф колец О, О'. При этом имеют место естественные вложения КсК{х)сЕд. Тот факт, что (} есть расширение идеала Р обозначается (0|-Р). Степень расширения [^д :К(х) р] называется относительной степенью идеала С} и обозначается /(<2\Р). Нормирование и<э поля Р обладает следующим свойством: Уа£К(х) ид(о)=е ир(а), где е=е(ф|Р) - независящее от а натуральное число, называемое индексом ветвления идеала С}.

Для каждого кольца нормирования О поля К(х) существует конечное непустое множество расширений ..., От, являющихся кольцами нормирования поля Р. При этом для идеалов Р кольца О и (¿1 - кольца г = 1, ...,т, выполняется следующее фундаментальное тождество стР)1ШР) = = ВД1-

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

Простые дивизоры полей К(х) и Р далее будут обозначаться соответственно буквами Р и. с индексами или без. Множество всех простых дивизоров полей К(х) и Р обозначим через Рк(х) и Рр-

Любая целочисленная линейная комбинация конечного множества элементов из Рр называется дивизором поля Р. Любой дивизор Б можно записать в виде

Л-ЕдеР,**. (1-3)

где пдЕЪ и лишь конечное число коэффициентов пц отлично от 0. Множество 5(-0)={ф | пд^О} называют носителем дивизора Б. На множестве ©р всех дивизоров поля Р определяется покомпонентное сложение и, таким образом, Юр превращается в свободную абелеву грзгппу со свободной системой образующих Рр. В ней выделяется подполугруппа Ш>р дивизоров вида (1.3) с неотрицательными коэфи-циеитами пс;. Такие дивизоры Б называют неотрицательными, или эффективными, и пишут Б > 0. Неотрицательный дивизор Б, в котором существует слагаемое с ненулевым коэффициентом, называют положительным и пишут Б > 0.

На дивизоры распространяются нормирования поля Р. Для дивизора Б вида (1.3) и<э(£>) = 11(2- Число Х^еР,, называется степенью дивизора Б и обозначается <!е§ Б. Заметим, что при Б = <3 степень дивизора Б равна степени идеала (}.

С каждым элементом а & Г* ассоциируется так называемый главный дивизор

M-EgeP, (L4)

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

L(D) = {я € F : (х) + D > 0} U {0} (для D е

Каждое из них есть линейное пространство над полем К, и если D2-Di>0, то L{Di)cL(D2) и dim(Z,(D2)/L(D1))<degD2-degDi. Размерность пространства L{D) называется размерностью дивизора D и обозначается также dimD. Для любого дивизора D поля F выполняется неравенство dimD < 1 + deg D, а величина д = max^gjj^{degD — dimD + l}^называется родом поля F.

Таким образом, для любого дивизора D: dim D= deg D+1—д+с, где с>0. Известная теорема Римана-Роха (см., например, [51) выражает константу с через некоторый канонический дивизор W, зависящий от D: с = dim(Wr — D). Нами используется следствие из этой теоремы, по которому dimD = degD + 1 — д, если degD > 2д — 1.

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

В §3 определяются наиболее известные классы линейных кодов и, в частности, алгебро-геометрические коды Гоппы.

Каждый такой код на гладкой проективной кривой V над GF(q)

задается двумя дивизорами D, G, где D=Pi+P2-\-----1-Рп - сумма

некоторых точек кривой V, G - любой дивизор, носитель которого не содержит Pi,...,Рп. Соответствующий код C{D,G) состоит из всех векторов вида (f(Pi),f{P2),-.-,f{Pn)), где / пробегает множество всех таких рациональных функций на V, для которых (/)+(?> 0.

Аналогичным образом определяется код C(D,G) в любом поле алгебраических функций F. При этом в качестве дивизора D берется сумма некоторых простых дивизоров первой степени, а в качестве G - любой дивизор с условием S(D)r\S(G) = 0. Значение элемента / на простом дивизоре Р € D вычисляется точно так же как и для идеала 1-ой степени поля К(х), расширением которого является идеал Р.

Такой код C(D, G) изоморфен факторпространству L(G)/L(G-D) и при K=GF(q) является линейным [п, к, ¿¿]ч-кодом с параметрами: \n-{q+l)\<2gy/q , Jfe=dimL(G!)-dimL(G!-D), d > degG-2^+2, d > n— deg G, где g - род кривой или поля алгебраических функций.

Если 2д + 1 < degD < п, то отображение <jd • L(G) C(D,G), ^n(f) = (f(Pi)^f{Pz),--,f(Pn)), является изоморфизмом линейных

пространств, и тогда dim L(G - D) = 0, к = dim G = deg G + 1 - g, n + l-g<k + d<n + l.

Глава II. Многочлены Степанова и их обобщения.

Для описания неприводимых над полем GF(q) делителей указанных выше многочленов достаточно описать все неприводимые делители многочлена , а±=.

gu(x) = tc"^ +х, (П.1)

где и = ±1 при нечетном п и и = ±2 или и = 0 при четном п.

При четном q его неприводимыми над GF(q) делителями являются в точности все неприводимые над GF(q) многочлены, степени которых делят число (п + и)/2.

При решении поставленного вопроса в случае нечетного q использованы общепринятые обозначения, включая следующие:

— для а е GF(q)*, ord а - мультипликативный порядок элемента а,

— для к € Z, exp2(fc) = тах{/ 6 N0 : 21\к},

— Ф(т) - число неприводимых унитарных многочленов степени т из кольца GF(g)[a;], всех при т > 1 и всех, кроме х, при m = 1.

Теорема II.1 А) Пусть q - нечетно. Неприводимый над GF(q) многочлен h(x) степени т > 1 делит <?u(i) тогда и только тогда, когда: 1) т\п+и, т % ; 2) ord(a)\2{qm/2-1), где а - корень h(x). Б) При выполнении условий 1),2) число Хт неприводимых над GF(q) унитарных делителей степени т многочлена ди(х):

Хт = E-=i (?),гдек=вф2(т)- (IL2)

Решен вопрос о неприводимых над GF(qn) делителях многочлена

Теорема II.2 а) Если п - нечетно, т.е. и = ±1, то любой неприводимый над полем GF(q) делитель многочлена ди(х) является неприводимым над полем GF{qn).

б) Если п - четно и и= ± 2, то любой неприводимый над GF(q) делитель степени т>\ многочлена ди{х) разлагается над GF(qn) в произведение двух неприводимых многочленов степени т/2.

в) Если п — четно и и = 0, то любой неприводимый над полем GF(q) делитель степени т > 1 многочлена д„(х) разлагается над полем GF(qn) в произведение линейных многочленов.

Следствие II. 1 Если 2 Цп, то множество неприводимых над GF(qn) делителей многочлена ди{х) совпадает с множеством его неприводимых делителей над GF(q). Если 2\п и и= ± 2, то многочлен ди(х) имеет неприводимые над GF(qn) делители степени

т тогда и только тогда, когда он имеет неприводимые над GF(q) делители степени 2т. При этом число неприводимых над полем GF(qn) делителей степени т> 1 многочлена ди(х) вычисляется по

формуле (II S), если 2 Jfn, и равно если 2|п.

Следствие II. 2 Пусть q - нечетно, и = 1 или 1. Тогда:

а) если п = l(mod 2) или п = 2(mod 4), то (gu(x),g-u(x)) = х,

б) если п ~ O(mod 4), то (gv(x),g-u(x)) = хч + х.

Для вычисления числа точек на рассматриваемых ниже алгебраических кривых нам необходимы сведения о корнях многочленов I, II, III в полях GF(q), GF(qn) и результаты о суммах характеров конечных полей от этих многочленов.

Обозначим через Ль Ач, Аз - множества всех корней многочленов I, II, III в поле GF(q), и Bi, В2, £3 ~ множества всех корней многочленов I, II, III в поле GF(qn).

Теорема II.3 а) Если q - четно, то Ai = Аг = A3 = GF(q),

б) Если q - нечетно, то А\ = Ач= Аз = {0},

В =т В = ! {0} > п = 2( mod 4)

1 1 ' ' 2 \ GF(q)a, а е GF(q2), а«"1 = -1 , п = 0( mod 4) '

В3 = GF{qn/2)a, где а 6 GF{qn),a<>n'2-1 = -1.

в) Все корни многочленов I, II имеют кратность s, а корни многочлена III - s/2.

Пусть Xn,s{x) = Xs{normn{x)) ~ мультипликативный характер индекса s поля GF(qn), индуцированный характером \в поля GF(q).

Для / £ GF(qn)[x] обозначим: 5„,,(/) = £*eGF(9~) *„,.(/(*))■ Известно (см. [5], стр.41), что число решений уравнения (*) над GF(qn) выражается формулой Nq* = YlXn , Sn,tO)-

Теорема II.4 Пусть f(x) е GF(qn)[x], п > 1, а, Ь, s € N, s\q - 1, a + b = s. Тогда:

. «i/ » „ _ .f qn — 1 , если 2 Ца

а) если 2 /п, f(x) - вида I, то 5„,,(/ = { „ J, ;

I Я Q г если 2\q

qn — q ,если q - любое, 4|п

б) если 2\п, f(x) - вида II, то Sn,s(f) = qn - 1 ,если 2 J(q, 4 Цп ;

q"-q2 , если 2\q, 4 Jfn

в) если 2|п, 2|s, f(x) - многочлен вида III, mo Sn,«(/) = (g"/2-l)<f/2.

Теорема II.5 Пусть f(x) - многочлен вида I-III над полем GF(qn), n > 1, а + Ь= s, 8\q—l, Mq — множество корней многочлена }{х) в поле GF{qn) и Mi = GF(qn)\M0. Тогда:

а) для a€GF(qn) уравнение (*) имеет над GF(qn) ровно s решений вида (а, Р), если a£Mi, и единственное решение (а,0), если а£Мо;

б) если Nq* - число всех решений над GF(qn) уравнения (*), то

sqn — (s - 1 )q ,если f(x) вида I и 2\q , или - II и 2 ¡(q, 4|n sq" — (a — 1) ,если f(x) вида I и 2 Ц q , или - II и 2 J[q, 4 J[n sqn — (s — 1 )q2 ,если f(x) вида II при 2|q и 4/n ' sqn - (s - l)qn/2 ,если f{x) вида III

N4n - 1

С использованием сумм аддитивных характеров, доказана Теорема II.7 Пусть GF(qn) - поле характеристики р, п>3, р'—1|д—1. Тогда число решений над GF(qn) уравнения (**) равноp*qn.

Глава III. О свойствах алгебраических кривых и полей алгебраических функций.

Алгебраические кривые типа I и П имеют особые точки. В связи с этим перейдем к бирационально изоморфным им гладким кривым.

Теорема III.1 Аффинная кривая V типа I или II бирационально

изоморфна гладкой кривой Vi, заданной уравнением

V' = A(w), (III.2)

где:

1) ЛН = (1 + ш«("",,/,-1)в(1 +г</п+1"2-1)ь, если /(х) вида I, 2 J[q;

2) fxH = (1+<д1+ц„-1 )tt(1+T+tp,-1 )Ь, если /(*) вида I и 2\q;

3) h(w)={l+w4n/2 '-^"(l+w«''**1-1)», если f{x) вида II, 2J(q, АЦп;

„n/2-1я/2+1_i

4) ЛИ = )"( )Ь> ecAU }{x>> вида 2I*> 4*n;

en/2—1 _ • «»/Í+Í-1

5) /i(u>)=(

Г+Ш«-1—)"( ^i+ii)«-1—)Ь' если ви^а II, 4|n.

Теорема III.2 Алгебраическая кривая, заданная уравнением (III.S), имеет ровно N = sqn GF(qn) -рациональных точек в каждом из случаев 1)-5).

Теорема III.3 Алгебраическая кривая V, заданная уравнением (III.2), имеет род д, который в каждом из случаев 1)-5) выражается соответственно формулой:

1)9 = (<?(п+1)/2 + <7(п~1)/2 - 4) (я - 1)/2;

2)9 = (g<"+1>/2 + ff(»-i)/a - 2(g + l))(e - 1)/2;

S)g = {qn'2+1 + g"/2-1 - 4)(s - l)/2;

ff = (gn/2+1 + qnl2~l ~ 2(<72 + l))(e - l)/2; 5; ff = (?n/2+1 + - 2(g + l))(s - l)/2. Кривая типа III разлагается в объединение § кривых, каждая из которых бирационально изоморфна кривой, заданной уравнением

у2 = х + х4"/2. (III.5)

Теорема III.4 Пусть q - нечетно. Тогда кривая Vi, заданная уравнением (III. 5), является гладкой неприводимой кривой рода g = (<7П/2 — 1)/2 с N = 2q" - qn!2 GF(qn)-рациональными точками.

Для кривой V типа IV или V доказана

Теорема III.5 Алгебраическая кривая V типа IV или V над полем GF(qn) является неприводимой гладкой кривой рода g — (qn — 1)дг("+«)/2 с Nqn = p'qn GF(qn)-рациональными точками.

Далее рассматриваются поля алгебраических функций над полем К = GF(qn), заданные уравнениями вида (III.2), где fi{x) - любой из многочленов 1)-5).

В целях общности введем для многочлена Д (ж) обозначение

ф{х)=ф1(х)а-ф2{х)\

где ф\(х), фъ(х) - многочлены из первых и вторых скобок записей многочлена Д(х) в случаях 1)-5) теоремы III. 1.

Во всех указанных случаях нас интересуют простые дивизоры поля F, их индексы ветвления и степени относительно поля К(х), соответствующие функции нормирования. Условимся простые дивизоры Рх-а поля К(х) при а 6 К обозначать через Ра.

Теорема III.6 Пусть К = GF(qn), F - поле алгебраических функций, заданное уравнением у' = фх (х)аф2 (х)6, a + b = s, s \ q — 1, (а, s) = 1, 71 > 1 при нечетном q, п > 2 при четном q. Тогда:

1) F есть циклическое расширение поля К(х) степени s, К - алгебраически замкнуто в F, и род поля F д—(deg фг (х) + deg фг (х) - 2) ;

2) для каждого простого дивизора Ра, а £ К, поля К{х) существует ровно s расширений Qa,ß, где ß пробегает все решения уравнения у' = ф{а) в К; Qa,ß как идеал порождается многочленом х — а и со-держиту-ß; e(Qaj\Pa) = 1, degQa%ß = degPa = 1, f(Qa^\Pa) = 1;

3) для простого дивизора Рос поля К{х) существует s расширений

порождаемых как идеалы элементом х 1 и содержащих соответственно элементы ух~т/* — г = 1,..., з, где & - корни степени s из 1 в поле К; при этом e(Qäl-foo) = 1, deg£?«> = 1,

/Ю2?|Роо) = 1, i = h...,s;

4) если р(х) — неприводимый над К многочлен и р{х)\ф{х), то для простого дивизора Рр(х) поля К{х) существует единственное расширение Qp(x); degQp(x) = degPp(x) = degp(x), e{Qp{x)\Pp(x])=s, f{Qp(x)\Pp{x))=i;

5) если многочлен p(x) неприводим над К и р(х) Ц ф(х), то простой дивизор Рр(х) поля К{х) имеет в F t расширений Q$xy i = 1, i, где ф и t зависит от р(х) и для каждого из них eiQp(x)\Pp(x)) = 1»

HQpI)\Pp(*)) = I de6= f degp(x).

Ниже рассмотрено поле F, заданное уравнением

/г 9n'2

у2 = Л(х), где h(x) = х + я®" = JJ (я — о»)«

Теорема III. 7 Пусть К = GF(q"), q - нечетно, п - четно, F -поле алгебраических функций над К, заданное уравнением у2 = h(x), а(х),Ь(х) в К[х], Ъ(х) ф 0, и г = Тогда:

1) F - гиперэллиптическое поле функций рода g = \{qn^2 — 1);

2) для Р = Px-a,, i = I,..., qn/2, в F существует единственное расширение Q = Qx-a., и e{Q\P) = 2, f{Q\P) = 1, degQ = 1, vQ(z) = 2(ехрж_0. a(x) - ехрг_а> b(x));

S) для P = Рх-ь, b € K, b Ф aj, г = 1,..., q"/2, существуют ровно 2 расширения Q^xlb, Q^-b> вторые порождаются многочленом x—b и содержат, соответственно, у — с и у + с, где с - фиксированное значение (h(б))1/2. При этом e{Q^b\P)=HQ^b\p)= deg<?<J2b=l, (z) = ехР*-ьФ) ~ ехРх-ьЧх)> 3 = !>2;

^ г — Ь

4) для Рос в F существует единственное расширение Q^; е(<?оо|Яоо)=2, /(Qoo|Poo)=degQoo=l, VQoo(2r)=2(deg6(a;)-dega(a;));

5) если р(х) - неприводимый над К многочлен степени m > 1 и h(x) не является квадратом в К[х]/р(х), то для Р = Рр(х) существует единственное расширениеQp(x)> e{QP(x)\P)—^, f(QP(x)\P)=2, degQp(x) = 2degp(i), vQpW(z) = expp(l) a(x) - expp(l) b{x);

6) если p(x) - неприводимый над К многочлен степени т > 1 и h(x) - квадрат в К[х]1р{х), то для Р = Рр(х) существуют ровно 2

расширения Q%y j = 1,2; e(Q$x)\P) = f(Q$x)\P) = 1, deg Qp(l) = degp(x), vq(i) (г) = expp(l) a(x) - expp(l) b(x).

Рассмотривая поля F типа IV и V, объединим эти случаи записав: /(*) = hu(x) = а;«(п+",/2+1 - a.«<~)"+i = *(*«" _

где и = 1 в случае IV, или и — 2 в случае V. Из теоремы II.6 следует, что уравнение

Ур' ~ У = Ma) (III.8)

имеет р' решений при любом а 6 GF(qn). С использованием этого факта доказана

Теорема III.8 Пусть F - поле алгебраических функций, заданное уравнением (**) при f(x) = hu(x), и=1,2. Тогда:

1) F есть расширение поля К(х) степени р', К алгебраически замкнуто в F ирод поля F: g = |(р» - l)g(n+u)/2;

2) для каждого а € К простой дивизор Ра = Рх-а поля К(х) имеет р' различных расширений Qa,p> порождаемых многочленом х — а и содержащих многочлены у — р, где ¡3 пробегает все решения уравнения (IÍI.8) (при соответствующем и); e(Qa р\Ра) = 1,

f(Qa,e\Pa) = р', degQafi = 1;

3) простой дивизор Роо поля К(х) имеет единственное расширение Qoo; е(Ооо|Рос) = Р', }{Qoc\Poo) = degQoo = 1;

4) еслир(х) - неприводимый над К унитарный многочлен и degp(a:)>l, то е(<Эр(х)|Рф)) = 1, f{Qp(x)\Pp(x))=p', degQp{x) = degp(i).

Глава IV. Об алгебро-геометрических кодах Гоппы

В этой глгше исследуются свойства геометрических кодов Гоппы на рассмотренных полях алгебраических функций.

При определении алгебро-геометрического кода Гоппы C(D, G) в поле алгебраических функций F в качестве дивизора D выбирают сумму Qi + •• ■ 4- Qn различных простых дивизоров степени 1 поля F, в качестве G - любой дивизор с условием 5(G) П S(D) = 0. Кодовыми словами являются все векторы (z(Qi)i •••) z{Qn)), z € L(G). Тгжие слова образуют линейное пространство над К, изоморфное факторпространству L(G)/L(G - D). Если в G в качестве слагаемых участвуют лишь простые дивизоры степени 1, то D и G можно рассматривать как дивизоры на кривой V, и C(D, G) естественно называть кодом на кривой V.

Большая свобода выбора дивизора G, на первый взгляд, делает трудно обозримым весь класс кодов Гоппы на F. Однако многие варианты выбора G приводят к эквивалентным кодам. В частности, C(D,G) ~ C(D, Gi), если Gx = G + (z), z £ F, (см., например, [9]). А так как для любого G существует такое z G F, что G + (z) > 0, то достаточно брать лишь G > 0.

Если <7 > 0 и носитель 5((7) дивизора б не содержит бесконечных простых дивизоров, то неравенство (а(х)/Ь(х)) + <7 > О может выполняться лишь при условии с1е§6(а;) > degа(a;), что существенно ограничивает пространство ¿((7). Поэтому при построении кодов С(0,0) обычно в ¿>((7) включают бесконечные простые дивизоры.

В случае I, когда К содержит в бесконечных простых дивизоров

, для любого г£Р выполняется равенство г^т (г)=идо> (г).

В связи с этим следует выбирать (7 так, чтобы ,..., входили в дивизор <7 с одинаковыми коэффициентами.

Всюду ниже в случае I мы выбираем б удовлетворяющий указанным выше условиям. При этом для упрощения записей введем обозначение ^^ _ д(1) +

Для общности в записях в случаях И-Ш единственный бесконечный простой дивизор Q00 будем обозначать также

Нами получено еще одно существенное ограничение на выбор дивизора (7 при построении кода с точностью до эквивалентности. При этом рассмотрена более общая ситуация, когда F задается уравнением (*) над причем многочлен /(х) имеет каноническое разложение над ОР(дп):

Нх) = а • П*=1 а е (1У.1)

причем — 1 , в>1 , deg/=m>0 , (в,тц) = 1 , г = 1, (1У.2)

Заметим, что все эти условия выполняются в случаях 1-Ш.

Теорема IV. 1 Пусть Р - поле алгебраических функций, задан-ноенадСР(дп) уравнением (*) при условиях (IV.1), {IV.2) иС(0,С\) - код, заданный в поле Р дивизорами

к I

о = а1+...+о„ ,в 1 = гг<эР,(х)+чЯчл*) + г<э°°>

Р<(®)|/(®), г, > о, г = 1 q}(х) Л/{х), >0, 1 = 1 ,...,1, г > 0. Тогда код С(£>,(?1) эквивалентен коду С{Г>,С) при (7 = + сфоо) где £,• - остаток от деления г,- на з,

с = г + degc(a;), с(х) = П*=1 рЫг'/>] ■ 1^=1 <&(*)'' •

Таким образом, при построении кодов Гоппы на Р в случаях 1-Ш можно ограничится рассмотрением кодов С {Б, (7) лишь при дивизорах в вида, указанного в теореме IV.1.

В случаях IV-V, когда Р задается уравнением (**), дивизор в можно выбирать еще более простого вида.

Пусть Р - поле алгебраических функций над полем (7.Р(<7П) характеристики р, заданное уравнением ур' - у = /(я), где deg /(х) = т> о, (т,р) = 1, р' - - 1.

Теорема IV.2 В указанном выше поле F любой код C(D,G\) эквивалентен коду C(D,G), где G = rQ«,.

Заметим, что в теореме IV.1 избавиться в G от слагаемых второй

суммы Yli=\ tiQp,(x), не нарушая эквивалентности кодов не всегда возможно.

Рассмотрим поле F типа I или II. Для построения кода выберем в качестве дивизора D сумму всех N = sqn простых дивизоров степени

1, кроме Qоо, » = 1,

D = Q1+Q2+-+QN. (IV.6)

Согласно теореме IV. 1 при построении кодов с точностью до эквивалентности в качестве G можно взять дивизор вида

G = £1 , + El' , T2,kQ2,k + rQoo, (IV.7)

где QtJ = <ЭР,,,(х). Pi,j(x)\4>i(x), 0 < ritJ < s, j = 1 i = 1,2,

r >0,

Qoo — Qoo- Так как код C(D,G) изоморфен факторпро-странству L(G)/L(G — D), то для его описания достаточно описать пространства ¿(G) и L(G — D).

В общем случае известно что код C(D,G) является линейным [п, к, dj-кодом над полем К с параметрами к > deg G + 1 — g, где g -род поля F, d> N — deg G.

Если вьшолняется неравенство

2д - 2 < deg G, (IV.9)

то в силу теоремы РиманагРоха ([9], стр.28-29) dim L(G)= deg G+l-g. Если, кроме того, degG < N, то L(G — D) = {0}, и в этом случае к = deg G + 1 -д.

Из утверждения 1) теоремы III.6 следует, что любой элемент z&F однозначно представляется в виде

z = U0(s) + Ui(z)i/ +----1- ui-i(x)y'~1, где иДж) G К(х). (IV.10)

Выясним сначала, когда щ(х)у' € L{G).

Лемма IV.l Элемент z = ^^ € F, где i > 0, 0 < j < s,

w(x) £ GP(g")[a:], (w(x), x) = 1, содержится в L(G) тогда и только тогда, когда выполняются условия:

1) любой неприводимый над GF(qn) делитель многочлена ui(x) совпадает с одним из многочленов pitk, I = 1,2, к = 1,..., ti;

2) exPpiМх) w(x) < к = 1,.., h;

3) ехриМя) w(x) < к = 1,..., t2;

4) degu>(a;) -i - jc + r > 0, где с - (у) = 7degф(х).

Выбирая теперь для каждого ] унитарный многочлен и)} (х) наибольшей степени, удовлетворяющий условиям 1)-3), получим

щ(х) = Ф[^']ш12ф](фф)дф), где

9ф) = П 92Лх) =

Пусть ^ = degwj(x)-]с + г, 0<}<з, Я, = : 0 < г <

если > 0, и В] = 0, если сГ,- = -1.

Теорема IV.3 Если для определенного равенством (IV. 7) дивизора (7 выполняется условие (IV.9), то множество В = 1)*2дВ3 является базисом пространства !/((?). Следствие 1У.1 При условии (IV.9)

т= • • • + : ¿е^(х)<с1,,1 = 0, ...,,-1)

■Шо(х) и)1(х) IV,-1(1) J

Следствие IV.2 Если выполнено условие (IV.9), то элемент г вида (IV.10) содержится в Ь{С) тогда и только тогда, когда щ(х)ух еЦв), г = 0, ...,«-1.

Теперь при условии (IV.9) найдем базис пространства — £)). Лемма IV.4 При условии (IV. 9):

а)Ь{0-0) = {(**"-*) • £,6{0.....я_1} : <1*6, },

б,) базисом пространства Ь(С — £>) является множество

Для описания пространства Ь(С)/Ь(С—0) выделим в каждом из смежных классов пространства ¿(С7) по подпространству £((?—/)) по одному представителю, которого и условимся принимать за элемент пространства Ь(в)/Ь(С - О). Тогда имеет место

Теорема 1У.4 Если для дивизора (3 вида (IV. 7) выполнено условие (IV.9), то

а) ЦО/ЦС-Б) = {ЕЙ : ***** * М = " 1}},

б) базисом пространства Ь(0)/Ь(С — И) является множество

:0< з <8-\,<1, > 0,0 < г < < А .

Для построения порождающей матрицы кода С(£>,(?) упорядочим простые дивизоры 1-ой степени поля Е следующим образом: Qa1,P1,^^■J ЯачП 1 ЧО!,/?!«) ■••) фс«,п ,/3,п£, Ой!,/?!«—11 •••, <3а,п '

где £ - любой элемент порядка в в поле , с*1,..., а,» - произвольная перестановка элементов поля ОР^п). Тогда при ТУ = qns, порождающая матрица кода С(Б, (?) будет иметь вид / Аа А0 ... А0 \ Аг А^ ... А^-1

А2 А2{ ... А2е--1

А =

\ А.-г А,-^ ... Л,.!*'-1 / где А3 - матрица размеров (^+1)хдп, полученная из первых tj+1 строк матрицы

/1 1 ... 1 \

ах а2

В =

а?

дЛ —2

V <*1

а%

Г

а;

*—2

а;

•-2

их покомпонентным умножением на вектор (гг,д,..., ), «Л* =

Следствие IV.3 Если в имеет вид (IV. 7), а Р - (IV.6), выполнено условие (1У.9) udegG < ТУ, то С(£>,б) естъ [ЛГ, /с,с/],*-код, где ТУ=дп5, ТУ-<1е§С<<КТУ-в-тах{с^ : = 0,...,в-1}.

Следствие IV.4 Если С? = гфоо, О - дивизор из (IV. 6), выполнено условие (IV. 9) и ¿е£<3 < ТУ, то С (И, в) есть [ТУ, к, -код, где ТУ = цпз, к = - д+1, 6 = N -

Замечание. Из этих двух следствий видно, что использование в качестве б дивизоров, отличных от гф(» возможно позволит строить коды такой же размерности, что и при С = гфоо, но с большим кодовым расстоянием. Однако подтверждающих эту гипотезу примеров у автора пока нет.

Построим код Гоппы С(1), (3) на простых дивизорах поля Р, заданного над А" = вР^п) уравнением у2=/(я), где f{x) — хя"/2+х, q - нечетное, п > 2 - четное.

Обозначим через А = {«1,..., а«}, з = (р!2, множество всех корней многочлена /(х), и через В = -КД.А = {¿>1,...,Как показано в

теореме III.7 поле F в этом случае имеет следующие ТУ = 2qn простых дивизоров степени 1:

О«-«

г - 1 о"/2 <Э(1) 0(2) 7 = 1 t , i — l,..., q , Wx-bj ) Чх-bj i J —i1

Q о

Обозначив: Qx-a,=Qi, Q^b, =Qвозьмем в качестве D дивизор

Тогда, в силу теоремы IV. 1, при построении кода C(D,G) с точностью до эквивалентности в качестве G достаточно рассмотреть дивизор G = rQoo, г € N.

Заметим, что здесь в определении кода участвуют лишь простые дивизоры первой степени. Поэтому его можно рассматривать как код на кривой. При доказательстве вспомогательных утверждений оказывается, что следует различать случаи:

о < [|] < |(<zn/2 + о; l(9n/2 +< [I] < " ^ ;

3°. q" - ä^i < [§] < д» ; 4". [§] > «Л

где б = 1 при четном г и е = —1 при нечетном г.

Лемма IV.10 Код C(D,G) состоит из векторов вида (ziQt),z(Q,), z(Q™),z{Q^), z(Q• • •, ziQ^)) , где, в зависимости от случаев 1°-4°, элемент z пробегает множества: 1°. Сг = (а(х): dega(x) < [§]};

2". С2 = {а(х) + Ь(х)у : dega(x) < [§] ,deg6(x) < [§] -

3°. Сг = (а(х) + Ь{х)у : dega(x) < [§] ,degb(x) < qn - qn- l};

4°. С4 = {а(х) -I- Ь(х)у : degа(х) <qn- l,deg&(x) < qn - qn¡2 - l}.

Теорема IV.5 При указанном выборе дивизоров D, G код C(D, G) является линейным [JV, k, d]g» -кодом, где N = 2qn — qn^2, а параметры k, d принимают в случаях V — 4° следующие значения: 1°. fc = [§] + 1 , d = 7V — 2 [§];

3°. к = [§] + 1 + qn - qn'2, N-r<d<N- ([§] + qn - qn'2) ; 4°. k = N,d= 1.

Заметим, что в случаях 2°, 3° при совпадении найденной верхней оценки для d с истинным значением d код C(D, G) является МДР-кодом, т.е. кодом с максимально достижимым кодовым расстоянием.

Из леммы IV. 10, содержащей описание кодов C(D,G) во всех четырех случаях, легко находятся базисы соответствующих пространств, а значит и порождающие матрицы кодов, соответствующие выбранным базисам.

Зафиксируем поле F типа IV-V. Из теоремы III.8 следует, что оно содержит N = p'qn простых дивизоров Qa,ß первой степени, где а пробегает GF(qn), а ß при фиксированном а - все решения уравнения ур' — у = hu{a).

Рассмотрим код С(Б, <?), определяемый дивизорами £>, (? на Р: ° = Е Л ^ > С = гР«, , Г > 0.

■ *а,р

Заметим, что из теоремы IV.2 следует, что при построении кодов, с точностью до эквивалентности, достаточно рассматривать именно такой дивизор (7.

Лемма IV. 14 Полной системой представителей смежных классов пространства Ь{С) по подпространству Ь(Б — в) может служить система многочленов г(х, у)=ао(х)+а1(х)у+...+арш-1(х)ур'~1 при следующих ограничениях на о,(а;);

1) если (I -1 )т < г < 1т, I = 1, ...,р* -1, то а,(а:) < (г - тг)/р*, г = 0,1,..., I - 1, ц(х) = 0,]=1,1 + 1, ...,р' - 1;

2) если (р,-1)т<г<р*дп, то dega,(x)<(r-тш)/p,, г = 0, ...,р*-1;

3) если р'яп + (I - 1)т < г < ря(д" - qu) + 1т, I = 1, ...,р' - 1, то degao(a:) < д", dego,(a;) < д" - д", г = 1,...,/ - 1,

degai(I) > (г- тз)1р', з = 1,1 + \, ...,р' - 1;

4) если г > р"(дп — д") + (р* - 1)т, то degao(a;) < дп, dega,(x) < д" -д", г = ^....р" - 1.

Используя лемму IV. 14, нетрудно построить базис пространства ¿(С)/£(£) - С).

Теорема IV.6 Рассматриваемый код С{Э, С?) является линейным [./V, к,<1\-кодом, в котором параметры к,с1 удовлетворяют следующим условиям:

1) если (/ - 1)т < г < 1т, 1 = 1,2, ...,р' - 1, то к = [*=?*] +

(р'-1+1) (?"- <*<р'чп- р^11] -1+1;

2а) если (р*-1)т<г<р*дп-т-£, где е = 0 при р'|г+т, и е=1 при р' Цг+т, то А=т+1— , р'дп-г<<1<р'дп-г +

26; если рвдп - т - е < г < р"дп, то й = г + 1 - (р* - 1)(т - 1)/2, дп _ < Й < р.дп _ Г + (р. _ 1)(т _ 1 )/2;

3) если р'д" + (/ - 1)т < г < р'(дп - д") -Нт, / = 1,2, ...,р* - 1, то * = д" + (дп - д«)(/ - 1) + П!?1 [*=?*] + р« - I,

Яп~ ["-у-^] <<1<(р*-1)д«+я"(1-1)-г+ [12^-11] + +1;

4) еслиг>р"(дп-ди)+(рв-1)т, то А;=р'дп-(р,-1)ди, (¿=ди+р*-1.

Заметим, что в случаях 3)-4) при р' = 2 полученные коды являются МДР-кодами. Это повышает интерес к рассмотрению случаев г > N, которые обычно опускаются.

ЛИТЕРАТУРА

1. Влэдуц С.Г., Манин Ю.И. Линейные коды и модулярные кривые. Итоги науки и техники, т.25, 1984, 209-257.

2. Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометриче-ские коды. Основные понятия. М.: МЦНМО, 2003.

3. Гоппа В.Д. Коды на алгебраических кривых. ДАН СССР, т.24, п.1, 1981, 170-172.

4. Степанов С.А. О нижних оценках сумм характеров над конечными полями. Дискретная математика, т.З, вып.2, 1991, 77-86.

5. Степанов С.А. Арифметика алгебраических кривых. Москва, "Наука", 1991.

6. Степанов С.А., Озбудак Ф. Расслоенные произведения гиперэллиптических кривых и геометрические коды Гоппы. Дискретная мат., т.9, вып.З, 1997, 36-42.

7. Цфасман М.А. Коды Гоппы, лежащие выше границы ВаршамовагГильберта. Проблемы передачи инф., т. 18, п.З, стр.3-6.

8. Stepanov S.A. Codes on Algebraic Curves. Kluwer Academic/Plenum Publishers, 1999.

9. Stichtenoth H. Algebraic function fields and codes. Springer-Verlag, 1993.

10. Tsfasman M.A., Vladut S.G., Zink Т. Modular curves, Shimura curves, and Goppa codes, better then Varshamov-Gilbert bound. Math.Nachr., v.109, 1982, 21-28.

Публикации автора по теме диссертации

11. Глухов М.М.-мл. Нижние оценки сумм характеров от многочленов. Тезисы докладов Международной конференции "Современные проблемы теории чисел", Тула, 1993, 36.

12. Глухов М.М.-мл. Нижние оценки сумм характеров от многочленов над конечными полями. Дискретная мат., т.6, вып.З, 1994, 136-142.

13. Глухов М.М.-мл. О канонических разложениях некоторых двучленов над GF(qm). Тезисы докладов II международной конференции "Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел", Воронеж, 1995, 41.

14. Глухов М.М.-мл. О кодах Гоппы на кривой у2 = х + хя"/2. Материалы VII Международного семинара "Дискретная математика и ее приложения", Москва, 2001, 303-304.

15. Глухов М.М.-мл. О кодах Гоппы на одном семействе полей алгебраических функций. Дискретная математика, т.13, вып.2, 2001, 14-34.

16. Глухов М.М.-мл. О кодах Гоппы на суперэллиптических кривых и полях алгебраических функций. Вестник ИКСИ, серия "К", спец. выпуск, М.:2003, 118-127.

17. Ozbudak F., Glukhov M.-jr. Codes on superelliptic curves. Turkish j. of Math., v.22, n.2, 1998, pp.223-234.

Всего пронумеровано 22 стр. Подписано к печати 24.10.2005 г. Авт. л. 0,91 Усл. печ. л. 1,37 Заказ № 241 ф/05 Тираж 70 экз.

Типография в/ч 33965

»2 0 8 35

РНБ Русский фонд

2006-4 19430

(

Введение

Глава I. Вспомогательный материал

§ 1. Сведения из теории полей алгебраических функций

§2. Сведения из теории алгебраических кривых

§3. Сведения о линейных кодах над конечными полями

Глава II. Многочлены Степанова и их обобщения

§ 1. О неприводимых делителях многочленов

§2. О корнях многочленов 45 ♦

§3. Суммы характеров от многочленов и число решений уравнений, определяющих соответствующие кривые

Глава III. О свойствах алгебраических кривых и полей алгебраических функций

§1. О свойствах алгебраических кривых

§2. О свойствах полей алгебраических функций

Глава IV. Об алгебро-геометрических кодах Гоппы

§ 1. О выборах дивизоров, определяющих коды Гоппы

§2. О кодах Гоппы в случаях I, II

§3. О кодах Гоппы в поле F в случае III

§4. О кодах Гоппы в поле F в случаях IV-V

Теория кодирования является одним из больших и хорошо развитых разделов дискретной математики. В последние годы в связи с усилением роли информатизации и увеличением объемов передаваемой на большие расстояния информации значение теории кодирования продолжает возрастать. В частности, в последние годы появилось большое число работ, посвященных применению теории кодирования в криптографии (см., например, [40], [24], [25]).

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

Развитие теории кодирования происходит в различных направлениях. Имеются работы, в которых расширяются алгебраические структуры, на которых строятся коды. Так, например, рассматриваются коды над кольцами, модулями, некоммутативными алгебрами и т.д. (см., например, [26] и обзорную работу [38]). Расширяются также и средства построения кодов. Так, например, имеются работы по построению кодов с применением линейных рекуррентных последовательностей, квазигрупп и проективных плоскостей (см., например, [33], [19], [22], [23]). В связи с этим создаются и новые методы оценки параметров соответствующих кодов. В некоторых работах указываются более тонкие оценки корректирующих свойств кодов, находятся новые параметры кодов, исследуются вероятностные характеристики корректирующих способностей кодов и т.д.

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

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

Первыми работами в этом направлении являются работы В.Д.Гоппы [16], [15], [17], в которых автор предложил строить коды на точках алгебраических кривых. В последствии это направление развивалось многими авторами. В 1984 г. появился обзор С.Г.Влэдуца и Ю.И.Манина работ по кодам на модулярных кривых (см. [3]). В настоящее время имеется ряд монографий, посвященных методам построения и исследованию свойств алгебро-геометрических кодов (см., например, [46], [44], [6]).

В.Д.Гоппа показал, что с помощью его конструкции можно строить хорошие коды, и в частности, асимптотически длинные коды информационная мера которых достигает известной границы Варшамова-Гилберта. Вскоре после этого М.А.Цфасман [32], а также независимо С.Г.Влэдуц и Т.Цинк заметили, что среди геометрических кодов Гоппы существуют коды с информационной мерой, превосходящей указанную границу, которая до этого долгое время оставалась не улучшаемой (см. [47]). При построении таких кодов использовались алгебраические кривые с большим числом точек над конечным полем, в частности, классические модулярные кривые Шимуры. При этом, как было доказано С.Г.Влэдуцем [4], [5] такие коды строятся за полиномиальное время.

В дальнейшем в ряде работ рассматривались алгоритмы декодирования (см., например, [42], [43], [49], [36]), а также коды на конкретных классах кривых (см., например, [1], [35], [45], [48]). В ряде работ хорошие коды строились в виде различных комбинаций геометрических кодов Гоппы, таких как каскадное соединение [18] и расслоенные произведения [29],

30], [31].

В связи с построением таких кодов особый интерес вызывают алгебраические кривые с большим числом точек над заданным конечным полем К, т.е. с большим числом Х-рациональных точек. Для числа N ^-рациональных точек на алгебраической кривой (при К = GF{q)) имеется известная оценка Вейля

N-(q + l)\<2g^, где д - род алгебраической кривой. В 1991 году С.А.Степановым (см. [27]) были указаны кривые, на которых эта оценка достигается. Идея С.А.Степанова была использована автором для построения более широкого класса кривых со сравнительно большим, хотя и несколько меньшим границы Вейля, числом .ЙГ-рациональных точек. Этот класс кривых над полем К = GF(q) характеристики р состоит из суперэллиптических кривых, заданных уравнением

У3 = /(*), (*) с многочленом f(x) вида:

I. + (я* + где а, 6, n, s Е N, п - нечетно, п > 1, а + b = s, (а, s) = 1, ц € К*, s\q — 1.

II. (jix + (цхУ^У (дя + (Н*п/2+1)Ь, где а, 6, n, s Е N, п - четно, п > 2, а + Ь = s, (a,s) = 1, /х G К*, — 1.

III. (^ + (Mz)«n/2)S/\ где s, n E N, s, n - четны, д E К*, — 1, q - нечетно и кривые Артина-Шрейера, заданные уравнением yp3-y = f(x), (**) с многочленом f(x) вида:

IV. (fixyin+1)/2+1 - (цх)*{п-1)/2+\ где n, s G N, n - нечетно, n > 1, fi G K*, ps — 1|q — 1.

V. - (»х)«п/2-1+\ где n, s G N, n - четно, n > 2, // G if*, pe — — 1.

Некоторые из этих кривых уже использовались для построения хороших кодов с помощью расслоенных произведений (см., например, [30]).

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

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

В главе 2 изучаются свойства указанных выше многочленов. В частности находятся оценки для сумм мультипликативных и аддитивных характеров от этих многочленов, число их корней в полях GF(qn) и GF(q), число неприводимых делителей заданных степеней. В заключение находятся формулы для числа рациональных точек на соответствующих алгебраических кривых.

В главе 3 изучаются свойства соответствующих аффинных кривых и полей алгебраических функций над полем GF(qn). Для всех простых дивизоров рассматриваемых полей алгебраических функций указываются степени, относительные степени и индексы ветвления, приводятся формулы для вычисления значений функций нормирования.

В главе 4 исследуются коды Гоппы, построенные в указанных полях щ алгебраических функций над полем GF(qn). Находятся базисы и порождающие матрицы этих кодов, находятся или уточняются основные параметры этих кодов.

На защиту выносятся следующие результаты.

1. Описание /^-рациональных точек рассматриваемых кривых.

2. Описание неприводимых над полями GF(q) и GF{qn) делителей многочленов I-V, вывод формул для числа таких делителей заданной степени.

3. Теоремы о сужении выбора пар дивизоров, задающих алгебро-геометрические коды в суперэллиптических полях алгебраических функций и расширениях Артина-Шрейера поля GF{qn){x). щ 4. Теоремы о базисах и основных параметрах кодов, построенных в указанных полях алгебраических функций с многочленом f(x) вида I-V.

Эти результаты расширяют имеющийся запас линейных кодов и позволяют строить новые линейные коды большой длины с достаточно хорошими корректирующими свойствами. Основные результаты диссертации докладывались на II Международной конференции "Теория чисел и ее приложения"(Тула, 1997 г.), на VII Международном семинаре "Дискретная математика и ее приложения"(Москва, 2001 г.), на V Международной конференции "Алгебра и теория чисел: современные проблемы * и приложения"(Тула, 2003 г.), на конференции Академии ФСБ и Института криптографии, связи и информатики, посвященой памяти академика А.Н. Колмогорова (Москва, 2003 г.) и опубликованы в работах РН12],[41].

Заключение.

Диссертация посвящена построению и исследованию линейных алгебро-геометрических кодов на Х-рациональных точках алгебраических кривых и на простых дивизорах полей алгебраических функций, заданных некоторыми полиномиальными уравнениями F(x,y) = 0 над конечным полем К = GF(qn) характеристики р.

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

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

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

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

Список основных обозначений. ехРр(ж) aix) — naax{£ £ No : р(ж)'|а(ж)}, для р(х),а(х) £ К[х]. ехр2 k = max{Z £ N0 : 2l\fc}, для A; 6 N. if (я) - поле рациональных функций над полем К. К(х,у) - поле алгебраических функций (простое алгебраическое расширение поля К(х)).

Уравнение (*): ys = f(x) с многочленом f(x) £ GF(qn)[x] вида (типа):

I. (дх + Ы^'У^ + М''"""2)6, где а, 6, n, s £ N, п - нечетно, п > 1, а + b = s, (а, s) = 1, /л £ К*, s\q — 1.

II. {fix + {»хуп/2~У (fix + (мя)«п/2+1)6, где а, 6, п, 5 G N, п - четно, п > 2, а + b = s, (а, s) = 1, д £ if*, s\q — 1.

III. (^ + (H?n/2)S/2, где s, n G N, s, n - четны, /л £ К*, s\q — 1,

Уравнение (**) yp' — у = f(x) с многочленом /(ж) над полем GF(qn) характеристики р вида (типа):

IV. - W(n1)/2+1, где n, s £ N, п - нечетно, п > 1, /л £ К*, ps — l\q — 1.

V. (fix)«n/2+1+1 - (H*n/21+1, где n, s € N, n - четно, n > 2, /х G if*, — 1|<? — 1. g - род соответствующей кривой или поля алгебраических функций; = ж9("+")/2 + ж, it = ±1 при нечетном п или и = О при четном п. = (px)q(n+u)/2+1 — (1лх)д(п ")/2+1; и = 1 при нечетном п > 1 или и — 2 при четном п > 2.

D,G- дивизоры, определяющие алгебро-геометрический код C(D, (?).

1. Барг A.M., Кацман Г.Л., Цфасман М.А. Алгебро-геометрические коды на кривых малых родов. Проблемы передачи инф., т.23, п.1,1987, 42-46.

2. Виноградов И.М. Основы теории чисел. М.:Наука, 1972.

3. Влэдуц С.Г., Манин Ю.И. Линейные коды и модулярные кривые. Итоги науки и техники, т.25, 1984, 209-257.

4. Влэдуц С.Г. Модулярные кривые и коды с полиномиальной сложностью построения. Депонировано.

5. Влэдуц С.Г., Кацман Г.Л., Цфасман М.А. Модулярные кривые и коды с полиномиальной сложностью построения. Проблемы передачи инф., т.20, п.1, 1984, 47-55.

6. Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометрические коды. Основные понятия. М.: МЦНМО, 2003.

7. Глухов М.М.-мл. Нижние оценки сумм характеров от многочленов. Тезисы докладов Международной конференции "Современные проблемы теории чисел", Тула, 1993, 36.

8. Глухов М.М.-мл. Нижние оценки сумм характеров от многочленов над конечными полями. Дискретная мат., т.6, вып.З, 1994, 136-142.

9. Глухов М.М.-мл. О канонических разложениях некоторых двучленов над GF{qm). Тезисы докладов II международной конференции "Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел", Воронеж, 1995, 41.

10. Глухов М.М.-мл. О кодах Гоппы на кривой у2 = х + хдП/2. Материалы VII Международного семинара "Дискретная математика и ее приложения", Москва, 2001, 303-304.

11. Глухов М.М.-мл. О кодах Гоппы на одном семействе полей алгебраических функций. Дискретная математика, т.13, вып.2, 2001, 14-34.

12. Глухов М.М.-мл. О кодах Гоппы на суперэллиптических кривых и полях алгебраических функций. Вестник ИКСИ, серия "К", спец. выпуск, М.:2003, 118-127.

13. Гонсалес С., Коусело Е., Марков В., Нечаев А. Параметры рекурсивных МДР-кодов. Дискретная мат., т. 12, вып.4, 2000, 3-24.

14. Гоппа В.Д. Рациональное представление кодов и (L, д)-коды. Проблемы передачи информации, т.7, п.З, 1971, 41-49.

15. Гоппа В.Д. Коды на алгебраических кривых. ДАН СССР, т.24, п.1, 1981, 170-172.

16. Гоппа В.Д. Алгебро-геометрические коды. Изв. АН СССР, Сер.Мат., т.46, п.4, 1982, 762-781.

17. Гоппа В.Д. Коды и информация. УМН, т.39, п.1, 1984, 77-120.

18. Зиновьев В.А., Эриксон Т. О каскадных равновесных кодах, превышающих границу Варшамова-Гильберта. Проблемы передачи инф., т.21, п.1, 1985, 109-111.

19. Гонсалес С., Коусело Е., Марков В., Нечаев А. Рекурсивные МДР-коды и рекурсивно-дифференцируемые квазигруппы. Дискретная мат., т. 10, вып.2, 1998, 3-29.

20. Лидл Р., Нидеррайтер Г. Конечные поля. Москва, "Мир", 1988.

21. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. Москва, "Связь", 1979.

22. Нечаев А.А. Линейные коды и полилинейные реккурентные последовательности над конечными кольцами и квази-фробениусовыми модулями. Докл.Ак.Наук России, 345, 1995, 229-254.

23. Нечаев А.А., Кузьмин А.С., Марков В.Т. Линейные коды над конечными кольцами и модулями. Фундаментальная и прикладная математика, 3, №1, 1996, 195-254.

24. Сидельников В.М., Шестаков С.О. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона. Дискретная математика, т.4, вып.З, 1992, 57-63.

25. Сидельников В.М. Открытое шифрование на основе двоичных кодов Рида-Маллера. Дискретная математика, т.6, вып.2, 1994, 3-20.

26. Сидельников В.М. Квантовые коды и абелевы подгруппы экстраспециальной группы. Проблемы передачи информации, т.38, п.З, 2002, 34-44.

27. Степанов С.А. О нижних оценках сумм характеров над конечными полями. Дискретная математика, т.З, вып.2, 1991, 77-86.

28. Степанов С.А. Арифметика алгебраических кривых. Москва, "Наука", 1991.

29. Степанов С.А. Коды на расслоенных произведениях гиперэллиптических кривых. Дискретная мат., т.9, вып.1, 1997, 83-94.

30. Степанов С.А., Озбудак Ф. Расслоенные произведения гиперэллиптических кривых и геометрические коды Гоппы. Дискретная мат., т.9, вып.З, 1997, 36-42.

31. Степанов С.А., Шалалфех М.Х. Коды на расслоенных произведениях кривых Артина-Шрейера. Дискр. мат., т. 13, вып.2, 2001, 3-13.

32. Цфасман М.А. Коды Гоппы, лежащие выше границы Варшамова-Гильберта. Проблемы передачи инф., т. 18, п.З, стр.3-6.

33. Couselo Е., Gonzales S., Markov V., Nechaev A. Recursive MDS-codes and recursively differetiable fc-quasigroups. Proc.Sixth.Intern.Workshop on Algebraic and Combin. Coding Theory. Pskov, Russia, 1998, 78-84.

34. Couselo E., Gonzales S., Markov V., Nechaev A. Recursive MDS-codes. Proc. Workshop on Coding and Criptogr. Paris, Prance, 1999, 271-278.

35. Driencourt Y., Michon J.F. Elliptic codes over fields of characteristic 2. J.Pure Appl.Algebra, v.45, n.l, 1987, 15-39.

36. Justensen J., Larsen K.J., Jensen H.E., Havemose A., Hoholdt T. Construction and decoding of a class of algebraic-geometric codes. IEEE Tr.Inf.Th., v.35, n.4, 1989, 811-821.

37. KasamiT. An upper bound on kfniox affine-invariant codes which fixed d/n. IEEE Trans.Inform.Theory, 1969, v.15, n.9, 174-176.

38. Niederreiter H. Knapsack-Type Cryptosystems and Algebraic Coding Theory. Probl. Control and Inform Theory, v. 15, 1986, pp. 19-34.

39. Ozbudak F., Glukhov M.-jr. Codes on superelliptic curves. Turkish j. of Math., v.22, n.2, 1998, pp.223-234.

40. Pellican R. On a decoding algorithm for codes on maximal curves. IEEE Tr.Inf.Th., v.35, n.6, 1989, 1228-1232.

41. Skorobogatov A.N., Vladut S.G. On the decoding of algebraic-geometric codes. IEEE Tr.Inf.Th., v.36, n.5, 1990, 1051-1060.

42. Stepanov S.A. Codes on Algebraic Curves. Kluwer Academic/Plenum Publishers, 1999.

43. Stichtenoth H. A note on Hermitean codes over GF(q2). IEEE Tr.Inf.Th., v.33, n.4, 1987, 605-609.

44. Stichtenoth H. Algebraic function fields and codes. Springer-Verlag, 1993.

45. Tsfasman M.A., Vladut S.G., Zink T. Modular curves, Shimura curves, and Goppa codes, better then Varshamov-Gilbert bound. Math.Nachr., v.109, 1982, 21-28.

46. Tsfasman M.A., Vladut S.G. Geometric Approach to Higher Weights. IEEE Tr.Inf.Th., v.41, n.6, 1995, 1564-1588.

47. Vladut S.G. On the decoding of algebraic-geometric codes over Fq for q > 16. IEEE Tr.Inf.Th., v.36, n.6, 1990, 1461-1463.