Suites Multiplexées et Applications en Cryptographie

Suites Récurrentes Linéaires et applications en cryptographie 

Suites r écurrentes linéaires sur un corps fini 

Ce chapitrr contient csscnticllrment drs rappels de résultat~. de notations sur les corps finis et les suites récurrentes linéaires dont nous ferons usage dans cette thèse. 

 Rappels sur les corps finis 

Corps finis et extensions 

Définit ion 1.2.1. Un corps fim est un corps contenant un nombre fini d’éléments. Remarque 1.2.2. Les corps finis sont appelés corps de Calots. Exemple 1.2.3. (1) (Q, +, .), (IR,+,.) et (C, +, .) sont des corps qui ne sont pas fintS. (2) (Zs, +, .) et (Z2, + .. ) sont des corps finis. 12 Le corps Z2 ne contient que deux éléments 0 et 1 et nous avons les tables d’opérations suivantes : + 0 1 0 0 1 1 1 1 f: 0 1 Les éléments 0 et 1 sont appelés éléments binaires. Définition 1.2.4. Soit p > 1 un nombre premier. On note JFP le corps fini à p éléments ZjpZ. Remarque 1.2.5. Les notations suivantes sont les mêmes : il s’agit de ZjpZ et Zp. Pour tout q puissance d’un nombre premier p, il existe un corps fini de cardinal q. Proposition 1.2.6. (11 Jj Tout anneau intègre ayant un nombre fini n;::: 2 d’éléments est un corps. Théorème 1.2.7. (JtJj 1. Soient q = pn et q’ = pm où n, m ;::: 1 et p est un nombre premier. On a : IFq C !Fq’ {::::::::} n divise m. 2. Soit IF un corps fini de cardinal q > 1. Alors i) q = pm, où p est un nombre premier et m un entier positif ii) IF est unique (à un isomorphisme de corps près). Théorème 1.2.8. J Pour tout corps fini IFq, le groupe multiplicatif, noté IF;, est cyclique. Définition 1.2.9. Si IFq est un corps fini et s’il existe un entier positif non nul minimal n tel que n(J = 0 pour tout (3 E IF9, alors un tel entier est appelé caractéristique de IF q et IF q est dit de caractéristique n. Théorème 1.2.10. Soit IF9 un corps fini. Alors la caractéristique de !Fq est premier. 13 Démonstration. Le cardinal de F9 est égal à q. F9 contient l’élément unité 1, et puisque 1Fq est fini les éléments 1, 1 + 1 = 2, 1 + 1 + 1 = 3, … ne sont pas tous distincts. De plus, le plus petit entier p tel que p. 1 = 1 + 1 + 1 + … + 1 = 0, p(fois) doit être un nombre premier (car (r · s) ·1 = 0 => (r · 1){s ·1) = 0 => r · 1 = 0 ou s = 0). 0 Théorème 1.2.11. [ 1/ Tout corps fini est de caractéristique un nombre premter p et possède p »‘ éléments où mE N*. Proposition 1.2.12. (Théorème Wedderburm)Tout anneau mtégrt .fim est un corps commutatif. Définition 1.2.13. Un qénémtF.ur de IF~ P~t appelP élément primitif de IF9. Un polynôme ayant un élément, primitif comme racme est appelé polynôme pnmtttf. Corollaire 1.2.14. [ ·/ Tout corps fini contient un élément primittf. Lemme 1.2.15. Dans un corps fini de caractéristique p, on a (x+ y)P = xP + yP Démonslntlion. Nous avons expression binomiale suivante : oli Si 1 $ k $ p- 1. alors pgcd(k!,p) = 1. Donc ( ~- ) = p(p- 1)(p 2) … (p-k+ 1) – (p- 1)(p- 2) … (p-k+ 1) – ( d )  » k! – P k! = 0 mo p . 0 Par induction, nous avons le corollaire suivant : Corollaire 1.2.16. Dans tout corps fini dP camté1″istiq11.e p, on a (x+ y)P » = xP » + yP » pour tout n > 1 Définition 1.2.17. Extension d’un corps Soit IT… un corps. On dit que OC est une extenswn de n.. st et seulement si IT… est un sous-corps de OC. Exemple 1.2.18. Le corps de cardinal q =pm, noté IFq est une extenswn de degré m du corps premier F P. 1. C est une extenswn de IR et de Q. 2. IR elit une extenswn de Q( J2). 3. Q( J2) est une extension de Q. Proposition 1.2.19. Soit OC une extenswn de IL. Alors OC est un espace vectonel sur n…. Proposition 1.2.20. Pour tout entier m > 1, IFqm est une extension dt degré m de IFq. Définition 1.2.21. On note [JK : IT…] la dimenswn de l’espace vectonelJK sur IL. Cet entier s’appelle le degré de l’extension de k sur L. Exemple 1.2.22. 1. Le corps des nombres complexes C est une extenswn de IR de degré [C : IR] = 2. 2. Le corps IR est une extension de Q de degré mfini : [IR : Q] = oo. 3. IF q, où q = pn est une extension de IF q de degré n. Définition 1.2.23. Sott IT… un corps. Une extension OC de IT… est un corps de rupture pour le polynôme J(x) E IT…[X] sur IT… si et seulement si, OC contient une racme de f. Exemple 1.2.24. IR est un corps de rupture pour X3 – 2 sur Q. 15 Théorème 1.2.25. St J(X) est un polynôme irréductible dans OC[X], alors f possède un corps de rupture sur OC. Corollaire 1.2.26. Tout polynôme f(X) E r[X] possède un corps de rupture sur r.. Démonstration. En effet, tout polynôme f E IK[X] se décompose en produit de polynômes irréductibles. 0 Définition 1.2.27. Une extension OC de H…. est un corps de décomposition(ou corps scindé) pour f E H….[X] sur H…. st et seulement st, f peut être scmdé dans OC[ X] c’est-à-dire il peut être décomposé en produit de polynômes linéatres dans OC[ X]. Autrement dit st toutes les memes de f dans une clôture algébrique dP. H…. contenant OC sont dans OC. Exemple 1.2.28. 1. Le corps C est un corps de décomposition sur IR. pour le polynôme P(X) = X2 + 1 =(X – i)(X + i). 2. Le corps Q est un corps de décomposition sur Q pouT le polynôme Q(X) = X 2 – 1 = (X- 1)(X + 1). Théorème 1.2.29. Tout polynôme fE OC[X] possède un corps de décomposition sur OC. Définition 1.2.30. Un corps de décomposition minimal sur lK est appelé un corps des racines pour f sur OC. Exemple 1.2.31. 1. C est un corps des racines sur IR pouT le polynôme X 2 + 1. 2. Q( J2) est un corps de décompostttan sur Q pour le polynôme X 2 – 2. 

 Suites récurrentes linéaires et propriétés 

Définition 1.3.1. Une suite (xn)nEN d’éléments de lFq est dite récurrente linéaire homogène (ou homo.rJencous lmmr feedbark shift. regtster seqnenrr ou LFSR sequrnrr 16 en anglais) si elle satisfait, pour tout n ~ 0, une re/atton de récurrence linéatre homogène (à coeffictents constants) de la forme (1.1) avec ao, a1, a2, … , ak-l E IFq. L’ entter k est appPlé degré ou ordre df la relatwn 1.1 et l’état initlal ou conditwns mitiales de cette dernière est (xo, X1, x2, Xk-2, Xk-d · La relatton de réwrrence lméaire est notée parfois Remarque 1.3.2. Les termes équation de récurrence linéaire et solution sont aussi employés pour désigner la relation de récurrence et une suite la satisfaisant. Exemple 1.3.3. Suite de Fibonacci. Posons q = 2, alors nous tr·availlons dans F2 = {0, 1}. Soit la relation de récurrence linéaire et comme conditions initiales x0 = 1, x 1 = 0, on tro·uve la suite bien connue (xn)neN = 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, …. Définition 1.3.4. Une suite (xn)neN E IFq est dite récurrente linéatre non homogène (ou nonhomogeneous lmear feedback shift regtster sequence en anglais) si elle satisfait, pour tout n ~ 0, une relation de récurrence linéaire non homogène (à coefficients constants) de la forme 17 l’entier k est appelé le degré ou ordre de la relation l.t et l’état imttal ou conditwns initiales de cette dernière est (xo, x 1, x2, Xk-2, xk_I). La relation de 1’écurrence homogène qui lui est associée est simplement Exemple 1.3.5. Posons q = 2, alors IF2 – {0, 1}. Soit la rPlation df’ récurrrmœ ltnéaire d’ordre 4 suivante : Xn … 4 = Xn+3 + Xn+l + Xn + 1, avec x0 = 1, x1 = 1. x2 = 0, x3 = 1 comme conditions inittales. Les termes de la suite sont 11101000010111110100001011111 Remarque 1.3.6. La suite nulle (O)nEN est solution de toute équation linéaire récurrente homogène et nt l’est pour aucune équatwn linéaire récurrente non homogène. Dans la suite, nous allons nous concentrer principalement sur les suites récurrentes linéaires homogènes. De plus, toute suite récurrente linéaire homogène sera dite suite récurrente linéaire tout l)irnplcmcnt. 1.3.1 Suites récurrentes linéaires et déterminants de Hankel Définition 1.3.7. Sott x0 , x1, x2, … une suite d’éléments de IFq. Pour les entters n ;::: 0 et r ;::: 1, on pose n 0 el 1′ > 1 Si D(r) = n rl+ 1 · Théorème 1.3.10. r J La smte Xo,Xt,X2, … d’éléments de IFq est une suite récurrente linéaire si el seulement si, il existe un entier posUif r tel que D~) = 0 pour· tout nombrr fini de n ;::: 0. Théorème 1.3.11. r J La smte Xo, Xt’ X2, … d’éléments de IFq est une suite récurrente lméazre, de polynôme minimal de degré k si et seulement si D};l = 0 pour tout r ;::: k + 1 et k + 1 est le plus pettt entier pour lequel ces conditions sont rempltes 1.3.2 Matrice associée d’une suite récurrente linéaire Dans cette partie. nous déterminons et étudions ce qu’est une matrice associée à une suit> récurrente linéaire. Remarque 1.3.12. La matrice associée est encore appelée matrice compagnon et même pardois matrice de trasition. 19 =0 Définition 1.3.13. À l’équation (1.1}, on associe la matrice carré d’ordre k définie par M= 1 0 0 0 1 0 0 0 0 0 1 0 Si k = 1, alors M = (a0). De plus, si k > 1 et (xn)nEN est solution de l’équation (1.1}, alors Xn+k-1 Xn+k-1 =M Xn+k-2 Xn+l et en particulier, pour tout n ;::: 0 Xn+k -2 Xo Exemple 1.3.14. Soit x0 , x1 , x2 , 0. 0 une suite récurrente linéaire sur IF2 satisfaisant la relation de récurrence Xn+S = Xn+4 + Xn+2 + Xn+l + Xn. Nous avons a4 = 1, a3 = 0, a2 = 1, a1 = 1, ao = 1. Alors la matrice M associée à la relation de récurrence est une matrice 5 x 5 définie par : 1 0 1 1 1 1 0 0 0 0 M= 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 Remarque 1.3.15° Soit xo, x 1 , x2 , 0 0. une suite récurrente linéaire sur IFq satisfaisant à la 1-elation 20 où les ai, 1 ~ i ~ k- 1 appartiennent à lFq. Posons Xn+k-l Xn+k-2 Alors à cette suite on associe la matrice M d’ordre k x k sur lFq définie par : M= 1 0 0 0 1 0 0 0 ao 0 0 1 0 Et de plus, nous avons Xn+I = MXn pour n ;:::: 0 et donc Xn = M n Xo avec Xo = xo Une conséquence de la définition d’une matrice associée d’une suite récurrente linéaire : Proposition 1.3.16. Soit x0 , x 1, x2, … une suite récurrente linéaire d’ordre k s·ur 1Fq satisfaisant à la relation (1.1} avec a0 =/: 0, alors l’ordre de la suite x0 ,x1,x2, ..• divise l’ordre de la matrice qui lui est associée. Démonstration. Comme det( M) = (-1)k- 1a0 =J 0, alors si T l’ordre de la matrice M associée à la suite x0 , x1, x 2 , … est fini, alors Xn+r = M n+r Xo = M n Xo x M r = M n Xo x 1 = MnX0 = Xn. 21 Donc rest une période de x0 ,x1,x2 , ..•. Il résulte du Lemme 1.3.22 (définie dans la section qui suit) que l’ordre de If\. suite divise T. 0 En plus de ces quelques définitions, nous alllons donner quelques propriétés des suites récurrentes linéaires. Pour cc faire, nous commençons par dire cc qu’est une suite ultimement périodique et périodique. 1

Périodicité d ‘une suite récurrente linéaire

Définition 1.3.17. Soit x0 ,x1, … une suite d’éléments de IFq. S’il existe des entiers r et no avec r 2: 1, tels que x n+r = Xn po ur tout n 2: no alors la sut te Xo, x 1 , . . . est dite ultimement périodique. Exemple 1.3.18. Sott x0 , x1, x2, … une smte récurrente linéaire sur IF2 satisfatsant la rf fofwn de rfrun·rnrr Xn+4 = Xn.,..2 + Xn+ l OllC(‘ cornmr ftat im.tlal (x3 = 1, X2 = 0, Xi = 1, Xo = 1). Alors les termes sont : 11 1 o 1 1 1 o o 11 o 1 11 o o 11 o 11 1 o o 11 o 1 11 o o 1 … Là, nous voyons bien que cette suite est pénodique à partir du rang 1 et de pénode 7. De ce fait, nous pouvons dir·e que pour tout n > n0 = 1 la suite xn+4 = Xn+2 + Xn-1 est pénodique. Donc ultimement périodique et les termes dans cette période sont 1 0 1 1 1 0 0 Remarque 1.3.19. La plus ptlite parrm. toutes les pértodes poss1bles de la smte ultimement pénodtque est appelée la période de la suite. Définition 1.3.20. Une suite x0 , x 1 • … d’éléments de IFq est dite périodique s’il existe un entier r tel que Xn+r = Xn pour tout n = 0, 1, … et r est appelé période de la suite. 22 Exemple 1.3.21. Soit x0 , x1, x2 …. une suite récurrente linéaire de relatwn de récurrence Xn+5 = Xn+l + Xn et son état zmtial est x4 = 1, X3 = 0, X2 = 1, x1 = 1, x0 = 1. Alors les termes de la sutte sont : 1111010 01111010 01111010 01111010 0 1 … La suite est bien périodique pour tout n 2:: 0 et de période 7. Les termes de la période sont 1 1 1 0 1 0 0 Lemme 1.3.22. Toute pérwde d’une suite ttlttmement pénodique est divisible par la pénodc.. de.. la swtc. Démonstration. Soit t une période d’une suite ultimement périodique xo. Xt. x2 …. et t 1 la. période de ret.tc suite, alors on a Xn~t = Xn pour tout n 2:: no et Xn+t 1 = Xn pour tout n 2:: n 1. Supposons que t 1 ne divise pas t, alors il existe des entiers q et r tels quet= qt1 +r avec 0 ::; r t 1. Ce qui implique que (pour n assez grand) Par conséquent rest une période de la suite x0 , x1, x2 , …. Ce qui est une contradiction avec la définition de t 1. Donc r = 0 et t 1 divise t. 0 Lemme 1.3.23. [.!t j La suite x0, x1• x2, … est périodtque st et seulement si il extste un entzer r > 0 tel que Xn+r = Xn pour tout n = 0, 1, … Théorème 1.3.24. f J Jj Si x0 , x1, x2,. . . est une suite récurrente linéaire dans un corps fin·i satisfaisant à la ·relation (1 . 1 ), et si le coefficient a0 est non nul, alors la sude x0 , x 1, x2 , .•. e.st périodique.