Содержание к диссертации
Введение
1 Алгеброгеометрические коды 9
1.1 Введение в алгебраическую геометрию 10
1.1.1 Аффинные и проективные многообразия 10
1.1.2 Локальное кольцо в точке 15
1.1.3 Дивизоры. Линейное пространство, заданное на дивизоре.
1.2 Коды на кривых 19
1.3 Некоторые алгеброгеометрические коды
1.3.1 Коды рода ноль 20
1.3.2 Эллиптические коды 20
1.3.3 Эллиптические коды Грайсмера 21
1.3.4 Коды Эрмита 24
1.4 Заключение и выводы по главе 25
2 Множества, свободные от покрытий 26
2.1 Определения и обозначения 28
2.2 МСП и коды, исправляющие ошибки 30
2.2.1 Построение МСП на кодах, исправляющих ошибки 2.2.2 Параметры МСП на кодах Рида-Соломона и эллиптических кодах 32
2.2.3 Анализ МСП, построенных на кодах Рида-Соломона 34
2.2.4 Сравнение МСП, построенных на кодах Рида-Соломона
и эллиптических кодах 39
2.2.5 Примеры 41
2.3 Использование МСП 43
2.3.1 Построение каскадных конструкций 43
2.3.2 Способ применения и использование МСП в системах связи 44
2.3.3 Способ применения и использование МСП для задачи распознавания образов 44
2.4 Заключение и выводы по главе 46
3 Быстрые вычисления на кривой в поле характеристики 3 47
3.1 Эллиптические кривые 48
3.2 Группа точек на эллиптической кривой 49
3.3 Кривые, заданные над рт, где р ф 2,3 54
3.4 Кривые, заданные над полем характеристики 2 55
3.5 Арифметика эллиптических кривых, заданных над полем характеристики 3 56
3.6 Алгоритмы умножения скаляра на точку 3.6.1 Алгоритм, использующий двоичное представление скаляра 57
3.6.2 Алгоритм, использующий сбалансированное двоичное представление скаляра 3.6.3 Метод окна 59
3.6.4 Совместное умножение скаляров на точки 61
3.6.5 Использование эндоморфизмов для быстрых вычислений 62
3.6.6 г-аддическое представление скаляра 65
3.6.7 Метод разбиения 69
3.7 Умножение скаляра на точку в поле характеристики 3 70
3.7.1 Представление скаляра 70
3.7.2 Уменьшение длины последовательности 73
3.7.3 Тернарное знаковое представление 75
3.7.4 Использование метода разделения 76
3.7.5 Обобщающий метод 78
3.8 Заключение и выводы по главе 78
Заключение 79
- Введение в алгебраическую геометрию
- Некоторые алгеброгеометрические коды
- МСП и коды, исправляющие ошибки
- Группа точек на эллиптической кривой
Введение к работе
Актуальность темы. В настоящее время получили широкое распространение и продолжают быстро развиваться области, связанные с обработкой и передачей данных в беспроводных сетях, системах хранения данных, космической связи.
Важной задачей является повышение эффективности существующих методов передачи и хранения информации. В том числе и повышение эффективности методов помехоустойчивого кодирования, используемых в этих системах. Одним из способов повышения эффективности методов помехоустойчивого кодирования является поиск и построение оптимальных кодов, а именно кодов, лежащих на верхних границах существования.
В последние десятилетия методы алгебраической геометрии нашли применение в теории помехоустойчивого кодирования. Алгеброгеометрические коды представляют собой широкий класс эффективных кодов, исправляющих ошибки. Среди кодов, построенных на модулярных кривых, были найдены коды, параметры которых лежат выше асимптотической границы Варшамова-Гильберта. Существуют алгеброгеометрические коды, близкие к верхним границам существования.
Для реализации процедур построения алгеброгеометрических кодов необходимо быстро вычислять различные преобразования над точками кривой. Поэтому задача быстрых преобразований является актуальной.
Как качество алгеброгеометрических кодов, так и эффективность вычислительных алгоритмов, использующих кривые, зависит от выбора соответствующей кривой. Однако вопросы выбора кривых для указанных приложений остаются в значительной степени открытыми. Несмотря на многочисленные работы в этом направлении, в общем случае задача выбора "оптимальной" кривой остается нерешенной.
Основной целью работы разработка и исследование методов использования эллиптических кривых в задачах избыточного кодирования информации.
Методы исследования. Для достижения поставленной цели в работе рассматриваются следующие основные задачи:
построение оптимальных помехоустойчивых кодов,
построение лучших из известных множеств, свободных от покрытий,
построение алгоритмов быстрых вычислений на эллиптических кривых.
Для решения поставленных задач используются методы алгебраической теории кодирования, алгебры, алгебраической геометрии, комбинаторики и теории сложности алгоритмов.
Научная новизна работы заключается в следующем:
предложен метод построения подкласса оптимальных алгеброгеометрических (эллиптических) кодов;
найдено истинное расстояние для построенного подкласса оптимальных эллиптических кодов;
с помощью эллиптических кодов построены множества, свободные от покрытий, параметры которых будут лучшими из известных;
предложен новый алгоритм для умножения скаляра на точку в поле
характеристики 3, выигрывающий по сложности у известных методов.
Практическая ценность и реализация результатов. Практическая ценность работы заключается в том, что в ней предложен способ построения нового оптимального подкласса g-ичных кодов. Использование таких кодов позволяет улучшить существующие системы передачи информации. Кроме того, были предложены эффективные методы умножения скаляра на точку на эллиптической кривой, обладающие преимуществами перед известными методами.
Публикации. Основные результаты работы отражены в 8 публикациях. Из них 2 работы опубликованы в журналах, входящих в список ВАК.
Основные положения, выносимые на защиту:
подкласс оптимальных алгеброгеометрических (эллиптических) кодов, лежащих на верхней границе существования;
метод определения истинного расстояния и размерности для кодов из полученного подкласса оптимальных кодов;
множества, свободные от покрытий, на основе алгеброгеометрических (эллиптических) кодов.
Структура работы. Диссертация состоит из введения, трех глав, заключения и списка использованной литературы. Работа изложена на 93 страницах. Основное содержание работы включает И рисунков, 8 таблиц и 13 алгоритмов. Первая глава посвящена сведениям, необходимым для построения алгеброгеометрических кодов. Показаны различные конструкции алгеброгеометрических кодов и доказано, что подкласс эллиптических кодов будет лежать на границе Грайсмера.
Вторая глава посвящена вопросам использования кодов, исправляющих ошибки, для построения множеств, свободных от покрытий. Кроме того, произведено сравнение множеств, свободных от покрытий, построенных на эллиптических кодах и кодах Рида-Соломона.
Третья глава посвящена вопросам быстрого умножения скаляра на точку.
В заключении сформулированы основные результаты работы.
Введение в алгебраическую геометрию
В 1977 году В.Д. Гоппа показал как, используя аппарат теории полей алгебраических функций, можно построить коды, исправляющие ошибки [8]. В 1981 году для построения кодов В.Д. Гоппа предложил использовать аппарат алгебраической геометрии [9]. В 1982 году вышла работа М.А. Цфасмана, С.Г. Влэдуца, Т. Цинка [101], в которой было показано, что существуют алгеброгеометрические коды, лежащие выше асимптотической границы Варшамова-Гильберта. Так в теории кодирования появилось новое направление - алгеброгеометрические коды.
Несмотря на значительное число работ в области построения кодов, задача построения оптимальных кодов остается по-прежнему актуальной. В данной главе будет исследован вопрос о поиске оптимальных алгеброгеомет-рических кодов, а в качестве критерия оптимальности будет использована граница Грайсмера.
На сегодняшний день алгеброгеометрические коды используются для построения комбинаторных объектов [82, 103, 31], имеющих широкое практическое значение, более детально этот вопрос будет рассмотрен в следующей главе.
В параграфе 1.1 будет рассмотрено краткое введение в алгеброгеометрические коды. В параграфе 1.2 представлен общий подход к построению алгебро геометрических кодов. В параграфе 1.3 рассмотрены некоторые конструкции алгеброгеометрических кодов, а также показано, что среди алгеброгеометри-ческих кодов есть оптимальные, лежащие на верхней границе Грайсмера.
Определение 1 Поле F называется алгебраически замкнутым, если каждый полином из [х] имеет хотя бы один корень в F.
Например, конечное поле F2 алгебраически не замкнуто, поскольку х2 + х + 1 не имеет корней над F2. Поле рациональных чисел Q и поле действительных чисел R не замкнуты, поскольку х2 + 1 не имеет корней над ними. Напротив, поле комплексных чисел С замкнуто.
Определение 2 Алгебраическим замыканием поля F называется поле , такое что F С F и удовлетворяет следующим свойствам: алгебраически замкнуто, если существует поле , такое что С F С F, то = . Другими словами алгебраическое замыкание поля F - это наименьшее замкнутое поле, содержащее F.
Теорема 1 (теорема 3.4, [102]) Для каждого поля с точностью до изоморфизма существует уникальное алгебраическое замыкание.
Например, алгебраическим замыканием поля действительных чисел R является поле комплексных чисел С. Алгебраическим замыканием конечного поля характеристики простого числа р станет бесконечное поле, которое содержит копию поля рп для каждого положительного целого п.
Пусть Fg - это конечное поле, состоящее из q элементов, и д его алгебраическое замыкание. Предположим, что n-мерное аффинное пространство заданное над полем Fд - это множество An(Fg) = {(ао, а\,..., ап_і) : аі б Fg}.
Элемент P = (ао,аі,...,а„_і) Є Ап называется точкой аффинного пространства, а ее компоненты называются аффинными координатами.
Например, рассмотрим пространство A2(F2). Пусть V = Z(y2 — х), тогда %[V] будет состоять из {A + By} , где Л, В Є ІгМ- Тогда F2(V) будет алгебраическим расширением поля функций 2(х), осуществленного с помощью добавления элемента у, связанного с х соотношением у2 = х.
Теперь рассмотрим случай проективных координат. Рассмотрим полином у2 — х3 - х — 2 в точке (1 : 2 : 1) Є P2(F5), где первой, второй и третьей координате соответствуют х, у, z соответственно. Данный полином будет равен нулю при выборе координат точки (1,2,1), но при выборе координат точки 2(1,2,1) = (2,4,2) полином у2 — х3 — х - 2 должен быть так же равен нулю, поскольку, согласно определению 3 точки (1,2,1) и (2,4,2) рассматриваются как одна точка в проективном пространстве.
Определение 14 Пусть t пораждающий элемент идеала Мр. Тогда любой элемент кольца z Є Op может быть уникально представлен в виде z = utm, где и — это единица кольца, и т Є Ъ. Если т 0, то Р — это ноль кратности т функции z. Если т 0; то Р — это полюс кратности т функции z. Пусть т = ordp(,z) = vp(z).
Некоторые алгеброгеометрические коды
В данной главе рассматриваются множества, свободные от покрытий (МСП). Впервые этот объект был введен Каутцом (Kautz) и Синглтоном (Singleton) в 1964 году в работе [69]. Каутц и Синглтон назвали этот объект "superimposed codes".
В общем случае под МСП можно понимать множество векторов, в котором объединение любых г векторов не покроет полностью никакой другой вектор из множества.
Каутц и Синглтон предложили использовать МСП для задачи связи в многоканальных системах. В этой задаче вектор МСП задает для каждого пользователя множество каналов, по которым пользователь производит параллельную передачу. Причем если передача производится одновременно несколькими пользователями, и их число не превышает некоторый порог, то каждый пользователь осуществит бесконфликтную передачу, хотя бы по одному из каналов.
Позднее введенный Синглтоном и Каутцом объект рассматривался в работах [50, 51, 10, 52, 80, 74].
В 1985 году Ердош [Erdos], Франкл [Prankl] и Фюреди [Fiiredi] [55] ввели множества, свободные от покрытий, как комбинаторный объект. В 1987 году в работе Хванга [Hwang] [66] МСП были введены для зада чи построения плана экспериментов. Эта задача появилась еще во времена второй мировой войны и была связана с необходимостью построения схем тестирования большого количества образцов крови. Целью являлось построение плана с минимальным количеством экспериментов, с помощью которого можно было бы протестировать максимальное количество образцов и выявить среди них дефектные.
В 1997 году в работах [44, 43, 68] было предложено использовать МСП для задач распознавания образов. Такие приложения возникают при анализе текстов поисковыми серверами и в системах коррекции орфографии. Например, если слово написано с ошибкой вида перестановки двух соседних символов, то составляя из слова код, полученный наложением кодов символов, построенных как вектора МСП, получим некоторый код, который будет равен коду полученному из слова, если бы оно было написано без ошибки. Далее, используя таблицу соответствия кодов слов и самих слов, можно исправить ошибку.
Существуют различные способы построения МСП: на схемах, латинских квадратах и кодах, исправляющих ошибки [69]. С помощью границы существования МСП, приведенной в работе [10], можно показать, что МСП, построенные с помощью кодов Рида-Соломона, будут лежать близко от границы. Поэтому параметры МСП на кодах Рида-Соломона считаются лучшими из известных. Соответственно задача построения подоптимальных МСП на кодах, исправляющих ошибки, лучших чем коды Рида-Соломона, является актуальной.
В данной главе будет проведено сравнение параметров МСП, построенных с помощью кодов Рида-Соломона, и МСП, построенных на эллиптических кодах Грайсмера [21]. В параграфе 2.1 вводятся основные определения и обозначения. В параграфе 2.2 производится сравнение МСП, построенных с помощью кодов Рида-Соломона, и МСП, построенных с помощью эллиптических кодов, введенных в предыдущей главе. В параграфе 2.3 приводятся примеры использования МСП.
МСП и коды, исправляющие ошибки
В данной главе рассматривались кодовые методы построения множеств свободных от покрытий. Основной результат главы может быть сформулирован следующим образом: использование эллиптических кодов может делает выбор параметров множеств, свободных от покрытий, более гибким по сравнению с множествами, свободными от покрытий, построенными на кодах Рида-Соломона. То есть существуют точки, в которых множества свободные от покрытий, построенные на эллиптических кодах, лучше чем множества, свободные от покрытий, построенные на кодах Рида-Соломона.
Решение в общем виде задачи о том, когда множества, свободные от покрытий, построенные на кодах Рида-Соломона, лучше эллиптических кодов Грайсмера остается открытым, в данной работе было преложено решение частной задачи.
Быстрые вычисления на кривой в поле характеристики 3 В 1985 году Нилом Коблицом [Koblitz] и Виктором Миллиром [Miller] [71, 78] независимо было предложено использовать эллиптические кривые для криптосистем с открытым ключом. Со второй половины 90х годов криптосистемы на эллиптических кривых стали приобретать важное практическое значение. Эффективность криптосистем на эллиптических кривых зависит от быстроты реализации арифметики, заданной на точках кривой. Быстрота реализации арифметики зависит от: эффективности реализации полевых операций, эффективности реализации операций сложения точек на кривой, эффективности реализации умножения скаляра на точку.
Задача умножения скаляра на точку состоит в быстром вычислении следующей суммы
На сегодняшний день хорошо исследованными можно считать методы быстрого умножения скаляра на точку в полях характеристики 2 [64, 32]. Последние несколько лет наблюдается интерес к методам быстрого умножения скаляра на точку в полях характеристики 3 [88, 81], xnj связано с новым направлением эллиптической криптографии [45]. Данная глава посвящена адаптации известных алгоритмов для поля характеристики 3.
Данная глава имеет следующую структуру. В параграфах 3.1-3.5 вводится группа на эллиптической кривой и приводятся необходимые формулы для сложения точек, в параграфе 3.6 приводятся известные алгоритмы для умножения скаляра на точку. В параграфе 3.7 рассматриваются алгоритмы умножения скаляра на точку в поле характеристики 3.
Рассмотрим однородное уравнение кривой Y2Z + axXYZ + azYZ2 = X3 + a2X2Z + a4XZ2 + a6Z\ (3.1) где ai, аг, «Зі Й4) «6 Є Wg. Такое уравнение называется эллиптическим уравнением, заданным в форме Вейрштрасса. Множество всех Fg-рациональных точек Р Є f2(Fq), удовлетворяющих уравнению (3.1), называют эллиптической кривой и обозначают как E(q). Точка Р = (0:1:0) будет единственной точкой на бесконечности, которую высечет кривая (3.1), обозначим еч, за О. Для удобства будем рассматривать кривую (3.1) в аффинных координатах. Пусть х = , у = j, тогда уравнение (3.1) будет выглядеть как у2 + а\ху + а$у = х3 + а2х2 + сцх + а6. (3.2)
На кривой (3.2) будут лежать точки из множества A2(Fg) вместе с точкой О. Будем рассматривать только те кривые, у которых нет особых точек, то есть кривые с дискриминантом Д ф 0. Для кривой (3.2) дискриминант Д может быть определен как [32]:
Зададим группу на эллиптической кривой, для чего определим операцию сложения двух точек кривой. Определим как обратную к Р = (x\,yi) точку, которая получится при пересечении кривой с прямой перпендикулярной оси абсцисс, проведенной через точку Р = (x\,yi) рисунок 3.1. Координаты обратной точки могут быть получены как — Р = (х\, —у\ — а\Х\ — аз).
Определим сумму двух точек на кривой (3.2) две точки Р\ = (#i,f/i) и Рг — ІХ2,У2), так что х\ Ф Х2 и, проведя через них прямую, вычислим координаты третьей точки Pg = {х зіУг) пересечения нашей прямой с кривой. Эти координаты будут удовлетворять следующей системе уравнений рисунок 3.2:
Определим формально, что сумма Р + (—Р) = О. То есть прямая перпендикулярная оси абсцисс высекает на кривой точку Р, обратную к ней (-Р) и точку на бесконечности О.
Таким образом задается операция сложения на множестве точек эллиптической кривой. Покажем теперь, что множество точек, лежащих на кривой, задает группу. 1. Замкнутость по определенной операции следует из того, что для суммы любых двух Fg-рациональных точек результирующая будет также q-рациональной. Это легко показать, анализируя формулы сложения двух точек. 2. В качестве обратного к точке Р = (xi,yi) выберем — Р = (хі,—уі — а\Х\ - аз). 3. В качестве нейтрального элемента определим точку О, поскольку Р + О = О + Р = Р. Это следует из сделанного выше формального определения. 4. Доказательство ассоциативности может быть найдено в книге [87]. 5. Группа коммутативна, поскольку для вычисления суммы P + Q используется та же прямая, что и для вычисления точки Q + Р. Таким образом над множеством точек на эллиптической кривой задается группа.
Группа точек на эллиптической кривой
Алгоритм, использующий двоичное представление скаляра, это наиболее простой метод, который может использоваться для умножения скаляра на точку. Представим к в двоичной системе счисления к = (ki-i,...,ki,ko)2, где / = "log2(A;) . Тогда будет справедлив алгоритм 1.
Оценим сложность алгоритма 1. Поскольку на каждой итерации алгоритма происходит удвоение точки (2Р), то общее количество операций удвоения точки составит /. Сложение точек происходит, только если на позициях двоичного представления к стоят единицы. В среднем число единиц в двоичном представлении к составит . Тогда количество операций, выполняемых алгоритмом составит: A + ID, (3.29) где Л - сложность сложения двух точек, D - сложность удвоения. Из этого алгоритма можно выделить три стратегии ускорения: можно укоротить представление, например, использовать представление по другому основанию; можно уменьшить количество единиц в двоичном представлении к. Это снизит количество сложений в предложенном алгоритме; можно снизить сложность удвоения за счет использования более легкой операции. Среднее количество сложений может быть уменьшено. Ранее отмечалось, что вычисление точки обратной к данной вычислительно просто. Этим фактом можно воспользоваться. Перейдем от просто двоичного представления к к сбалансированному двоичному представлению k = Y h- 2\ где / Є {0,±1}.
Для того чтобы получить такое представление, можно последовательно заменять встречающиеся в двоичной последовательности подряд идущие единицы 11 на 10 - 1. Например,
Сбалансированное двоичное представление имеет следующие свойства: произведение двух подряд идущих символов последовательности будет нулевым; длина последовательности составит I = [log2(A;)] + 1; среднее количество единиц в векторе , в худшем случае количество единиц составит .
Двоичное сбалансированное представление может быть посчитано с помощью следующего алгоритма.
В работе [61] был предложен метод умножения скаляра на точку, где главная идея метода состояла в использовании быстрых эндоморфизмов.
Пусть Е — это эллиптическая кривая, определенная над рт. Эндоморфизм ф на кривой Е(рт) — это отображение ф:Е Е, такое что ф{0) = О, ф{Р) = (д(Р), h(P)) для всех Р Є Е{рт) и ф{Рг + Р2) = Ф{Р\) + Ф(Р2) Для всех Рі, Р2 Є Е(рт).
Характеристическим уравнением эндомофризма называется нормированный полином f{x) є Z[x] минимальной степени такой что f$)(P) = О. Рассматривая эллиптическую кривую Е, определенную над q можно определить эндоморфизм { (х,у) (W). (3-35)
Это эндоморфизм на Е, который часто называют эндоморфизмом Фро-бениуса. Характеристическим уравнением будет полином х2 — tx + q, где t = q-\-l — пи п — это количество точек на кривой E(q) [87].
Рассматривая эллиптическую кривую Е, определенную над q, для любого целого т можно определить эндоморфизм
Похожие диссертации на Алгеброгеометрические методы избыточного кодирования информации
