Теория
LFSR — регистр сдвига с линейной обратной связью: состояние из \(n\) бит каждый такт сдвигается на одну позицию, а вытесненный бит возвращается обратно, предварительно пройдя через XOR с отводами. Такая схема реализует умножение многочлена на \(x\) в поле GF(2) — отсюда связь с примитивными многочленами.
Если полином обратной связи примитивен, регистр из любого ненулевого состояния проходит все \(2^n-1\) ненулевых комбинаций — максимальный период. Схем две: Фибоначчи (сдвиг вправо, новый старший бит — чётность пересечения состояния с маской) и Галуа (сдвиг влево с XOR маски). Именно на LFSR построены CRC, скремблеры и первые потоковые шифры.
Важно: LFSR линеен: по \(2n\) выходам состояние восстанавливается решением системы линейных уравнений. Как самостоятельный ГПСЧ он слаб.
Пример с решением
- Условие. Регистр из 4 бит с полиномом \(x^4 + x + 1\) (маска 0011), зерно 1, схема Галуа: первые четыре состояния.
- Формула. \(s' = ((s \ll 1) \bmod 2^n) \oplus (mask \wedge (s \gg (n-1)))\).
- Подстановка. \(s = 0001\), старший бит 0 — маска не применяется.
- Вычисление. 0010, 0100, 1000; у 1000 старший бит 1: \(0000 \oplus 0011 = 0011\).
- Ответ. 2, 4, 8, 3. За 15 тактов регистр вернётся к 1 — период полный.
Главное
- Период \(2^n-1\) — у примитивного полинома из любого ненулевого зерна.
- Линейность — плюс для CRC, минус для криптографии.