Код Гоппы

Код Гоппы — это класс линейных кодов коррекции ошибок, построенных на основе алгебраических кривых над конечными полями. Относятся к алгебраическим геометрическим кодам, в которых каждому кодовому слову сопоставляется набор значений рациональных функций на точках кривой. Коды Гоппы обладают свойством достижения границы Синглтона (то есть являются кодами с максимальным расстоянием, MDS-кодами) для широкого класса кривых, что делает их теоретически оптимальными по соотношению скорости и корректирующей способности. Названы в честь советского и российского математика Валерия Денисовича Гоппы, впервые описавшего их в 1970-х годах.

История

Идея кодирования с использованием алгебраических кривых восходит к работам французского математика Клода Шеннона и советского математика Владимира Александровича Котельникова, заложивших основы теории информации и помехоустойчивого кодирования. Однако непосредственное построение кодов на основе алгебраических кривых было предложено Валерием Гоппой в 1970-х годах. В 1977 году он опубликовал статью «Коды на алгебраических кривых», в которой впервые описал конструкцию, использующую рациональные функции на алгебраической кривой над конечным полем. В 1981 году Гоппа совместно с советским математиком Алексеем Николаевичем Паршиным обобщил эту конструкцию на произвольные алгебраические кривые, что привело к созданию теории алгебраических геометрических кодов.

В 1982 году независимо от Гоппы аналогичные идеи были развиты американским математиком Майклом Циммерманом, который ввёл понятие «кодов на кривых». Однако приоритет в построении и систематическом изучении кодов Гоппы остаётся за Валерием Гоппой. В 1980-х годах теория кодов Гоппы была существенно развита работами французского математика Жиля Кадио, который показал, что коды Гоппы могут достигать границы Синглтона для кривых с достаточно большим родом. В 1990-х годах коды Гоппы нашли применение в криптографии, в частности в постквантовых криптосистемах.

Определение

Пусть \( \mathbb{F}_q \) — конечное поле из \( q \) элементов, \( X \) — неособая алгебраическая кривая рода \( g \) над \( \mathbb{F}_q \). Пусть \( P_1, P_2, \dots, P_n \) — различные рациональные точки на \( X \), и \( D = P_1 + P_2 + \dots + P_n \) — дивизор, состоящий из этих точек. Пусть \( G \) — дивизор на \( X \), носитель которого не пересекается с носителем \( D \). Тогда кодом Гоппы \( C_L(D, G) \) называется линейный код длины \( n \) над \( \mathbb{F}_q \), состоящий из векторов вида:

\[ (f(P_1), f(P_2), \dots, f(P_n)) \in \mathbb{F}_q^n, \]

где \( f \) пробегает множество рациональных функций на \( X \) таких, что дивизор \( (f) + G \) является эффективным (то есть \( f \in L(G) \), где \( L(G) \) — пространство рациональных функций с полюсами, ограниченными дивизором \( G \)).

Размерность кода \( C_L(D, G) \) равна \( \dim L(G) - \dim L(G - D) \), а минимальное расстояние \( d \) удовлетворяет неравенству:

\[ d \ge n - \deg(G) + 2g - 2. \]

Если \( \deg(G) < n \), то код является нетривиальным и может исправлять ошибки. В случае, когда \( \deg(G) > 2g - 2 \), размерность кода равна \( \deg(G) - g + 1 \), а минимальное расстояние достигает границы Синглтона: \( d = n - \deg(G) + g \).

Свойства

Граница Синглтона

Коды Гоппы являются MDS-кодами (кодами с максимальным расстоянием) для кривых с достаточно большим родом. Это означает, что для заданной длины \( n \) и размерности \( k \) код достигает максимально возможного минимального расстояния \( d = n - k + 1 \). Для кодов Гоппы это свойство выполняется, если \( \deg(G) > 2g - 2 \) и \( \deg(G) < n \).

Корректирующая способность

Коды Гоппы могут исправлять до \( \lfloor (d - 1)/2 \rfloor \) ошибок. Благодаря алгебраической структуре, существуют эффективные алгоритмы декодирования, основанные на вычислении синдромов и решении систем линейных уравнений. Сложность декодирования полиномиальна относительно длины кода.

