Posuvný registr s lineární zpětnou vazbou

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Posuvný registr s lineární zpětnou vazbou (anglicky linear-feedback shift register, zkratkou LFSR) je posuvný registr, jehož výstup je lineárně závislý na jeho předchozích výstupech a stavu.

Posuvné registry s lineární zpětnou vazbou jsou oblíbené jako generátory pseudonáhodných čísel a také v kryptografii jako součásti proudových šifer. Jejich výstup je kromě zpětnovazební funkce závislý také na jejich počátečním stavu, který se v případě použití jako generátorů pseudonáhodných čísel nazývá semínko (v případě šifrového použití je odvozený z klíče).

Posuvné registry s lineární zpětnou vazbou je možné implementovat hardwareově i softwareově. Nejběžnější je registr složený z jednotlivých bitů, tedy lineární funkce je počítána nad dvouprvkovým tělesem, kde operace sčítání odpovídá exkluzivnímu součtu.