Регистр сдвига с линейной обратной связью

---

Регистр сдвига с линейной обратной связью (РСЛОС, англ. linear feedback shift register, LFSR) — сдвиговый^[англ.] регистр битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии^[1]. По похожему принципу работают регистр сдвига с обратной связью по переносу и регистр сдвига с обобщённой обратной связью.

Регистр состоит из функциональных ячеек памяти (битов одного или нескольких машинных слов), в каждой из которых хранится текущее состояние (значение) одного бита. Количество ячеек ${\displaystyle L}$, называют длиной регистра. Биты (ячейки) обычно нумеруются числами ${\displaystyle i=0,\;1,\;\dots ,\;L-1}$, содержимое ${\displaystyle i}$-й ячейки обозначается через ${\displaystyle S_{(L-1)-i}}$. Значение нового бита ${\displaystyle S_{L}}$ определяется до сдвига битов в регистре и только после сдвига записывается в ячейку ${\displaystyle 0}$, а из ячейки ${\displaystyle L-1}$ извлекается очередной сгенерированный бит.

---