Регистрация Войти
Рейтинг:1
JAAAY avatar Crypto

Могут ли коды Рида-Соломона работать с бесконечными полями, такими как $\mathbb{Q}$?

флаг us
JAAAY

В настоящее время я читаю о кодах RS. Я вижу, что они используют поля Галуа (конечные поля) в качестве векторных пространств. Есть ли какая-либо другая особая причина, кроме того, что они упрощают двоичную арифметику и, например, в $GF(2^8)$ каждый байт можно рассматривать как вектор? Могут ли они работать в векторных пространствах, определенных в бесконечных полях, таких как $\mathbb{Q}$. Спасибо заранее за ваше время.

PS: Заранее извините, если это неподходящее место для публикации этого вопроса, но я видел, что и Math, и Crypto StachExchanges имеют теория кодирования тег.

63
0 + 0
poncho avatar
флаг my
poncho
В криптографии мы обычно не работаем в $\mathbb{Q}$; по скучным практическим причинам мы предпочитаем сообщения, которые могут быть выражены ограниченным числом битов.
2
Ответить
флаг us
Mikero
Нам также нравится иметь возможность определять равномерное распределение вероятностей в пространстве!
3
Ответить
Daniel avatar
флаг ru
Daniel
То, что упоминают Пончо и Микеро, имеет смысл, и это важные причины, по которым мы не рассматриваем бесконечные алгебраические структуры в криптографии. Однако, просто чтобы удовлетворить ваше любопытство: коды Рида-Соломона можно легко применить к **любому** полю, независимо от его размера. На самом деле они существуют в **любом кольце**, независимо от размера, если оно содержит достаточно большую «исключительную последовательность» (например, https://crypto.stackexchange.com/a/96507/13843).
1
Ответить
Daniel avatar
флаг ru
Daniel
Однако коды Рида-Соломона сами по себе просто берут сообщение и добавляют некоторую избыточность для ошибок декодирования. Их использование в криптографии, например, при обмене секретами Шамира, требует выборки равномерно случайных элементов по этой структуре, что, как упомянул Микеро, невозможно.
1
Ответить
Рейтинг:3
kodlu avatar Crypto
флаг sa
kodlu

Да, они могут работать и при некоторых условиях шума в канале быть полезными для кодирования с исправлением ошибок в непрерывном канале. Первоначально эта идея возникла благодаря профессору Уэлчу (алгоритму Уэлча-Берлекэмпа и известности, связанной с Уэлчем), у которого были неопубликованные конспекты лекций об этом в 1980-х годах, и с инженерной точки зрения $\mathbb{C}$ было очевидным полем для использования, когда вопрос о существовании первобытных корней единства любого желаемого порядка $n$ тривиально, просто возьмите $\omega=\exp\{2 \pi i/n\}.$

Как указывалось в комментариях, это не так полезно для криптографии, поскольку для некоторых протоколов крайне важно существование однородных распределений. Конечно, коды Рида-Соломона в формулировке полевой оценки тесно связаны с обменом секретами Шамира, скажем, с порогом. $т,$ но в условиях конечного поля, чтобы не допустить утечки информации, если менее $t$ акции известны.

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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