Les Suites Récurrentes Linéaires et la 4G

Les corps nis sont utilisés dans la plupart des constructions de séquences pseudoaléatoires et d’analyse de périodes, des corrélations et des étendues linéaires des séquences de registres à décalage de rétroaction linéaire (LFSR) et des séquences générées non linéaires. Ce chapitre donne une description de ces corps nis et certaines propriétés qui sont fréquemment utilisées dans la conception de séquences.

Dans la section 1.2, nous présentent des dénitions et propriétés des suites récurrentes linéaires et des registres à décalage de rétroaction linéaire. En dernière partie, nous donnons une dénition des m-séquences avec quelques-unes de leurs propriétés. 1.1 Rappels sur les corps nis Dénition 1.1.1. Un anneau (A, +, ) est un ensemble A muni de deux lois internes notées ” + ” et ”  ” tel que : 1. (A,+) est un groupe abélien, 2.  est associative, c’est-à-dire (a  b)  c = a  (b  c) pour tout a, b, c ∈ A, 3.  est distributive par rapport à +, c’est-à-dire pour tout a, b, c ∈ A, nous avons : a  (b + c) = (a  b) + (a  c) et (b + c)  a = (b  a) + (c  a). Si la loi  admet un élément neutre noté 1A, on parle d’anneau unitaire et si elle est commutative, on parle d’anneau commutatif.

Dénition 1.1.2. • Un élément a ∈ A est dit inversible s’il existe a 0 ∈ A tel que 3 a 0  a = a  a 0 = 1A. • Un élément a de A est dit diviseur de zéro à droite (respectivement à gauche) si a 6= 0 et s’il existes b 6= 0 tel que a  b = 0 (respectivement b  a = 0). • Un anneau A est dit intègre s’il est sans diviseur de zéro, autrement dit si (a 6= 0, b 6= 0 ⇒ a  b 6= 0). Exemple 1.1.1.  Z est un anneau unitaire intègre.  Z/8Z est un anneau non intègre ( car ¯2  ¯4 = ¯0). Dénition 1.1.3. 1. Un corps est un anneau dans lequel tout élément non nul est inversible. 2. Un corps ni est un corps de cardinal ni (qui a un nombre ni d’élément). 

Un corps ni est aussi appelé corps de Galois qu’on note GF(q) où Fq.

Exemple 1.1.2.  (Q, +, ),(R, +, ) et (C, +, ) sont des corps.  (Z2, +, ) forme un corps ni de cardinal 2. Proposition 1.1.1. (Zp, +, ) est un corps si et seulement si p est un nombre premier. Preuve : L’ensemble (Zp, +, ) est un anneaux commutatif, il reste à montrer que tout élément non nul est inversible si et seulement si p est un nombre premier. -Supposons que Zp est un corps. Soit a ∈ Zp \ {0}. Alors a est inversible. On a pgcd(a, p) = 1. Par suite p est un nombre premier. -Réciproquement, Supposons que p est un nombre premier et soit a ∈ Zp, avec a 6= 0. Alors p ne divise pas a et comme p est un nombre premier, alors pgcd(a, p) = 1 ⇒ a est inversible dans Zp. Remarque : Si (Zn, +, ) est un corps où n > 1 est un entier positif, alors n est un nombre premier. Nous notons (Zp, +, ) simplement par Zp, ou GF(p), appelé le corps de classe des résidus modulo p. 1.1.1 La théorie de base des corps nis Dans ce qui suit, nous allons travailler avec des corps nis.

Dénition 1.1.4. (Caractéristique d’un corps)

Soit F est corps. On appelle caractéristique de F, le plus petit entier positif m tel que ∀ a ∈ F, m × a = 0. 

Proposition 1.1.2

. Soit F un corps ni. Alors la caractéristique de F est un nombre premier. Preuve : Soient F un corps ni et l’homomorphisme d’anneau ϕ : Z → F qui à n 7→ n.1. Le noyau Ker(ϕ) est un idéal premier non nul ( car F est ni) de Z. L’anneau quotient Z/(Ker(ϕ)) est isomorphe à un sous anneau de F, donc intègre. On a donc Ker(ϕ) = (p) pour p premier. Soit F un corps. Un sous ensemble K de F qui est lui-même un corps sous les opérations de F sera appelé sous corps de F. Et F est appelé extension de K. Si K 6= F, on dit que K est un sous corps propre de F. Alors GF(p n ) est de caractéristique p et contient GF(p) comme sous corps. 

Structure de corps nis

Théoreme 1.1.3. Soit F un corps ni et |F| = q avec la caractéristique p. Alors F = GF(p) si q = p ou F est un espace vectoriel de dimension n sur GF(p) si q > p, c’est-à-dire que q = p n . Preuve : Si q = p, on obtient F = GF(p) parce que GF(p) est un sous corps de F. En posant q > p, on choisit un ensemble maximal d’éléments de F linéairement indépendant de GF(p), prenons α0, α1, …, αn−1. Alors F contient tous les éléments a0α0 +a1α1 +…+ an−1αn−1, ai ∈ GF(p) et pas d’autres. Donc F est un espace vectoriel de dimension n sur GF(p) et contient q = p n éléments. Ce théorème montre que si F est un corps ni d’ordre q et de caractéristique p, alors q = p ou q = p n (n ≥ 1). Deux corps nis F et G sont dit isomorphes s’il existe une correspondance biunivoque de F sur G qui préserve l’addition et la multiplication. Tous les corps ni d’ordre p sont isomorphes (nous omettons la preuve ici)[9]. Donc nous n’avons que deux types diérents de corps nis : l’un est GF(p), le corps de classe de résidus modulo p, et l’autre est GF(p n ), le corps d’extension obtenu en adjoignant le zéro d’un polynôme irréductible de degré n sur GF(p) à GF(p n ). Parfois on note F avec un ordre q par Fq. Pour un corps ni F, on note F ∗ le groupe multiplicatif des éléments non nuls et inversibles de F.