PICSI

Définition.  

• La complexité linéaire d'une suite infinie s=(s_t)_{t ≥ 0}, notée Λ( s), est le plus entier Λ tel que s peut être engendrée par un LFSR de longueur Λ ; elle est infinie si aucun LFSR ne permet de l'engendrer. Par convention, la complexité linéaire de la suite nulle est égale à 0. La complexité linéaire d'une suite vérifiant une relation de récurrence linéaire correspond au degré de son polynôme minimal.
• La complexité linéaire d'une suite finie sⁿ = s₀ s₁…s_n−1 de n éléments, notée Λ(sⁿ), est la longueur du plus petit LFSR qui permette de produire une suite dont les n premiers éléments correspondent à sⁿ. Pour toute suite finie sⁿ de longueur n, le LFSR de longueur Λ(sⁿ) qui engendre sⁿ est unique si et seulement si n ≥ 2 Λ( sⁿ) [2].

La complexité linéaire d'une suite infinie s et celle de la suite finie composée de ses n premiers éléments sont liées par la propriété suivante. Si la suite infinie s est de complexité linéaire Λ, alors sⁿ est également de complexité linéaire Λ si n ≥ 2 Λ. Dans ce cas, sⁿ correspond aux n premiers éléments produit par l'unique LFSR de longueur Λ qui engendre s [2]. Une notion plus fine est celle de profil de complexité linéaire d'une suite infinie s=s₀s₁…. On désigne par ce terme la suite (Λ( sⁿ))_{n ≥ 1} composée des complexités linéaires de chacune des sous-suites sⁿ = s₀…s_n−1 formées par les n premiers éléments de s.

Complexité linéaire d'une suite aléatoire binaire.   L'espérance de la complexité linéaire d'une suite binaire sⁿ = s₀…s_n−1 de n variables aléatoires binaires indépendantes et uniformément distribuées est donnée par

E[Λ(sn) ] = n 2 + 4 + ε(n) 18 + 2−n   n 3 + 2 9    ,

où ε(n) = n mod 2. Dans le cas d'une suite infinie binaire de période 2ⁿ obtenue en répétant une suite s₀… s_2ⁿ−1 de 2ⁿ variables aléatoires binaires indépendantes et uniformément distribuées, l'espérance de la complexité linéaire est

E[Λ(s) ] = 2n −1 + 2−2n .

De plus amples résultats, notamment sur le profil de complexité linéaire d'une suite aléatoire, peuvent être trouvés dans [3].

Algorithme de Berlekamp-Massey.   L'algorithme de Berlekamp-Massey est un algorithme qui permet de déterminer la complexité linéaire d'une suite finie, ainsi que le polynôme de rétroaction d'un LFSR de longueur minimale qui permet de l'engendrer. Cet algorithme est dû à Massey [2] qui a montré que l'algorithme itératif de décodage des codes BCH proposé par Berlekamp [1] pouvait également être utilisé pour trouver le plus petit LFSR engendrant une suite donnée. Pour une suite sⁿ de longueur n, l'algorithme de Berlekamp-Massey effectue n itérations. La t-ième itération détermine en fait un LFSR de longueur minimale qui engendre les t premiers éléments de sⁿ. L'algorithme se déroule de la manière suivante.

Entrée. sn = s0 s1…sn−1, suite q-aire de n éléments de Fq. Sortie. Λ, la complexité linéaire sn et P, le polynôme de rétroaction d'un LFSR de longueur Λ qui engendre sn. Initialisation.   P(X) ← 1, P′(X) ← 1, Λ ← 0, m ← −1, d′← 1.   Pour t de 0 à n−1 faire d ← st + ∑i=1Λ pi st−i. Si d ≠ 0 alors T(X) ← P(X). P(X) ← P(X) − d (d′)−1 P′(X) Xt−m. si 2Λ ≤ t alors Λ ← t + 1 − Λ. m ← t. P′(X) ← T(X). d′← d. Retourner Λ et P.

Dans le cas particulier d'une suite binaire, il n'est pas nécessaire de stocker la valeur de d′ puisque celle-ci est toujours égale à 1. Dans ce cas, le polynôme de rétroaction est remis à jour simplement par la formule

P(X) ← P(X) + P′(X) Xt−m .

Le nombre d'opérations effectuées pour calculer la complexité linéaire d'une suite de longueur n est proportionnel à n². Il est important de noter que le LFSR de longueur minimale qui génère une suite sⁿ de longueur n est unique si et seulement si n ≥ 2 Λ(sⁿ). Le tableau suivant décrit par exemple le déroulement de l'algorithme de Berlekamp-Massey appliqué à la suite binaire de longueur 7, s₀…s₆ = 0111010. Les valeurs de Λ et P obtenues à la fin de l'itération t correspondent à la complexité linéaire de la suite s₀…s_t et au polynôme de rétroaction d'un LFSR de taille minimale permettant de l'engendrer.

t	st	d	Λ	P(X)	m	P′(X)
			0	1	−1	1
0	0	0	0	1	−1	1
1	1	1	2	1+X2	1	1
2	1	1	2	1+X+X2	1	1
3	1	1	2	1+X	1	1
4	1	0	2	1+X	1	1
5	0	1	4	1+X+X4	5	1+X
6	0	0	4	1+X+X4	5	1+X

Table 1: Déroulement de l'algorithme de Berlekamp-Massey appliqué à s₀…s₆ = 0111010

 

Références

[1]

E.R. Berlekamp. Algebraic Coding Theory. McGraw-Hill, 1968.

[2]

J.L. Massey. << Shift-register synthesis and BCH decoding >>. IEEE Transactions on Information Theory, 15:122-127, janvier 1969.

[3]

R.A. Rueppel. Analysis and Design of stream ciphers. Springer-Verlag, 1986.