%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \theoremstyle{definition} \newtheorem{comcnt}{Tout}[subsection] \newcommand\thingy{% \refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } \newtheorem{defn}[comcnt]{Définition} \newtheorem{prop}[comcnt]{Proposition} \newtheorem{lem}[comcnt]{Lemme} \newtheorem{thm}[comcnt]{Théorème} \newtheorem{cor}[comcnt]{Corollaire} \newtheorem{rmk}[comcnt]{Remarque} \newtheorem{exmps}[comcnt]{Exemples} \newcommand{\limp}{\mathrel{\Rightarrow}} \newcommand{\liff}{\mathrel{\Longleftrightarrow}} \newcommand{\pgcd}{\operatorname{pgcd}} \newcommand{\ppcm}{\operatorname{ppcm}} \newcommand{\signe}{\operatorname{signe}} \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Frob}} \renewcommand{\qedsymbol}{\smiley} % % % \begin{document} \title{Rappels maths pour crypto} \author{David A. Madore} \maketitle {\footnotesize \immediate\write18{sh ./vc > vcline.tex} \begin{center} Git: \input{vcline.tex} \end{center} \immediate\write18{echo ' (stale)' >> vcline.tex} \par} \pretolerance=10000 \tolerance=8000 % % % \section{Entiers} \subsection{L'anneau des entiers} On appelle $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ l'ensemble des entiers relatifs. Il a pour sous-ensemble $\mathbb{N} = \{0,1,2,3,\ldots\}$ l'ensemble des entiers naturels (ou positifs). Sur $\mathbb{Z}$ on a les opérations : $+$ (addition) et $\times$ (multiplication) ; et les éléments remarquables : $0$, $1$. Ces données vérifient les propriétés suivantes : \begin{enumerate} \item Associativité de l'addition : $x+(y+z) = (x+y)+z$ \item Neutralité de zéro pour l'addition : $0+x = x+0 = x$ \item Existence d'opposés (=symétriques pour l'addition) : (pour chaque $x$, il existe un élément noté $-x$ tel que) $x + (-x) = (-x) + x = 0$ \item Commutativité de l'addition : $y+x = x+y$ \item Distributivité de la multiplication sur l'addition : $x(y+z) = xy + xz$ et $(x+y)z=xz+yz$ \item Associativité de la multiplication : $x(yz) = (xy)z$ \item Neutralité de un pour la multiplication : $1x = x1 = x$ \item Commutativité de la multiplication : $yx = xy$ \end{enumerate} Les trois premières propriétés traduisent le fait que $\mathbb{Z}$ est un \emph{groupe} pour l'addition ; les quatre premières, que $\mathbb{Z}$ est un \emph{groupe abélien} pour l'addition ; les sept premières propriétés traduisent le fait que $\mathbb{Z}$ est un \emph{anneau} ; les huit propriétés réunies traduisent le fait que $\mathbb{Z}$ est un \textbf{anneau commutatif}. Mieux : c'est un \emph{anneau intègre} : si $uv=0$ alors $u=0$ ou $v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 = 0$). Éléments inversibles : un \textbf{inversible} ou une \textbf{unité} (dans un anneau commutatif) est un élément $x$ tel qu'il existe $y$ tel que $xy = 1$. Dans $\mathbb{Z}$, les inversibles sont $1$ et $-1$. On a aussi sur $\mathbb{Z}$ une relation d'ordre : c'est-à-dire une relation réflexive (on a toujours $x\leq x$), antisymétrique (si $x\leq y$ et $y\leq x$ alors $x=y$) et transitive (si $x\leq y$ et $y\leq z$ alors $x\leq z$). % \subsection{Écriture $b$-adique} Si $b\geq 2$ est un entier naturel, tout entier naturel $A$ s'écrit de façon unique $A = \sum_{i=0}^{+\infty} a_i b^i$ avec $0\leq a_i1$, il y a toujours un nombre premier $p$ tel que $x < p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand », démontré en 1850). De façon équivalente : si $p$ est premier, alors le nombre premier qui le suit immédiatement est $<2p$. Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à $\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée Poussin : « théorème des nombres premiers », démontré en 1896). Moralement : la probabilité qu'un nombre de $n$ bits aléatoire soit premier est environ $\frac{1}{n\,\ln 2}$. Beaucoup de questions ouvertes. Par exemple : Conjecture des nombres premiers jumeaux : existe-t-il une infinité de nombres premiers $p$ tels que $p+2$ soit aussi premier (tels que $3$, $5$, $11$, $17$, $29$, $41$, $59$, $71$...) ? \smallbreak \textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors $p$ divise $a$ ou $p$ divise $b$. % \subsection{Décomposition en facteurs premiers} Pour tout entier $n$ \emph{non nul}, il existe une écriture \emph{unique} (à l'ordre près) de $n$ comme produit d'une \emph{unité} ($1$ ou $-1$) et de nombres premiers : en regroupant les facteurs premiers $p$, \[ n = u\, 2^{v_2(n)} \, 3^{v_3(n)} \cdots p^{v_p(n)}\cdots \] Ici, $v_p(n)$ (un entier naturel) est l'exposant de la plus grande puissance de $p$ qui divise $n$ : on l'appelle \emph{valuation $p$-adique} de $n$. Presque tous ces nombres sont nuls, ce qui permet de donner un sens au produit infini. Dire que $b|a$ signifie $v_p(b) \leq v_p(a)$ pour tout $p$. Quant à $u$, c'est simplement le signe de $n$. Exemple : $7920 = 2^4\times 3^2\times 5\times 11$, c'est-à-dire que $v_2(7920)=4$, $v_3(7920)=2$, $v_5(7920)=1$, $v_7(7920)=0$, $v_{11}(7920)=1$, et $v_p(7920)=0$ pour n'importe quel nombre premier $p\geq 13$. % \subsection{Remarques sur la complexité} Toujours pour des nombres de $n$ bits. \textbf{Tests de primalité :} \emph{polynomiaux}. Un test polynomial \emph{déterministe} est connu depuis seulement récemment (Agrawal-Kayal-Saxena), démontrablement en $O(n^{12})$, sans doute meilleur ($O(n^3)$ ?). En pratique, des tests probabilistes sont suffisants et plus efficaces (p.e., Miller-Rabin « pratiquement » en $O(n^2)$) éventuellement complétés par des certificats de primalité (p.e., test d'Atkin). \textbf{Algorithmes de factorisation :} \emph{lents}. Font appel à des résultats difficiles de théorie algébrique et analytique des nombres. La meilleure méthode connue (« méthode du crible général de corps de nombres ») a une complexité « attendue » (et heuristique) en $O(e^{n^{1/3}\,(\log n)^{2/3}\,(\textrm{cte}+o(1))})$ (avec $\textrm{cte} \approx 2$). On ne pourra donc pas envisager d'utiliser la décomposition en facteurs premiers pour calculer les pgcd. % \subsection{Valuation $p$-adique} Si $n$ est un entier et $p$ un nombre premier, $v_p(n)$ est l'exposant de la plus grande puissance de $p$ qui divise $n$. Si $a/b$ est un rationnel, on pose $v_p(a/b) = v_p(a)-v_p(b)$ (ne dépend pas de la représentation $a/b$ choisie). Par convention, $v_p(0) = +\infty$. Quelle est la valuation $2$-adique de $192$ ? $3$-adique ? $5$-adique ? Quelles sont les valuations $p$-adiques de $-\frac{24}{11}$, pour tous les $p$ possibles ? Propriétés de $v_p$ : produit (cf. lemme de Gauß) : on a $v_p(xy) = v_p(x) + v_p(y)$ ; inégalité sur la somme : on a $v_p(x+y) \geq \min(v_p(x), v_p(y))$ avec égalité si $v_p(x) \neq v_p(y)$. Dire que $x \in \mathbb{Q}$ est entier signifie exactement $v_p(x) \geq 0$ pour tout $p$. Remarque : calculer $v_p(n)$, pour un $n$ donné et un $p$ premier donné, est facile. Ce qui est difficile dans la décomposition en facteurs premiers, c'est de trouver tous les $p$ tels que $v_p(n) > 0$ (ou en fait, en trouver \emph{un}). % \subsection{Division euclidienne} Si $a$ est un entier relatif et $b$ un entier naturel \emph{non nul}, il existe un unique couple $(q,r)$ tel que : \begin{itemize} \item $q$ est un entier relatif, \item $r$ est un entier naturel tel que $0\leq r2$), $\varphi(m)$ est toujours \emph{pair} (sauf pour $m=2$). Si $p$ est premier, alors tous les nombres entre $1$ et $p-1$ sont premiers avec $p$ : $(\mathbb{Z}/p\mathbb{Z})^\times = \{\bar 1,\ldots, \overline{p-1}\}$ (et notamment $\varphi(p) = p-1$). Tous les éléments de $\mathbb{Z}/p\mathbb{Z}$ sont inversibles sauf $\bar 0$ : on dit que l'anneau $\mathbb{Z}/p\mathbb{Z}$ est un \emph{corps} et on le note $\mathbb{F}_p$. % \subsection{Théorème chinois} Si $m$ et $n$ sont deux naturels non nuls \textbf{premiers entre eux}, considérons l'application dont les composantes sont les deux surjections canoniques : \[ \mathbb{Z}/(mn)\mathbb{Z} \to (\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \] Autrement dit, il s'agit de l'application qui envoie un entier $z$ modulo $mn$ sur sa classe modulo $m$ et sa classe modulo $n$. Il s'agit d'un \emph{morphisme d'anneaux} (car les surjections canoniques en sont !) : \begin{itemize} \item il est injectif car un entier multiple de $m$ et de $n$ est multiple de $mn$ (lemme de Gauß), \item il est surjectif car les cardinaux coïncident ($mn$ au départ et à l'arrivée), \end{itemize} c'est donc un \textbf{isomorphisme}. Dresser la table d'isomorphisme de $\mathbb{Z}/10\mathbb{Z}$ avec $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z})$... \smallbreak Concrètement, le théorème chinois signifie : lorsque $m$ et $n$ sont premiers entre eux, se donner un entier modulo $mn$ revient au même que se donner cet entier modulo $m$ et modulo $n$ séparément (et, de plus, toutes les combinaisons d'une classe modulo $m$ et d'une classe modulo $n$ sont possibles pour une unique classe modulo $mn$). % \subsection{Théorème chinois explicite} Si on a une relation de Bézout $um+vn=1$, alors l'isomorphisme chinois a pour réciproque \[ \begin{array}{c} (\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \to \mathbb{Z}/(mn)\mathbb{Z}\\ (x,y) \mapsto umy+vnx\\ \end{array} \] (Remarque : dans cette expression, on peut se contenter de calculer $uy$ modulo $n$ avant de le multiplier par $m$, et de même $vx$ modulo $m$ avant de le multiplier par $n$, ce qui est parfois plus efficace que de faire tout le calcul modulo $mn$.) Exemple : trouver le nombre entre $0$ et $100$ congru à $9$ modulo $11$ et à $3$ modulo $13$. (Relation de Bézout : $6\times 11 - 5 \times 13 = 1$ ; ensuite, $6 \times 11 \times 3 - 5 \times 13 \times 9 \equiv 5\times 11 - 1\times 13 \equiv 42 \pmod{11\times 13}$.) \medskip Généralisations du théorème chinois : \begin{itemize} \item Si $m$ et $n$ ne sont pas premiers entre eux, toute donnée d'une classe $x$ modulo $m$ et d'une classe $y$ modulo $n$ ne permet pas forcément de retrouver une classe modulo $mn$ (il faut, et il suffit, pour cela, que $x$ et $y$ soient « compatibles », c'est-à-dire congrus modulo $d = \pgcd(m,n)$). Lorsque $x$ et $y$ sont compatibles, alors on retrouve une unique classe modulo $\ppcm(m,n)$ (pour faire le calcul en pratique, diviser l'un des deux nombres $m,n$ par $d$ pour se ramener à deux nombres premiers entre eux). \item Si $m_1,\ldots,m_k$ sont premiers entre eux \emph{deux à deux}, alors la donnée d'une classe modulo le produit $m_1\cdots m_k$ équivaut à la donnée de classes modulo chacun des $m_i$ (pour faire le calcul en pratique, on utilise les classes modulo $m_1,m_2$ pour trouver une classe modulo $m_1 m_2$, puis celle-ci et la classe modulo $m_3$ déterminent une classe modulo $m_1 m_2 m_3$, etc.). \item En combinant ces deux généralisations : connaissant la classe d'un entier modulo $m_1,\ldots,m_k$, on peut retrouver sa classe modulo $\ppcm(m_1,\ldots,m_k)$. \end{itemize} % \subsection{Calcul de l'indicatrice d'Euler} Si $m$ et $n$ (naturels non nuls) sont premiers entre eux, par le théorème chinois on a $(\mathbb{Z}/(mn)\mathbb{Z})^\times \cong (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times$, donc \[ \varphi(mn) = \varphi(m)\,\varphi(n) \] Si $p$ est premier alors $\varphi(p^r) = (p-1)\,p^{r-1}$ (car être premier avec $p^r$ équivaut à être premier à $p$, et c'est le cas de $p-1$ entiers sur $p$). On en déduit : \[ \varphi(n) = n\,\prod_{p|n}\left(1-\frac{1}{p}\right) \] où $p$ parcourt les premiers divisant $n$. Exemple : $\varphi(63) = \frac{2}{3}\times\frac{6}{7}\times 63 = 36$. (Intuitivement : parmi les $n$ entiers de $0$ à $n-1$, pour chacun des nombres premiers $p$ divisant $n$, il y a une proportion $\frac{p-1}{p}$ des nombres qui ne sont pas multiples de $p$, et toutes ces propriétés sont indépendantes --- c'est essentiellement le théorème chinois --- donc la proportion des nombres qui ne sont multiples d'aucun des $p$ divisant $n$ est le produit des $\frac{p-1}{p}$.) \textbf{Algorithmiquement :} \emph{lent} en général (demande de connaître la d.f.p.). % \subsection{Notions de théorie des groupes} Un \textbf{groupe} est un ensemble $G$ muni d'une opération binaire $\star$ (c'est-à-dire une application $G\times G \to G$ dont on note $g \star g'$ l'image d'un couple $(g,g')$) et d'un élément remarquable $e$ tels que : \begin{itemize} \item Associativité de $\star$ : $x\star(y\star z) = (x\star y)\star z$ \item Neutralité de $e$ pour $\star$ : $e\star x = x\star e = x$ \item Existence de symétriques : pour chaque $x$, il existe un élément noté $x'$ tel que) $x \star x' = x' \star x = e$ \end{itemize} Lorsque de plus la loi $\star$ est commutative ($y\star x = x\star y$), on parle de \emph{groupe abélien} (ou commutatif). Exemples : l'addition sur les nombres réels (la loi $\star$ étant l'addition et le neutre $e$ étant le nombre $0$), ou sur les complexes, ou sur les entiers ; la multiplication sur les nombres réels non nuls (la loi $\star$ étant la multiplication et le neutre $e$ étant le nombre $1$), ou sur les réels strictement positifs, ou sur les complexes non nuls ; la composition des isométries du plan (la loi $\star$ étant la composition et le neutre $e$ étant l'identité). Contre-exemple : la multiplication sur les entiers (ou même sur les entiers non nuls) \emph{ne forme pas} un groupe, faute d'inverses pour les entiers autres que $\pm 1$. Généralement, un groupe est noté soit de façon multiplicative (on écrit $xy$ au lieu de $x\star y$ et $1$ au lieu de $e$, et dans ce cas on note $x^m$ l'élément $x\star x\star \cdots x$ avec $m$ fois $x$ et $x^{-1}$ le symétrique de $x$, alors appelé « inverse »), soit de façon additive (on écrit $x+y$ au lieu de $x\star y$ et $0$ au lieu de $e$, et dans ce cas on note $mx$ l'élément $x + x + + \cdots + x$ avec $m$ fois $x$, et $-x$ le symétrique de $x$, alors appelé « opposé »). Très souvent on utilise une de ces deux notations de façon implicite. La notation additive est en principe réservée aux groupes abéliens (mais on n'en rencontrera pas de non-abéliens dans ce cours). \smallbreak Un \textbf{morphisme} de groupe $\psi\colon G \to G'$ est une application qui préserve la composition ($\psi(x\star y) = \psi(x) \star \psi(y)$), et du coupb forcément aussi l'élément neutre ($\psi(e) = e$) et les symétriques (le symétrique de $\psi(x)$ est l'image du symétrique de $x$). Un \textbf{isomorphisme} de groupes est un morphisme bijectif ; moralement : les groupes $G$ et $G'$ sont abstraitement « le même » (mais éventuellement notés ou étiquetés différemment). Attention ! On aura souvent affaire, par exemple, à un morphisme entre un groupe noté additivement et un groupe noté multiplicativement : dans ce cas, cela signifie $\psi(x+y) = \psi(x)\,\psi(y)$. Exemple : l'exponentielle (de base $e$, disons) constitue un isomorphisme entre le groupe additif des réels et le groupe multiplicatif des réels non nuls. L'\textbf{ordre d'un groupe} est simplement son cardinal, lorsque celui-ci est fini. L'\textbf{ordre d'un élément} $g$ dans un groupe fini est le plus petit $m\geq 1$ tel que $g^m = 1$ (en notation 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$. 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 élément neutre ; c'est-à-dire, c'est une partie $H$ de $G$ telle que $1 \in H$ et que $x,y \in H \limp xy \in H$ et que $x \in H \limp x^{-1} \in H$ (cette dernière partie étant d'ailleurs automatique si le groupe $G$ est fini). (Exemple : pour la multiplication, les nombres réels strictement positifs forment un sous-groupe du groupe des nombres réels non nuls.) Le sous-groupe engendré par une partie $E$ d'un groupe $G$ est le plus petit sous-groupe contenant $E$ (c'est-à-dire l'intersection de tous les sous-groupes de $G$ contenant $E$). On utilisera cette notion seulement dans le cas suivant : le \emph{sous-groupe engendré par un unique élément} $g$ de $G$ : c'est l'ensemble des puissances de $g$ (en notation additive : multiples). L'ordre $m$ de ce sous-groupe est l'ordre de $g$. Ce sous-groupe est isomorphe à $\mathbb{Z}/m\mathbb{Z}$, avec $\bar k \mapsto g^k$. \smallbreak \textbf{Théorème de Lagrange :} Dans un groupe fini, l'ordre de tout sous-groupe divise l'ordre du groupe. En particulier, l'ordre d'un élément divise l'ordre du groupe : si $G$ est un groupe fini et $g \in G$ alors $g^{\#G} = 1$. % \subsection{Groupes cycliques} On dit qu'un groupe fini $G$ est \textbf{cyclique} lorsqu'il existe un élément $g$ (appelé \emph{générateur} de $G$) tel que tout élément de $G$ soit de la forme $g^k$ (une puissance de $g$, en notation multiplicative ; en notation additive, cela s'écrirait : $kg$, i.e., un multiple de $g$), autrement dit : le sous-groupe engendré par $g$ est $G$ tout entier. Ou encore : $G$ est cyclique de générateur $g$ si et seulement si l'ordre de $g$ est égal à l'ordre de $G$. Le groupe \emph{additif} $\mathbb{Z}/m\mathbb{Z}$ est cyclique, avec pour générateur $1$ (mais ce n'est pas le seul possible ! cf. ci-dessous). Réciproquement, tout groupe cyclique est isomorphe à $\mathbb{Z}/m\mathbb{Z}$, avec $m$ l'ordre d'un générateur $g$ (qui est donc aussi l'ordre du groupe et ne dépend pas du générateur). D'où une autre définition possible : un groupe cyclique $G$ [de générateur $g$] est un groupe isomorphe à $\mathbb{Z}/m\mathbb{Z}$ [avec $1$ correspondant à $g$]. Quels sont tous les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme groupe additif !) ? Réponse : ce sont précisément les classes modulo $m$ des entiers premiers à $m$, c'est-à-dire les inversibles de $\mathbb{Z}/m\mathbb{Z}$ (comme anneau !). (Démonstration : si $\bar a$ engendre le groupe additif $\mathbb{Z}/m\mathbb{Z}$, alors en particulier il doit engendrer $\bar 1$, c'est-à-dire qu'on peut écrire $\bar 1 = \bar a + \bar a + \cdots + \bar a$, avec $u$ fois $\bar a$ disons, donc $\bar a \bar u = \bar 1$ dans l'anneau $\mathbb{Z}/m\mathbb{Z}$, et $\bar a$ y est bien inversible. Réciproquement, si $\bar a \bar u = \bar 1$, et si $\bar a + \bar a + \cdots + \bar a = 0$, avec $k$ fois $\bar a$, alors en multipliant par $\bar u$ on a $\bar 1 + \bar 1 + \cdots + \bar 1 = 0$, soit $\bar k = 0$, donc $k$ est multiple de $m$ : ceci prouve que l'ordre de $\bar a$ ne peut pas être plus petit que $m$.) Ainsi, pour $m$ entier naturel non nul et $a$ entier, il y a équivalence entre : \begin{itemize} \item les entiers $a$ et $m$ sont premiers entre eux, \item l'élément $\bar a$ a pour ordre (additif) $m$ dans le groupe $\mathbb{Z}/m\mathbb{Z}$, \item l'élément $\bar a$ est générateur du groupe $\mathbb{Z}/m\mathbb{Z}$, \item l'élément $\bar a$ est inversible dans l'anneau $\mathbb{Z}/m\mathbb{Z}$, \item l'élément $\bar a$ appartient au groupe $(\mathbb{Z}/m\mathbb{Z})^\times$ des inversible de l'anneau $\mathbb{Z}/m\mathbb{Z}$. \end{itemize} En particulier, $\mathbb{Z}/m\mathbb{Z}$ admet $\varphi(m)$ générateurs. Comme un groupe cyclique d'ordre $m$ est la même chose que (un groupe isomorphe à) $\mathbb{Z}/m\mathbb{Z}$, on en déduit : le nombre de générateurs de n'import quel groupe cyclique d'ordre $m$ est $\varphi(m)$. Attention ! on parlera aussi, plus loin, des générateurs du groupe \emph{multiplicatif} $(\mathbb{Z}/m\mathbb{Z})^\times$ (et de la question de savoir s'il y en a). Il ne faut pas confondre ! \medbreak De façon générale, l'ordre additif de $\bar a$ dans $\mathbb{Z}/m\mathbb{Z}$ vaut exactement $m/\pgcd(a,m)$. % \subsection{Théorème d'Euler} Si $m$ est un entier naturel non nul et $a$ un entier premier à $m$, alors \[ a^{\varphi(m)} \equiv 1 \pmod{m} \] Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$ a un ordre qui d'après Lagrange doit diviser l'ordre du groupe, i.e. $\varphi(m)$. \textbf{Attention !} ne pas confondre l'ordre (« additif ») d'un élément du groupe additif $\mathbb{Z}/m\mathbb{Z}$ et l'ordre (« multiplicatif ») d'un élément du groupe multiplicatif $(\mathbb{Z}/m\mathbb{Z})^\times$. Exemple : quel est l'ordre de $2$ dans $\mathbb{Z}/7\mathbb{Z}$ ? (réponse : $7$ car $2+2+2+2+2+2+2 = 0$ dans $\mathbb{Z}/7\mathbb{Z}$ et qu'on ne trouve pas $0$ avant) ; et dans $(\mathbb{Z}/7\mathbb{Z})^\times$ ? (réponse : $3$ car $2\times 2\times 2 = 1$ dans $(\mathbb{Z}/7\mathbb{Z})^\times$ et qu'on ne trouve pas $1$ avant). Pour que l'ordre multiplicatif d'un élément $x$ dans $\mathbb{Z}/m\mathbb{Z}$ soit défini, il faut (et il suffit) que cet élément $x$ soit dans $(\mathbb{Z}/m\mathbb{Z})^\times$ (car c'est lui le groupe multiplicatif), et dans ce cas l'ordre additif vaut forcément $m$ car $x$ est un générateur du groupe cyclique $\mathbb{Z}/m\mathbb{Z}$. \smallbreak Cas particulier du théorème d'Euler : le « petit théorème de Fermat » : si $p$ est premier, alors $a^{p-1} \equiv 1 \pmod{p}$ lorsque $a$ n'est pas multiple de $p$ ; donc, pour tout entier $a$ on a \[ a^p \equiv a \pmod{p} \] Ceci fournit une condition \emph{nécessaire} mais non suffisante pour qu'un nombre soit premier. % \subsection{Éléments primitifs} Soit $m$ un entier naturel non nul. On dit que $g \in (\mathbb{Z}/m\mathbb{Z})^\times$ est (un résidu) \textbf{primitif} (modulo~$m$) lorsqu'il engendre $(\mathbb{Z}/m\mathbb{Z})^\times$ (comme groupe abélien multiplicatif) --- ce qui entraîne que $(\mathbb{Z}/m\mathbb{Z})^\times$ est cyclique. Autrement dit, $g^{\varphi(m)}=1$ est optimal : dire que $g$ est primitif modulo $m$ signifie que son ordre multiplicatif est exactement $\varphi(m)$ (et pas un autre diviseur de $\varphi(m)$). Exemple : les puissances de $\bar 2$ modulo $9$ sont : $\bar 2,\bar 4,\bar 8,\bar 7,\bar 5,\bar 1$ ; il y en a bien $\varphi(9)=6$ donc $2$ est primitif modulo $9$. \smallbreak \textbf{Attention !} Ne pas confondre : \begin{itemize} \item $\mathbb{Z}/m\mathbb{Z}$ (groupe \emph{additif}, d'élément neutre $0$) est d'ordre $m$ et est \emph{toujours} cyclique (avec pour générateurs au moins $1$ et $-1$, et tous les éléments de $(\mathbb{Z}/m\mathbb{Z})^\times$). \item $(\mathbb{Z}/m\mathbb{Z})^\times$ (groupe \emph{multiplicatif}, d'élément neutre $1$) est d'ordre $\varphi(m)$ et est \emph{parfois} cyclique (auquel cas ses générateurs s'appellent éléments \emph{primitifs} et il y en a $\varphi(\varphi(m))$). \end{itemize} \medbreak \textbf{Théorème :} \begin{itemize} \item Si $p$ est un nombre premier impair, alors $(\mathbb{Z}/p\mathbb{Z})^\times$ est cyclique, i.e., il existe des éléments primitifs modulo $p$. (Il en existe exactement $\varphi(p-1)$.) \item Si $p$ est un nombre premier impair et $r\geq 2$, alors $(\mathbb{Z}/p^r\mathbb{Z})^\times$ est cyclique, i.e., il existe des éléments primitifs modulo $p^r$. (Il en existe exactement $\varphi(p^{r-1}(p-1))$.) \emph{Mieux} : $g$ est primitif modulo $p^r$ si et seulement si il l'est modulo $p^2$. \item Si $p=2$ et $1\leq r\leq 2$, alors $(\mathbb{Z}/2^r\mathbb{Z})^\times$ est trivialement cyclique. \item Si $p=2$ et $r \geq 3$, alors $(\mathbb{Z}/2^r\mathbb{Z})^\times$ \emph{n'est pas} cyclique : il est produit d'un groupe cyclique d'ordre $2$ engendré par $-1$ et d'un groupe cyclique d'ordre $2^{r-2}$ engendré par $5$ (l'ordre maximal possible d'un élément est $2^{r-2}$). \end{itemize} % \section{Polynômes} \subsection{Définition, structure d'anneau et degré} Soit $k$ un anneau commutatif quelconque (par exemple : $\mathbb{Z}$), typiquement un corps (exemples importants : $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ ou bien $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$). Un \textbf{polynôme} en $t$ à coefficients dans $k$ est une somme formelle $f = a_0 + a_1 t + a_2 t^2 + \cdots$ avec $a_i \in k$ où \emph{seul un nombre fini} des $a_i$ est non nul (sinon on parle de \textbf{série formelle}). Autrement dit, on peut écrire $f = a_0 + a_1 t + \cdots + a_n t^n$ pour un certain $n$ (et si on impose $a_n \neq 0$, ceci définit $n$, qui s'appellera alors le degré de $f$). \textbf{Opérations :} \begin{itemize} \item Addition : terme à terme ($c_i = a_i+b_i$). \item Multiplication : « produit de Cauchy » en développant formellement ($c_i = \sum_{j=0}^{j=i} a_j b_{i-j}$). \end{itemize} Si $k$ est un anneau commutatif, alors $k[t]$ aussi. \textbf{Degré} d'un polynôme : $\deg f =$ le plus grand $i$ tel que $a_i \neq 0$ (le degré du polynôme nul est question de convention). On peut donc écrire un polynôme de degré $\leq N$ comme $a_0 + \cdots + a_N t^N$ ; si $a_N = 1$ on dit que $f$ est \textbf{unitaire}. Plus généralement, le coefficient $a_{\deg f}$ s'appelle \emph{coefficient dominant} de $f$. \textbf{Propriétés} du degré : \begin{itemize} \item $\deg (f+g) \leq \max(\deg f, \deg g)$ (avec égalité si $\deg f \neq \deg g$) \item $\deg (fg) = \deg f + \deg g$ (dès que $k$ est \emph{intègre}, en particulier sur un corps) \end{itemize} Si $k$ est un anneau commutatif intègre, alors $k[t]$ aussi. Attention, $k[t]$ n'est jamais un corps ! (Car $t$ n'a pas d'inverse pour la multiplication.) \medbreak À souligner : \emph{analogie} importante entre les polyômes, notamment dans $\mathbb{F}_p[t]$, et l'écriture en base $p$ des entiers. Différence importante : pas de retenue pour les polynômes. Complexité des opérations : cf. entiers. % \subsection{Opérations spécifiques aux polynômes} \textbf{Évaluation} de polynômes : si $f = a_0 + \cdots + a_N t^N$ et $x$ est dans $k$ ou $k[t]$ (ou plus généralement une « $k$-algèbre »), on définit $f(x) = a_0 + \cdots + a_N x^N$. Cas particulier : \textbf{composition} : si $g \in k[t]$, on note $f\circ g$ plutôt que $f(g)$. \medbreak \textbf{Racines :} si $f(x) = 0$ avec $x \in k$, on dit que $x$ est une \emph{racine} du polynôme $f$. \textbf{Attention :} On peut très bien avoir $f(x) = 0$ pour tout $x \in k$ sans pour autant que $f$ soit nul (e.g., $f = t^p - t$ dans $\mathbb{F}_p[t]$). (Mais on va voir que si $k$ est un corps, le nombre de racines de $f$ dans $k$ est inférieur ou égal au degré de $f$.) \medbreak \textbf{Dérivée :} si $f = a_0 + a_1 t + \cdots + a_N t^N$ alors $f' = a_1 + 2 a_2 t + \cdots + N a_N t^{N-1}$. \textbf{Attention :} On peut avoir $f'=0$ sans avoir $f$ constant (e.g., $f = t^p$ dans $\mathbb{F}_p[t]$). \textbf{Dérivées successives :} $f^{(i+1)} = (f^{(i)})'$ pour $i \in \mathbb{N}$. % \subsection{Polynôme interpolateur} Dans cette section, soit $k$ un \emph{corps} et $f \in k[t]$. \medskip \textbf{Fait fondamental :} lorsque deux polynômes de degré $\leq N$ coïncident en (au moins) $N+1$ points, ils sont égaux ; de façon équivalente, si un polynôme de degré $\leq N$ s'annule en $\geq N+1$ points, alors c'est le polynôme nul. Réciproquement, si $a_0,\ldots,a_N \in k$ sont deux à deux distincts, et $b_0,\ldots,b_N\in k$ sont quelconques, alors \[ \sum_{i=0}^N b_i \frac{\prod_{j\neq i}(t-a_j)}{\prod_{j\neq i}(a_i-a_j)} \] (\emph{polynôme interpolateur de Lagrange}) est un polynôme de degré $\leq N$ prenant en $a_i$ la valeur $b_i$. D'après ce qu'on vient de dire, c'est \emph{le} seul polynôme de degré $\leq N$ prenant en chaque $a_i$ la valeur $b_i$. Ceci permet de reconstruire un polynôme à partir de ses valeurs en suffisamment de points. % \subsection{Division euclidienne de polynômes} Sauf mention du contraire, $k$ est maintenant un \textbf{corps}. \smallskip \textbf{Division euclidienne} analogue à celle des entiers : Si $f\in k[t]$ et $g\in k[t]$ est \emph{non nul}, il existe un unique couple $(q,r)$ tel que : \begin{itemize} \item $q \in k[t]$, \item $r \in k[t]$ est (nul ou) de degré $\deg r < \deg g$ et \item $f = gq + r$. \end{itemize} \medbreak \textbf{Algorithme « naïf »} de division euclidienne : procéder par puissances \emph{décroissantes} : Soit $f = a_N t^N + \cdots + a_0$ et $g = b_D t^D + \cdots + b_0$ où $b_D \neq 0$ (donc $\deg g = D$) : \begin{itemize} \item si $N