Seminarium Teorii Gier i Decyzji:

Ciągi de Bruijna rzędu n są to ciągi binarne o okresie 2^n, które w swoim okresie zawierają wszystkie różne słowa o długości n. Ciągi de Bruijna mają wiele zastosowań w kryptografii i telekomunikacji. Powstaje problem, jak praktycznie konstruować takie ciągi o możliwie dużym okresie, np. 2^100 lub większe. Jedną z metod jest zastosowanie liniowych rejestrów przesuwnych (rekurencji liniowych), ale ciągi takie nie są dobre kryptograficznie. Lepsze są ciągi generowane przez nieliniowe rejestry przesuwne (rekurencje nieliniowe). Problem jest ze znalezieniem rekurencji nieliniowych, które generują ciągi o maksymalnym okresie. Podamy metodę konstrukcji takich rekurencji opartą na teorii ciał skończonych i pojęciu logarytmu Zecha.