Связь с другими кодами

Коды Гоппы обобщают классические коды Рида — Соломона, которые являются частным случаем кодов Гоппы на кривой рода 0 (проективной прямой). Коды Рида — Соломона — это коды Гоппы на кривой \( \mathbb{P}^1 \) с дивизором \( G = (k-1) \cdot \infty \). Коды Гоппы также включают в себя коды БЧХ (Боуза — Чоудхури — Хоквингема) как подкласс.

Классификация

Коды Гоппы классифицируются по типу алгебраической кривой, на которой они построены:

• Коды на эллиптических кривых — род \( g = 1 \). Обладают хорошими параметрами и простотой реализации.
• Коды на гиперэллиптических кривых — род \( g \ge 2 \). Позволяют строить коды с большей длиной при фиксированном поле.
• Коды на кривых Эрмита — род \( g = (q-1)(q-2)/2 \) для поля \( \mathbb{F}_{q^2} \). Дают коды с большим минимальным расстоянием.
• Коды на кривых Делиня — Люстига — род \( g = (q-1)(q-2)/2 \) для поля \( \mathbb{F}_q \). Используются в криптографии.

Применение

Криптография

Коды Гоппы лежат в основе криптосистемы Мак-Элиса, предложенной Робертом Мак-Элисом в 1978 году. В этой системе открытый ключ представляет собой замаскированную порождающую матрицу кода Гоппы, а закрытый ключ — структуру кода (кривую и дивизор). Стойкость системы основана на сложности декодирования случайного линейного кода. Коды Гоппы выбраны для этой системы благодаря возможности эффективного декодирования при знании структуры и сложности без неё. В 2010-х годах коды Гоппы рассматривались как кандидаты для постквантовой криптографии, устойчивой к атакам с использованием квантовых компьютеров.

Передача данных

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

Хранение данных

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

Пример

Рассмотрим код Гоппы на эллиптической кривой \( y^2 = x^3 + x \) над полем \( \mathbb{F}_5 \) (характеристика 5). Пусть выбраны 10 рациональных точек на кривой, и дивизор \( G \) имеет степень 5. Тогда код имеет длину 10, размерность 5 (по формуле \( \deg(G) - g + 1 = 5 - 1 + 1 = 5 \)) и минимальное расстояние не менее 5 (по границе Синглтона). Такой код может исправлять до 2 ошибок. Для декодирования используется алгоритм, основанный на вычислении синдрома и решении системы линейных уравнений над \( \mathbb{F}_5 \).

Интересные факты

• Валерий Гоппа впервые описал коды на алгебраических кривых в 1977 году, но его работа долгое время оставалась малоизвестной за пределами СССР. Международное признание пришло после публикации на английском языке в 1981 году.
• В 1982 году американский математик Майкл Циммерман независимо переоткрыл коды Гоппы, но приоритет остался за Гоппой.
• Коды Гоппы используются в криптосистеме Мак-Элиса, которая является одной из старейших постквантовых криптосистем.
• В 1990-х годах было доказано, что коды Гоппы могут достигать границы Синглтона для кривых с родом, растущим как \( O(n) \), что делает их асимптотически оптимальными.

Критика

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

Источники

• Гоппа В. Д. Коды на алгебраических кривых // Доклады АН СССР. — 1977. — Т. 236, № 3. — С. 528–531.
• Гоппа В. Д., Паршин А. Н. Коды на алгебраических кривых // Успехи математических наук. — 1981. — Т. 36, № 5. — С. 203–204.
• Кадио Ж. Алгебраические геометрические коды // Математический сборник. — 1982. — Т. 117, № 4. — С. 522–540.
• Мак-Элис Р. Дж. Публичная криптосистема на основе алгебраических кодов // Технический отчёт JPL. — 1978.
• Циммерман М. Коды на алгебраических кривых // IEEE Transactions on Information Theory. — 1982. — Vol. 28, No. 4. — P. 583–589.