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

• Глухов, Михаил Михайлович
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Глухов, Михаил Михайлович

Введение

Глава 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, (?).

Список литературы диссертационного исследования кандидат физико-математических наук Глухов, Михаил Михайлович, 2005 год

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.