Теорема о перестановке коэффициентов многочлена, принадлежащих идеалу кольца
Этой теоремы не получилось найти в Интернете, поэтому пусть ее увидит хотя бы Хабр. Сразу скажу, что многочлены, которые будут упомянуты в названии я буду называть также векторами в случае, когда требуется данное их представление, так что условный многочлен b (x) в паре абзацев ниже может оказаться вектором b, будьте осторожнее, чтобы не запутаться.
О чем вообще будет статья?
Пусть у нас есть поле GF (q), тогда будем рассматривать многочлены в расширении поля GF (q)/f (x). Рассмотрим произвольный многочлен a (x), принадлежащий идеалу Iₐ данного расширения, причем мощность Iₐ минимальна среди всех идеалов, содержащих a (x). Тогда утверждается следующее: многочлен p (x), координаты которого задаются следующим вектором:
, где P — матрица перестановки , также является элементом идеала Iₚ, причем мощности Iₐ и Iₚ совпадают в том случае, если Iₚ — идеал с минимальной мощностью среди всех идеалов, содержащих p (x).
Доказательство
Рассмотрим многочлен:
, где b (x) — произвольный элемент расширения поля. Очевидно, что множество Iₚ всех c (x) является идеалом. Рассмотрим его мощность. Для этого запишем c (x) для произвольного b (x) в векторном виде:
, где B — матрица, представляющая умножение на многочлен b (x). И рассмотрим элемент a':
Покажем, что a'(x) будет принадлежать Iₐ. Для этого необходимо и достаточно, чтобы матрица, являющаяся произведением трех последних была матрицей умножения на какой-то многочлен в расширении поля. Заметим, что матрица D является подобной матрице B, где
Это означает, что D — это операция умножения на многочлен b (x), выраженный в другом базисе. Значит a' принадлежит тому же идеалу, что и a. Но так как это верно для любого b (x), а умножение на матрицу P⁻¹ является биекцией, то мощность Iₚ не больше мощности Iₐ.
Проводя аналогичные рассуждения для многочлена p, можно получить, что мощность Iₐ не больше мощности Iₚ, а значит эти идеалы равномощны.
Замечу, что если использовать в качестве матрицы P не матрицу перестановки, а любую обратимую матрицу, то мы также получим элемент идеала Iₚ при умножении вектора a на нее.
Где использовать?
Наверное самый трудный вопрос в этой статье. Например, можно использовать данное свойство для построение нового циклического кода по уже имеющемуся: как известно, циклические коды можно представить в виде многочленов, тогда из одного порождающего полинома можно получить другой. А уже это свойство можно использовать в криптографии, например, в системах, аналогичных McEliece: вместо передачи порождающего многочлена, который может исправить t ошибок, передавать порождающий многочлен, исправляющий t' ошибок, где t' < t. Тогда можно в сообщение добавлять ошибок больше, чем способен исправить код, передаваемый в открытом ключе, но при этом принимающая сторона все равно будет способна расшифровать сообщение.
Заключение
Возможно, это всем известная теорема, которая прошла мимо меня, но ее потенциал использования в криптографии достаточно интересен: есть шифры, основанные на линейных кодах (вышеупомянутый McEliece), в которых сложность расшифрования сообщения достигается тем, что в закодированное сообщение вносятся ошибки. И внесение большего количества ошибок, чем может исправить нарушитель рушит большинство атак на данную криптосистему. А из доказанной выше теоремы может следовать то, что для получения кода, исправляющего меньшее число ошибок, достаточно переставить некоторые коэффициенты в порождающем многочлене кода (за исключением свободного члена и коэффициента при максимальной степени многочлена). Таким образом можно увеличить криптостойкость системы McEliece.
