Rejestr przesuwający z liniowym sprzężeniem zwrotnym

Rejestr przesuwający z liniowym sprzężeniem zwrotnym (ang. linear feedback shift register, LFSR) – rejestr przesuwający, którego bit wejściowy jest funkcją liniową jego poprzedniego stanu. Jedynymi funkcjami liniowymi w dziedzinie pojedynczych bitów są EX-OR oraz EX-NOR. Z tego powodu LFSR można zdefiniować jako rejestr przesuwający, którego wejście jest wysterowane funkcją XOR stanów kilku z komórek tworzących rejestr. Najczęstsze zastosowania LFSR to generowanie liczb pseudolosowych i pseudoszumu. Każdy LFSR jest związany z określonym wielomianem z pierścienia wielomianów gdzie jest ciałem skończonym Okres rejestru jest ograniczony przez stopień stowarzyszonego z nim wielomianu i wynosi maksymalnie gdzie jest stopniem wielomianu (ciało ma charakterystykę równą 2). Okres danego LFSR jest maksymalny jeżeli stowarzyszony z nim wielomian jest wielomianem pierwotnym. Rejestr taki, nazywamy rejestrem maksymalnej długości. Liczba wielomianów pierwotnych stopnia jest wyznaczona przez funkcję Eulera i wynosi Tak więc, dla przykładu dla rejestrów długości 7 istnieje dokładnie rejestrów maksymalnej długości. Jeżeli znany jest stopień wielomianu wystarczy zaledwie bitów wyjścia rejestru, by znaleźć ów wielomian. (Gdyż należy rozwiązać równań, każde z niewiadomymi, ale żeby otrzymać równań wystarczy zaledwie bitów wyjścia) W celu stosowania rejestrów w kryptografii, np. w szyfrach strumieniowych wykorzystuje się różne metody przełamywania liniowości: * nieliniowa kombinacja kilku bitów z aktualnego stanu rejestru, * kombinacja bitów z kilku różnych rejestrów za pomocą funkcji nieliniowej, * nieliniowa kombinacja bitów z kilku różnych rejestrów (np. generator redukujący), * regulacja większościowa częstotliwości taktowania rejestru (np. taka jak w szyfrze strumieniowym A5/1).