diff options
| -rw-r--r-- | rappels-maths.tex | 70 |
1 files changed, 55 insertions, 15 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index 8df213a..57a421b 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -850,7 +850,8 @@ multiplicative ; en notation additive, cela s'écrirait : $mg = 0$, i.e., un multiple de $g$) ; c'est aussi le nombre de puissances distinctes (en notation additive : de multiples distincts) de l'élément $g$. Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi -$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$. +$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$, et donc $g^i += g^j$ si $i \equiv j \pmod{m}$. Un \textbf{sous-groupe} $H$ d'un groupe $G$ est un sous-ensemble de $G$ qui est lui-même un groupe pour la même opération et le même @@ -1318,7 +1319,8 @@ puissance de $p$ (par exemple, si on sait ce que ça signifie, parce que $\mathbb{F}$ est un espace vectoriel de dimension finie $d$ sur son corps premier $\mathbb{F}_p$) ; on note typiquement $q = p^d$, et alors $d$ s'appelle le \textbf{degré} de $\mathbb{F}$ au-dessus de son -corps premier $\mathbb{F}_p$. +corps premier $\mathbb{F}_p$, ou simplement « degré absolu » +de $\mathbb{F}$. En particulier, le nombre d'éléments d'un corps fini est toujours une puissance $q = p^d$ d'un nombre premier $p$ (il n'y a pas de corps à @@ -1395,9 +1397,9 @@ Fermat), autrement dit, au bout de $d$ applications du Frobenius on retombe sur l'élément $x$ de départ ; il se peut qu'on retombe sur $d$ plus tôt : le plus petit $r$ tel que $x^{p^r} = x$, qui est aussi le nombre de conjugués distincts de $x$, s'appelle le \textbf{degré} -de $x$ (au-dessus de $\mathbb{F}_p$), et ce degré $r$ divise $d$ -(qu'on a appelé le degré de $\mathbb{F}$). Tous les conjugués de $x$ -ont bien sûr le même degré que $x$. +absolu de $x$ (ou : degré de $x$ au-dessus de $\mathbb{F}_p$), et ce +degré $r$ divise $d$ (qu'on a appelé le degré de $\mathbb{F}$). Tous +les conjugués de $x$ ont bien sûr le même degré que $x$. \bigbreak @@ -1483,8 +1485,8 @@ irréductible dans $\mathbb{F}_2[t]$. (On a $t^4 \equiv t^3+1 \pmod{g}$ donc $t^8 \equiv t^6+1 \equiv t^3+t^2+t$ donc $t^{16} \equiv t^6+t^4+t^2 \equiv t$ donc le premier critère est vérifié. Pour le second, $t^4-t \equiv t^3+t+1 \pmod{g}$ puis $g = t^4+t^3+1 \equiv t^2 -\pmod{t^3+t+1}$ et enfin $t^3+t+1 \equiv 1 \pmod{t^2}$ donc $t^4-t$ et -$g$ sont bien irréductibles.) +\pmod{t^3+t+1}$ puis $t^3+t+1 \equiv t+1 \pmod{t^2}$ et enfin $t^2 +\equiv 1 \pmod{t+1}$, donc $t^4-t$ et $g$ sont bien irréductibles.) \medbreak @@ -1501,16 +1503,41 @@ irréductibilité, et de recommencer jusqu'à obtenir un irréductible. \medbreak +\textbf{Polynôme minimal d'un élément :} Pour tout $x \in +\mathbb{F}_q$, où $q = p^d$, il existe un unique polynôme unitaire +irréductible $f \in \mathbb{F}_p[t]$ (noter que $x$ est dans +$\mathbb{F}_q$ mais que $f$ est à coefficients dans $\mathbb{F}_p$) +tel que $f(x) = 0$. Ce polynôme s'appelle le \emph{polynôme minimal} +de $x$. Son degré $\delta$ est égal au degré absolu de $x$, dont on +rappelle qu'il est défini comme le nombre de conjugués $\Frob^i(x)$ +de $x$ ; et les racines de $f$ dans $\mathbb{F}_q$ sont exactement les +conjugués $\Frob^i(x)$ en question : on a $f = \prod_{i=0}^{\delta-1} +(t-\Frob^i(x))$ (on rappelle que le degré absolu $\delta$ de $x$ +divise le degré absolu $d$ de $\mathbb{F}_q$). + +Si $\mathbb{F}_q$ est vu comme $\mathbb{F}_p[t]/(f)$ avec $f$ un +polynôme unitaire irréductible de degré $d$ sur $\mathbb{F}_p$, alors +le polynôme minimal de $\bar t$ est précisément $f$. Réciproquement, +si $x \in \mathbb{F}_q$ a pour degré $d$ (le degré absolu +de $\mathbb{F}_q$, c'est-à-dire le $d$ tel que $q=p^d$) et polynôme +minimal $f$ (de degré $d$, donc), alors il existe un unique +isomorphisme de corps $\psi\colon \mathbb{F}_p[t]/(f) \to +\mathbb{F}_q$ tel que $\psi(\bar t) = x$. + +\smallbreak + On a vu plus haut que sur le corps $\mathbb{F}_q$ (lorsque $q = p^d$), le polynôme $t^q - t$ se factorise en irréductibles comme $t^q - t = -\prod_{a \in \mathbb{F}_q} (t-a)$. Il est utile de savoir que sur -$\mathbb{F}_p$, ce même polynôme se factorise comme le produit de -\emph{tous} les polynômes unitaires irréductibles dont le degré $r$ -divise $d$ (plus précisément, chaque polynôme unitaire irréductible -$f$ de degré $r$ sur $\mathbb{F}_p$ devient, quand on le regarde sur -$\mathbb{F}_q$, le produit des $(t-a)$ pour les $r$ conjugués $a$ d'un -élément de degré $r$). Ce fait peut servir à dénombrer de façon -précise les polynômes unitaires irréductibles de n'importe quel degré +\prod_{a \in \mathbb{F}_q} (t-a)$. Il est utile de savoir ce qu'il en +est sur $\mathbb{F}_p$ : + +Le polynôme $t^q - t$ (où $q = p^d$) se factorise dans +$\mathbb{F}_p[t]$ comme le produit de \emph{tous} les polynômes +unitaires irréductibles dont le degré $\delta$ divise $d$. (Chacun de +ces facteurs $f$ est égal, dans $\mathbb{F}_q[t]$, au produit des +$(t-a)$ pour les $\delta$ conjugués $a$ d'un élément de +degré $\delta$.) Ce fait peut servir à dénombrer de façon précise les +polynômes unitaires irréductibles de n'importe quel degré sur $\mathbb{F}_p$. \medbreak @@ -1537,6 +1564,19 @@ Le nombre d'éléments primitifs est bien sûr $\varphi(q-1)$ (puisque, une fois qu'on sait que $\mathbb{F}^\times$ est cyclique, comme il est d'ordre $q-1$, le nombre d'éléments qui l'engendrent est connu). +Si $g \in \mathbb{F}_q$ est primitif, alors tout élément de +$\mathbb{F}_q$ est soit $0$ soit de la forme $g^i$ pour un entier $i$ +(cet entier est défini de façon unique modulo $q-1$ ; l'application +$\psi \colon \mathbb{Z}/(q-1)\mathbb{Z} \to \mathbb{F}_q^\times$ +donnée par $\bar\imath \mapsto g^i$ définit un isomorphisme de +groupes). La représentation des éléments de $\mathbb{F}_q^\times$ +sous la forme $g^i$ permet facilement de calculer des produits, mais +ne permet pas de calculer des sommes. + +Le problème consistant à retrouver $i$ connaissant (l'élément +primitif $g$ et) $g^i$ s'appelle le \emph{problème du logarithme + discret}, et il est algorithmiquement difficile. + % % % |