Registre de desplaçament: diferència entre les revisions

Contingut suprimit Contingut afegit
Recuperant 1 fonts i marcant-ne 0 com a no actives.) #IABot (v2.0.8
m Diacrítics
Línia 78:
existeix sempre un LFSR -- i.e. un polinomi de retroacció així com una inicialització -- tal que les <math>m</math> primeres sortides d'aquest LFSR corresponen a la <math>m</math>-pla. En el pitjor dels casos es pren un registre de longitud <math>m</math>, el polinomi de retroacció importa poc en aquestes condicions.
 
Això dónadona lloc a la definició de la ''complexitat lineal'' d'una successió (finita) com la longitud mínima d'un LFSR que genera aquesta successió. Com ho prova l'observació de damunt aquesta complexitat està limitada superiorment per la longitud de la successió.
 
Aquesta noció intervé sobretot en criptografia a causa de l'existència de l'[[#Algorisme de Berlekamp-Massey|algorisme de Berlekamp-Massey]].