Информатика · объяснение и практика
Короткая рекурсия объясняет префикс, но не доказывает неизвестное продолжение
Найти минимальную линейную рекурсию конечной последовательности над малым простым полем, проверить знаки коэффициентов и границу прогноза.

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
Алгоритм Берлекэмпа — Мэсси обновляет связующий полином, когда очередной символ расходится с текущей рекурсией. Полученная минимальная длина относится к заданному конечному префиксу. Продолжение неизвестного источника требует отдельной предпосылки о его генераторе.
Метод и постановка
Укажите простое поле заранее. Значения последовательности должны быть остатками от нуля до p−1, а вычисления выполняются по модулю p. Ненулевой элемент такого поля имеет обратный; именно это позволяет нормировать расхождение. Для составного модуля тот же шаг может быть незаконным, даже если все входные числа выглядят небольшими.
На очередном индексе связующий полином предсказывает линейную зависимость текущего и предыдущих символов. Нулевое расхождение сохраняет полином, ненулевое требует поправки с использованием последнего существенного обновления. Иногда поправка увеличивает минимальную длину, иногда меняет коэффициенты при прежней длине. Поэтому количество ненулевых символов само по себе не определяет сложность последовательности.
Проверка и границы вывода
В отчёте используется явное соглашение s[n]=c₁s[n−1]+…+cLs[n−L]. В связующем полиноме эти коэффициенты стоят с противоположным знаком. Над GF(2) знак незаметен, а над нечётным полем ошибка проявится сразу. Проверяйте подстановку на каждом индексе от L до конца введённого префикса.
Для коротких двоичных примеров минимальность можно независимо подтвердить перебором всех меньших длин и всех их коэффициентов. Это другой способ проверки, полезный для тестов алгоритма. Но даже доказанная минимальность для конечных данных не определяет будущее произвольной последовательности. Следующий символ может нарушить найденную рекурсию. Статистическая случайность, криптографическая стойкость и бесконечная линейная сложность также не следуют из одного конечного значения L. У нулевого префикса допустима длина ноль; называть её отсутствием данных было бы неточно.
Пример
Двоичный префикс 1,1,0,1,1,0,1,1 удовлетворяет рекурсии s[n]=s[n−1]+s[n−2] по модулю два. Длина один не подходит: коэффициент ноль не объясняет второй символ, а единица не объясняет третий.
Минимальная длина равна двум, коэффициенты равны 1,1. Этот вывод проверяет все введённые символы и исключает меньшую длину, но без модели источника не вынуждает следующий символ быть нулём.
От чтения к действию
А теперь — вы
Частые вопросы
Найденная рекурсия доказывает будущие члены?
Нет. Она описывает данный конечный префикс; без предпосылки о генераторе продолжение не идентифицировано.
Можно вводить составной модуль?
Нет. Обращение ненулевого расхождения требует поля; интерфейс ограничен перечисленными простыми.
Углублённый разбор
Ранг Ханкеля обнаруживает линейную рекурсию
Матрица Ханкеля собирает сдвиги одной последовательности в столбцы. Линейная зависимость этих столбцов превращает вопрос о рекурсии в вопрос о ранге, а ненулевой минор доказывает нижнюю границу её порядка.
Перед началом: Линейная рекурсия; Ранг и миноры матрицы.
Один коэффициент должен работать при каждом сдвиге
Положим H_{ij}=s_{i+j}, начиная индексы с нуля. Если s_{n+r}=a₀s_n+…+a_{r−1}s_{n+r−1} для всех n≥0, то столбец с номером r является той же линейной комбинацией первых r столбцов на любом числе строк. Аналогичные равенства действуют для дальнейших столбцов. Поэтому ранг любой конечной матрицы Ханкеля не больше r.
Обратная проверка требует осторожности. Одна зависимость на двух строках подтверждает только два уравнения. Чтобы объявить бесконечную рекурсию, нужно знать закон последовательности либо доказать, что одна комбинация работает при всех сдвигах. Из конечного префикса без дополнительных предположений всегда можно получить другое продолжение, которое разрушит найденную зависимость.
Минор отделяет минимальность от существования
Если найден ненулевой минор размера r, ранг не меньше r, а значит, рекурсии порядка меньше r быть не может. Затем отдельное тождество порядка r даёт верхнюю границу. Совпадение границ доказывает минимальность. Нулевой определитель одного большого блока сам по себе слабее: он не доказывает существование единой рекурсии для всех дальнейших членов.
Для суммы нескольких экспонент s_n=Σ_jb_jλ_jⁿ матрица раскладывается в сумму внешних произведений векторов степеней. Каждое слагаемое имеет ранг не больше одного. Число слагаемых поэтому ограничивает ранг сверху. Различные основания и ненулевые коэффициенты часто дают точную границу, но возможные сокращения следует проверять в выбранном поле.
Поле является частью утверждения о ранге
Ненулевой рациональный определитель может обратиться в нуль после перехода по модулю простого числа. Тогда минимальный порядок способен уменьшиться: основания совпадут или коэффициенты исчезнут. Поэтому нельзя вычислить ранг над вещественными числами, округлить его и перенести ответ на последовательность над конечным полем. Все операции должны выполняться в той алгебре, где задана рекурсия.
В точном малом примере удобно проверять и минор, и остаток каждого уравнения. При шумных измерениях точная теория ранга не применяется буквально: сколь угодно малый шум обычно делает матрицу полного ранга. Там требуется отдельная модель приближённого ранга и погрешности, а не объявление малых чисел точными нулями.
Две экспоненты и минимальный порядок
Условие. Над рациональными числами задано s_n=2ⁿ+3ⁿ для всех n≥0. Докажите минимальность рекурсии второго порядка.
- Первые члены равны 2,5,13,35,97,275. Определитель блока [[2,5],[5,13]] равен 26−25=1, поэтому порядок не может быть меньше двух.
- Оба основания 2 и 3 удовлетворяют λ²−5λ+6=0. Умножение на λⁿ и сложение даёт s_{n+2}=5s_{n+1}−6s_n для всех n≥0.
- В блоке размера три со строками (2,5,13),(5,13,35),(13,35,97) третий столбец равен пяти вторым минус шесть первых. Его определитель нулевой.
- Ненулевой минор даёт нижнюю границу два, а тождество для всех n — верхнюю два. Следовательно, найденный порядок действительно минимален.
Ответ. Минимальный порядок равен двум; коэффициенты рекурсии 5 и −6.
Проверка. Точные определители равны 1 и 0. Независимое раскрытие (λ−2)(λ−3) доказывает уравнение для обоих экспоненциальных слагаемых, а не только для выписанного префикса.
Где легко ошибиться. Не превращайте нулевой определитель одного конечного блока в утверждение о неизвестном бесконечном продолжении. Минимальность требует нижней границы и глобального закона.
Проверьте понимание
Вопросы к этой главе
Нужен квадратный блок?
Нет, ранг определён и для прямоугольной матрицы сдвигов. Квадратные миноры лишь дают удобные точные свидетельства нижней границы ранга.
Почему одной проверки следующего члена мало?
Она подтверждает одно дополнительное уравнение. Произвольная последовательность может согласоваться с рекурсией на сколь угодно длинном префиксе и нарушить её сразу после него.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup: §18.1, Exercise 18.3
Прочитана связь матрицы последовательных сдвигов с линейной рекурсией в упражнении 18.3. Собственная сумма степеней, её миноры и доказательство минимальности построены отдельно; алгоритм Берлекэмпа–Мэсси не повторяется.
Рациональная производящая функция рекуррентной последовательности
Производящая функция переводит рекурсию в умножение формальных рядов. Знаменатель задаёт однородное правило продолжения, а числитель хранит начальные условия; сокращение общей части меняет минимальный порядок.
Перед началом: Рекурсия над полем; Формальный степенной ряд.
Формальное умножение не требует сходимости
Для последовательности s₀,s₁,… определим S(z)=Σₙs_nzⁿ. Коэффициент произведения двух таких рядов является конечной свёрткой, поэтому вычисления имеют смысл без выбора численного z. Если свободный член Q равен единице, ряд Q обратим: каждый следующий коэффициент обратного ряда определяется из предыдущих. Это алгебраическое условие, а не аналитическая оценка радиуса сходимости.
Пусть s_n=as_{n−1}+bs_{n−2} при n≥2. Тогда коэффициенты степени n≥2 в (1−az−bz²)S исчезают. В степенях ноль и один остаются s₀ и s₁−as₀. Получается S=(s₀+(s₁−as₀)z)/(1−az−bz²). Начальные условия нельзя забывать: один знаменатель допускает много разных последовательностей.
Рациональная запись позволяет проверить и сократить модель
Если числитель и знаменатель имеют общий множитель, его нужно сократить перед выводом о минимальном порядке. Несокращённая дробь задаёт верное, но избыточное правило. Например, умножение обеих частей дроби на любой многочлен не меняет ряд и может искусственно увеличить видимую степень знаменателя. Поэтому степень произвольного знаменателя является только верхней границей.
Для дроби P/Q с Q(0)=1 и взаимно простыми P,Q минимальный знаменатель определяется однозначно после нормировки. Если существовал бы меньший знаменатель R, равенство PR=UQ и взаимная простота вынудили бы Q делить R. При правильной дроби это даёт соответствующий минимальный порядок рекурсии; возможную начальную неоднородную часть следует оговаривать отдельно.
Конечное поле меняет коэффициенты, но не смысл свёртки
Над F₅ все суммы, произведения и деления выполняются по модулю пять. Запись −2 и запись 3 обозначают один коэффициент. Ряд по-прежнему бесконечен как формальный объект, хотя последовательность состояний конечного линейного регистра периодична после некоторого момента. Периодичность и рациональная запись связаны, но вычислять период для вывода дроби не требуется.
Независимая проверка умножает найденные коэффициенты S на Q и убеждается, что после числителя получается нуль. Для доказательства бесконечного тождества используется сама рекурсия: каждый дальнейший коэффициент свёртки равен её невязке. Проверка только десяти коэффициентов полезна против арифметической ошибки, однако не заменяет это общее рассуждение.
Начальные условия в числителе
Условие. Над F₅ даны s₀=1,s₁=0 и s_n=2s_{n−1}+s_{n−2}. Найдите S(z), член s₅ и минимальную степень знаменателя.
- Умножаем на Q=1−2z−z². Коэффициенты начиная с z² равны нулю по рекурсии, а первые два дают P=1−2z.
- Следовательно, S=(1+3z)/(1+3z+4z²) в F₅[[z]]. Свободный член знаменателя равен единице, поэтому деление формально допустимо.
- Последовательно получаем s₂=1,s₃=2,s₄=0,s₅=2. Нулевой четвёртый член не означает прекращения последовательности.
- Единственный корень линейного P равен 3. Подстановка в Q даёт 1 по модулю пять, поэтому общего множителя нет. Минимальная степень знаменателя равна двум.
Ответ. S=(1+3z)/(1+3z+4z²), s₅=2, минимальная степень знаменателя два.
Проверка. Точная свёртка первых двадцати коэффициентов даёт только числитель (1,3); общая рекурсия объясняет нулевые коэффициенты всех дальнейших степеней.
Где легко ошибиться. Не теряйте начальные условия и не определяйте минимальный порядок по несокращённой дроби. Формальная обратимость зависит от свободного члена знаменателя.
Проверьте понимание
Вопросы к этой главе
Можно подставить z=1 в формальный ряд?
Автоматически нельзя. Формальный ряд не задан как сходящаяся численная сумма. Подстановка требует отдельного смысла, даже когда рациональную функцию можно вычислить в этой точке.
Всегда ли знаменатель имеет степень два?
Нет: особые начальные условия могут вызвать сокращение, а коэффициент при старшем сдвиге может оказаться нулём в выбранном поле. Минимальный знаменатель проверяется после сокращения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup: §16.8.1 и Theorem 18.2
Прочитаны формальные ряды, критерий обратимости по свободному члену и связь рациональности с рекурсией. Источник использует также обратные ряды Лорана; здесь отдельно выведена конвенция обычной производящей функции и собственный пример над F₅.
Примитивный многочлен даёт максимальный период регистра
Неприводимость многочлена исключает распад на меньшие поля, но максимальный период регистра требует большего — примитивности. Сравним два неприводимых многочлена степени 4 с периодами 15 и 5. Соглашение о порядке битов зададим явно через умножение на x по модулю многочлена.
Перед началом: Многочлены над GF(2) и деление с остатком; Порядок элемента конечной группы.
Состояние как остаток многочлена
Запишем состояние регистра как v=a0+a1x+a2x²+a3x³. Один шаг — вычислить xv по модулю выбранного многочлена p степени 4 с постоянным членом 1. Это линейное обратимое действие на четырёх битах. Нулевое состояние остаётся нулевым, поэтому максимальный цикл ненулевого состояния имеет длину 15, а не 16.
Для p=x⁴+x+1 равенство x⁴=x+1 даёт обновление(a0, a1, a2, a3)→(a3, a0⊕a3, a1, a2). Здесь битовая запись перечисляет коэффициенты от постоянного к старшему. Другие схемы регистра могут использовать обратный порядок и взаимный многочлен; прежде чем сравнивать периоды или отводы, нужно согласовать именно это представление.
Неприводимость и порядок проверяются отдельно
У неприводимого p остатки образуют поле из 16 элементов, а его ненулевые элементы — группу порядка 15. Элемент x имеет порядок, делящий 15. Многочлен примитивен, если этот порядок равен 15. Для проверки достаточно x¹⁵=1 и неравенств x³≠1, x⁵≠1: любой собственный делитель 15 делит 3 или 5.
Для p=x⁴+x+1 нет корней 0,1 и нет делимости на единственный неприводимый двоичный квадрат x²+x+1. Поэтому p неприводим. Вычисление остатков даёт x³=x³, x⁵=x²+x и x¹⁵=1. Два первых остатка не равны 1; следовательно, p примитивен. Эта аргументация не заменяет примитивность одним отсутствием линейных корней.
Неприводимый, но непримитивный пример
Возьмём q=x⁴+x³+x²+x+1. Он тоже не имеет двоичных корней и не делится на x²+x+1, поэтому неприводим. Однако(x+1)q=x⁵+1 в характеристике 2. Значит, по модулю q выполняется x⁵=1. Поскольку x≠1 и 5 просто, порядок равен 5. Регистр имеет короткие ненулевые циклы, несмотря на неприводимость q.
Полный перебор 15 ненулевых состояний для p даёт один цикл. Для q получаются три цикла длины 5. Это независимая конечная проверка полевого аргумента. Длинный период сам по себе не делает линейный регистр криптографически непредсказуемым: здесь исследуется длина орбиты, а не стойкость генератора или возможность восстановить его линейную рекурсию.
Два многочлена степени 4, разные орбиты
Условие. Сравните порядок x по модулю p=x⁴+x+1 и q=x⁴+x³+x²+x+1 над GF(2). Каковы периоды ненулевых состояний соответствующих регистров?
- Оба многочлена не имеют корней 0,1. Остатки по x²+x+1 ненулевые, поэтому при степени 4 оба неприводимы.
- Для p остатки x³ и x⁵=x²+x не равны 1, а x¹⁵=1. Порядок x равен 15.
- Для q тождество(x+1)q=x⁵+1 даёт порядок, делящий 5. Поскольку x≠1, порядок равен 5.
- Умножение любого ненулевого состояния на очередные степени x в поле имеет тот же период. Получаем один цикл 15 для p и три цикла 5 для q.
Ответ. p примитивен и даёт период 15; q неприводим, но непримитивен и даёт период 5. Нулевое состояние отдельно неподвижно.
Проверка. Последовательность ненулевых остатков 1, x, x², … по p посещает все 15 значений до возврата. По q уже пятый шаг возвращает 1; это можно проверить двоичным делением многочленов без таблицы примитивных полиномов.
Где легко ошибиться. Не делайте вывод о максимальном периоде только из неприводимости многочлена.
Проверьте понимание
Вопросы к этой главе
Почему период не может равняться 16?
Нуль неподвижен и не входит в цикл ненулевого состояния обратимого линейного обновления. Ненулевых состояний у четырёхбитного регистра 15.
Зависит ли период от ненулевого начального состояния?
Для неприводимого выбранного многочлена нет: умножение на ненулевое состояние в поле можно сократить. Для произвольного приводимого многочлена такое рассуждение уже неприменимо.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- David Kohel: Cryptography, §6.3, теорема 6.3
Связь периода, порядка остатка x и примитивности. Пара многочленов степени 4, соглашение о коэффициентах и полный конечный перебор здесь проверяются самостоятельно.
Разложение многочлена через неподвижные остатки Фробениуса
Берлекэмп — Мэсси восстанавливает рекурсию последовательности. Здесь одно похожее имя обозначает другую задачу: разложение уже заданного многочлена. Ключом станет пространство остатков, которые не меняются после возведения в квадрат по модулю этого многочлена.
Перед началом: Деление многочленов и НОД над GF(2); Ядро матрицы и исключение строк.
Квадратсвободность делает компоненты различимыми
Монический квадратсвободный многочлен над GF(2); коэффициенты от постоянного к старшему.
Пусть f моничен, имеет степень n и не содержит кратных неприводимых множителей. Это проверяется НОД(f,f′)=1. В характеристике два производная может потерять много членов и даже стать нулевой; такой случай нельзя обрабатывать как обычную цепочку простых множителей. Инструмент явно отклоняет кратный вход, а не выдаёт неполный список.
Если f=f₁…fᵣ с различными неприводимыми fᵢ, китайская теорема об остатках отождествляет GF(2)[x]/(f) с произведением r конечных полей. В каждом поле уравнение u²=u имеет только решения 0 и 1, поскольку u(u−1)=0. Поэтому неподвижные остатки всего произведения образуют двоичное векторное пространство размерности r.
Фробениус превращает вопрос о множителях в линейную систему
Записываем g=g₀+g₁x+…+gₙ₋₁xⁿ⁻¹. Над GF(2) квадрат суммы равен сумме квадратов, а gᵢ²=gᵢ. Значит, g² modf линейно зависит от коэффициентов g. Столбец j матрицы Q содержит коэффициенты остатка x^(2j) modf. Искомый набор удовлетворяет(Q−I)g=0; в двоичной арифметике вычитание совпадает с XOR.
Здесь важно согласовать строки и столбцы: инструмент хранит коэффициенты от постоянного члена, а каждый образ базисного остатка является столбцом. Транспонированная запись без изменения соглашения дала бы другое ядро. Размерность найденного ядра уже сообщает число неприводимых множителей, но для получения самих fᵢ нужны ещё разделяющие НОД.
Базисные остатки разделяют неприводимые компоненты
Неподвижный g на каждой компоненте равен 0 или 1. Поэтому НОД(f,g) собирает компоненты с нулевым значением, а НОД(f,g+1) — с единичным. Неконстантный базисный остаток может разделить текущий множитель на две части. Последовательно применяя базис ко всем уже найденным частям, получаем набор неразличимых по всем координатам компонент.
Полный базис не может оставить две разные неприводимые компоненты навсегда вместе: в пространстве всех двоичных r-векторов есть координата, различающая их. Когда число частей достигло размерности ядра, разложение полно. В конце надо перемножить факторы именно над GF(2): два одинаковых слагаемых сокращаются, обычное целочисленное сложение коэффициентов здесь неверно.
Три компоненты многочлена x⁷+1
Условие. Разложите f=x⁷+1 над GF(2) методом неподвижных остатков и подтвердите полноту результата.
- Производная f′=x⁶; постоянный член f равен 1, поэтому НОД(f,x⁶)=1. В факторкольце x⁷=1, и возведение x^j в квадрат удваивает показатель по модулю 7.
- Умножение индекса на 2 разбивает 0,…,6 на циклы {0},{1,2,4},{3,6,5}. Базис ядра:1, u=x+x²+x⁴, v=x³+x⁵+x⁶. Следовательно, неприводимых компонент ровно три.
- Вычисление НОД(f,u) даёт a=x³+x+1. Деление f на a оставляет произведение двух других компонент; НОД этого остатка с v даёт b=x³+x²+1.
- Последний множитель c=x+1. Два кубика не имеют корней 0 или 1, значит неприводимы; линейный c тоже неприводим. Число трёх факторов совпало с размерностью ядра.
Ответ. x⁷+1=(x+1)(x³+x+1)(x³+x²+1) над GF(2).
Проверка. Независимое перемножение двух кубиков даёт 1+x+…+x⁶. Умножение на x+1 сокращает все внутренние степени попарно и оставляет 1+x⁷. Перебор возможных делителей степеней 1–3 подтверждает отсутствие дальнейшего разложения.
Где легко ошибиться. Не путайте факторизацию Берлекэмпа с Берлекэмпом — Мэсси. Один алгоритм принимает многочлен и разделяет его компоненты, другой принимает конечную последовательность и строит минимальную рекурсию её префикса.
Факторизация Берлекэмпа над GF(2)
Многочлен степени1–8: коэффициенты0 или1 от постоянного до старшего, последний1. Требуется отсутствие кратных неприводимых множителей. Строятся матрица Фробениуса, базис ядра и точное разложение; это не алгоритм Берлекэмпа — Мэсси.
Проверьте понимание
Вопросы к этой главе
Почему константа 1 всегда находится в ядре?
Её квадрат равен ей самой в любом факторкольце над GF(2). Эта базисная константа не разделяет компоненты, но входит в полную размерность неподвижного пространства.
Достаточно ли найти один неконстантный остаток?
Он доказывает приводимость и может дать только частичное разбиение. Для полного результата нужны дальнейшие разделения либо независимое доказательство неприводимости всех полученных частей.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Thibaut Verron — Computer Algebra2, §13.2, Algorithm23
Неподвижная алгебра Фробениуса, условие квадратсвободности и разделение через НОД. Наш двоичный многочлен, циклы индексов и независимое перемножение рассмотрены отдельно от примеров источника.
Нормальный базис конечного поля превращает Фробениус в циклический сдвиг
Примитивный элемент поля не обязательно порождает нормальный базис. В GF(8) орбита α,α²,α⁴ линейно зависима, тогда как орбита θ=1+α даёт базис. На этом различии построим смену координат и увидим, почему возведение в квадрат превращается в перестановку трёх битов.
Перед началом: Линейная независимость над GF(2); Арифметика остатков многочленов.
Нужна независимость сопряжённых элементов
Расширение GF(8) над GF(2) с α³=α+1; координаты в полиномиальном базисе перечисляются как 1,α,α².
В поле характеристики два отображение F(x)=x² сохраняет сумму и произведение. На GF(8) выполнено F³(x)=x⁸=x. Нормальным называется базис θ,θ²,θ⁴, составленный из одной орбиты этого автоморфизма. Необходимо проверить, что три элемента действительно линейно независимы над GF(2); одна лишь цикличность орбиты этого не доказывает.
У α из выбранного представления α⁴=α²+α. Поэтому α+α²+α⁴=0, и три сопряжённых элемента зависимы. При этом α имеет порядок семь в мультипликативной группе и является примитивным. Примитивность относится к степеням при умножении, а нормальность — к линейному базису из сопряжённых; это разные требования.
Матрица переводит между двумя системами координат
Если столбцы M — полиномиальные координаты θ,θ²,θ⁴, то обычные координаты элемента v получаются как Mс, где с — его нормальные координаты. Все суммы и исключение выполняются по модулю два. Обратимость M подтверждает, что каждая тройка с описывает ровно один элемент поля и все восемь элементов покрыты.
Для конкретного элемента можно решить три линейных уравнения либо перебрать восемь троек. Последний способ удобен как независимая проверка маленькой матрицы. Условие ненулевого определителя проверяют в GF(2), а не по величине вещественного определителя с последующим произвольным округлением. Порядок столбцов фиксирует направление дальнейшего сдвига.
Квадрат переставляет коэффициенты, произведение — нет
Пусть v=c₀θ+c₁θ²+c₂θ⁴ с двоичными cᵢ. Тогда v²=c₀θ²+c₁θ⁴+c₂θ⁸=c₂θ+c₀θ²+c₁θ⁴. Нормальные координаты переходят (c₀,c₁,c₂)→(c₂,c₀,c₁). После трёх квадратов исходная тройка возвращается, что независимо проверяет связь с размером поля.
Эта простая перестановка относится к Фробениусу, а не к произвольному умножению двух элементов. Покомпонентное произведение нормальных координат обычно неверно. Для него нужна отдельная таблица произведений базисных элементов или переход к другому представлению. Нормальный базис не означает ортонормальность относительно вещественного скалярного произведения.
Квадрат α² через нормальные координаты
Условие. Возьмите θ=1+α в GF(8), где α³=α+1. Докажите, что θ,θ²,θ⁴ образуют нормальный базис, и найдите квадрат v=α² через циклический сдвиг.
- Получаем θ=1+α, θ²=1+α², θ⁴=1+α+α². Их столбцы в базисе 1,α,α² дают M=[[1,1,1],[1,0,1],[0,1,1]].
- Восемь двоичных комбинаций столбцов имеют разные полиномиальные значения 0,3,5,7,6,4,2,1 в битовой записи. Поэтому ранг M равен трём и орбита является базисом.
- Так как θ+θ⁴=α², нормальные координаты v равны (1,0,1). Применяем правило квадрата: (1,0,1)→(1,1,0).
- Новая тройка означает θ+θ²=α+α². Это и есть v². В полиномиальном представлении независимо (α²)²=α⁴=α+α².
- Ещё два циклических сдвига дают (0,1,1), затем (1,0,1). Последовательность соответствует v⁴ и v⁸=v.
Ответ. Нормальный базис существует для θ=1+α; v имеет координаты (1,0,1), а v² — (1,1,0) и значение α+α².
Проверка. Полный перебор восьми нормальных троек сравнивает циклический сдвиг с прямым квадратом многочлена по модулю x³+x+1. Совпадение проверяется на всём поле, а не только на выбранном v.
Где легко ошибиться. Не принимайте орбиту любого примитивного элемента за нормальный базис. И не переносите циклический сдвиг с операции x↦x² на произвольное произведение двух координатных векторов.
Проверьте понимание
Вопросы к этой главе
Почему α примитивен, но не нормален?
Ненулевые элементы GF(8) образуют группу простого порядка семь, и α≠1 имеет этот порядок. Но его сопряжённые α,α²,α⁴ линейно связаны. Групповой порядок не проверяет независимость трёх векторов.
Можно ли поменять местами θ² и θ⁴?
Базис сохранится, но изменятся координаты и формула перестановки. Правило (c₂,c₀,c₁) выведено для конкретного порядка θ,θ²,θ⁴. После перестановки столбцов нужно заново согласовать направление сдвига.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Peter J. Cameron: Galois fields, §3 Special bases
Прочитаны автоморфизм Фробениуса и определение нормального базиса как орбиты с циклическим действием. Собственные θ=1+α, матрица и все восемь проверок квадрата рассчитаны в указанном GF(8).
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Объединение HyperLogLog сливает регистры, а не складывает оценки
Объяснить идемпотентное объединение совместимых HyperLogLog-эскизов по покоординатному максимуму и границы оценки мощности пересекающихся множеств.
Открыть темуБлижайшее кодовое слово и гарантированное исправление — разные утверждения
Перечислить малый двоичный линейный код, установить минимальное расстояние и показать все ближайшие к принятому слову варианты без скрытого выбора.
Открыть темуПочему префиксный код читается без разделителей
Расшифровываем поток по дереву кодов, проверяем отсутствие одного слова в начале другого и различаем мгновенное и просто однозначное декодирование.
Открыть тему