diff options
| -rw-r--r-- | rappels-maths.tex | 380 |
1 files changed, 380 insertions, 0 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex new file mode 100644 index 0000000..badb046 --- /dev/null +++ b/rappels-maths.tex @@ -0,0 +1,380 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt]{article} +\usepackage[francais]{babel} +\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}} +\renewcommand{\qedsymbol}{\smiley} +% +% +% +\begin{document} +\title{Rappels maths pour crypto} +\author{David A. Madore} +\maketitle +{\footnotesize +\begin{center} +CVS: \verb=$Id: rappels-maths.tex,v 1.1 2008-09-29 18:58:04 david Exp $= +\end{center} +\par} +\pretolerance=10000 +\tolerance=8000 +% +% +% +\section{Entiers} + +\subsection{L'anneau des entiers} + +$\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ ensemble des +entiers relatifs. Sous-ensemble $\mathbb{N}$. + +Opérations : $+$, $\times$. + +Rappeler : $(\mathbb{Z},0,+)$ est un groupe abélien, +$(\mathbb{Z},0,+,1,\times)$ est un anneau commutatif. + +Mieux : anneau intègre. + +Éléments inversibles : $1$ et $-1$. + +Relation d'ordre... + +% +\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_i<b$ +entiers naturels « presque tous nuls » (expliquer). + +Écriture usuelle : $b=10$. Informatique : $b=2$. Un nombre « de $n$ +bits » signifie : inférieur à $2^n$. + +Multiplier par $b$ revient à décaler tous les chiffres d'un cran vers +la gauche. + +On passe pour l'instant sur l'écriture des nombres négatifs. + +% +\subsection{Remarques sur la complexité des opérations} + +Addition de nombres de $n$ bits : algorithme naïf en $O(n)$. + +Multiplication : plus compliqué. + +Algorithme naïf en $O(n^2)$. + +\emph{Multiplication de Karatsuba} : utilise récursivement +l'identité ${(a_1 w + a_0)} \penalty0 {(b_1 w + b_0)} = a_1 b_1 w^2 + +[(a_1+a_0)(b_1+b_0)-a_1 b_1-a_0 b_0] w + a_0 b_0$ pour une complexité +en $O(n^{\frac{\log 3}{\log 2}})$ (soit $O(n^{1.58\ldots})$). Facile +à implémenter. + +\emph{Multiplication de Strassen} : par transformée de Fourier +rapide, complexité en $O(n\,\log^2 n)$, difficile à implémenter. +Amélioration de Schönhage : $O(n\,\log n\,\log\log n)$ --- +complètement théorique. + +% +\subsection{Divisiblité (exacte)} + +Définition. Réflexive, transitive. Pas tout à fait antisymétrique +(mais vrai dans les entiers naturels). + +Note : Les entiers $1$ et $-1$ divisent tous les entiers. L'entier +$0$ est divisible par tous les entiers. + +% +\subsection{Nombres premiers} + +Un \textbf{nombre premier} $p$ est un entier (par convention : +positif) divisible seulement par $1$, $-1$, lui-même et son opposé ; +mais par convention, $1$ et $-1$ (et $0$...) ne sont pas premiers. + +Sur leur répartition : + +Il y en a une infinité (Euclide). + +Pour tout $x>1$, il y a toujours un nombre premier $p$ tel que +$x\leq p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand »). + +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 »). + +\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$. + +% +\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ß), inégalité sur la +somme (et cas d'égalité)... Dire que $x \in \mathbb{Q}$ est entier +signifie exactement $v_p(x) \geq 0$ pour tout $p$. + +% +\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 r<b$, et +\item $a = bq + r$. +\end{itemize} +On dit que $q$ est le \emph{quotient} et $r$ le \emph{reste} de la +\textbf{division euclidienne} de $a$ par $b$. (On appelle aussi $a$ +le \emph{dividende} et $b$ le \emph{diviseur}.) + +Si $b\geq 2$, dans l'écriture $b$-adique de $a$, le dernier chiffre +($a_0$ avec les notations précédentes) est égal au reste $r$ de la +division euclidienne de $a$ par $b$. + +Dire que $r=0$ signifie exactement que $b$ divise $a$ (la division +euclidienne est alors \emph{exacte}). + +\medbreak + +\textbf{Algorithme naïf :} (celui de l'école primaire) en $O(n^2)$. + +\textbf{Algorithme sophistiqué :} en $O(n\,\log n\,\log\log n)$ avec +Schönhage-Strassen + méthode de Newton (+ subtilités). + +Méthode de Newton : on inverse $b$ (en précision fixe) en itérant $x +\leftarrow 2x - bx^2$. + +Souvent implémentée \textbf{en matériel} pour certaines tailles +d'entiers (p. ex., division entière de 128 bits par 64 bits). + +% +\subsection{PGCD} + +Si $m_1,\ldots,m_\ell$ sont des entiers, on dit qu'un entier $c$ est +un \textbf{plus grand commun diviseur} (en abrégé : \emph{pgcd}) des +$m_i$ lorsque : +\begin{itemize} +\item $c$ divise chaque $m_i$ (i.e, $c$ est un diviseur commun + des $m_i$), et +\item tout entier $d$ qui divise chaque $m_i$ (i.e., tout diviseur + commun des $m_i$) divise aussi $c$. +\end{itemize} +En principe, le pgcd des $m_i$ est défini au signe près (si $c$ est un +pgcd des $m_i$ alors $-c$ l'est aussi) : en imposant qu'il soit +positif il devient unique et on parle alors \emph{du} pgcd des $m_i$. + +Exemple : le pgcd de $6$ et $10$ est $2$ ; le pgcd de + $6$, $10$ et $15$ est $1$. + +\medbreak + +Le pgcd \emph{existe} toujours : on peut le trouver à partir de la +décomposition en facteurs premiers par +\[ +v_p(\pgcd(m_1,\ldots,m_\ell)) = \min(v_p(m_1),\ldots,v_p(m_\ell)) +\] +(pour tout nombre premier $p$). Mais ce n'est pas une méthode +efficace de calcul ! + +\textbf{Notation :} Parfois $m_1\wedge \cdots \wedge m_\ell$, mais +cette notation peut être utilisée pour d'autres sortes de bornes inf. +Certains textes anglais utilisent $(m,m')$ pour le pgcd de deux +entiers. La notation $\pgcd(\cdots)$ est évidemment la plus claire. + +\medbreak + +\textbf{Quelques propriétés :} +\begin{itemize} +\item le pgcd d'un seul entier $m$ est lui-même (et le pgcd de zéro +entiers est $0$), +\item le pgcd est associatif (par exemple\\ + $\pgcd(m_1,m_2,m_3) = \pgcd(\pgcd(m_1,m_2),m_3)$), +\item le produit est distributif sur le pgcd\\ + ($\pgcd(cm_1,\ldots,cm_\ell) = |c|\,\pgcd(m_1,\ldots,m_\ell)$), +\item on peut toujours effacer des $0$ d'un pgcd, +\item dès qu'un des entiers est $1$ ou $-1$, le pgcd est $1$, +\item le pgcd d'une famille infinie se définit sans difficulté. +\end{itemize} + +% +\subsection{Entiers premiers entre eux} + +Lorsque $\pgcd(m_1,\ldots,m_\ell)=1$, on dit que les $m_i$ sont +\textbf{premiers entre eux} \emph{dans leur ensemble}. + +Lorsque $\pgcd(m_i,m_j)=1$ pour tous $i\neq j$, on dit que les $m_i$ +sont premiers entre eux \emph{deux à deux}. + +\textbf{Lemme de Gauß amélioré :} Si $m$ et $n$ sont premiers entre +eux, être multiple de $m$ et de $n$ équivaut à être multiple de $mn$. + +\textbf{Dirichlet :} La probabilité pour que deux entiers « tirés au + hasard » soient premiers entre eux est $\frac{6}{\pi^2}$. + +% +\subsection{PPCM} + +Définition analogue au PGCD. Exemple : le ppcm de $6$ et $10$ +est $30$ ; le ppcm de $6$, $10$ et $15$ est aussi $30$. Lien avec la +DFP (pour un nombre fini d'entiers). Le ppcm d'une famille infinie +d'entiers est défini, mais parfois surprenant (quel est le PPCM de +tous les nombres premiers ?). + +% +\subsection{Relation de Bézout} + +Si $a$ et $b$ sont premiers entre eux (c'est-à-dire $\pgcd(a,b) = 1$) +il existe des entiers $u$ et $v$ tels que $au + bv = 1$ (on verra +pourquoi plus loin) : on appelle cette égalité une \textbf{relation de + Bézout}\footnote{Étienne Bézout (1730--1783), avec un accent aigu.} +entre $a$ et $b$. + +Réciproquement, l'existence d'une relation de Bézout entre $a$ et $b$ +implique que $a$ et $b$ sont premiers entre eux (et alors les +coefficients, $u$ et $v$, sont aussi premiers entre eux). En effet, +tout diviseur commun de $a$ et $b$ doit diviser $au+bv$. + +Exemple : $42\times 38 - 55 \times 29 = 1$ constitue une relation de +Bézout entre $42$ et $55$. On verra plus loin comment obtenir une +relation de Bézout. + +Naturellement, ajouter $b$ à $u$ et $-a$ à $v$ donne une nouvelle +relation de Bézout entre $a$ et $b$. Donc il n'y a pas unicité. + +Si $au + bv = \pm 1$ on dit parfois que les rationnels $a/b$ et $-v/u$ +(écrits sous forme irréductible) sont \emph{adjacents}. + +% +\subsection{Algorithme d'Euclide} + +Soit à calculer le pgcd de deux entiers $a$ et $b$. +\textbf{L'algorithme d'Euclide} pour ce faire est le suivant : +\begin{itemize} +\item Initialiser : $(m,n) \leftarrow (|a|,|b|)$. +\item Tant que $n\neq 0$, répéter : +\begin{itemize} +\item Faire $(m,n) \leftarrow (n,r)$ où $r$ est le reste de la division + euclidienne $m=nq+r$ de $m$ par $n$. +\end{itemize} +\item Renvoyer $m$ (le pgcd recherché). +\end{itemize} + +\smallskip +\textbf{Invariant :} $\pgcd(m,n) = \pgcd(a,b)$ (constant) + +\medbreak +Exemple : soit à calculer le pgcd de $a=98$ et +$b=77$ : +\begin{itemize} +\item $(m,n)=(98,77)$ ; division euclidienne $98 = 77\times 1 + 21$ ; +\item $(m,n)=(77,21)$ ; division euclidienne $77 = 21\times 3 + 14$ ; +\item $(m,n)=(21,14)$ ; division euclidienne $21 = 14\times 1 + 7$ ; +\item $(m,n)=(14,7)$ ; division euclidienne $14 = 7\times 2 + 0$ ; +\item $(m,n)=(7,0)$ ; on renvoie $7$. +\end{itemize} + +\medbreak +\textbf{Algorithme d'Euclide « étendu »} : L'idée est +de « remonter » les coefficients dans l'algorithme d'Euclide : la +dernière division $m=nq+1$ donne une relation $1 = m-nq$ puis on +remplace $n$ (qui est lui-même un reste de division euclidienne) et +ainsi de suite jusqu'à trouver une relation entre les entiers $a$ et +$b$ de départ. + +En mémoire constante, cela donne : + +Soit à calculer une relation de Bézout entre deux entiers $a$ et $b$ +(premiers entre eux) : +\begin{itemize} +\item $(m,n,u,v,u',v') \leftarrow (|a|,|b|,\signe(a),0,0,\signe(b))$. +\item Tant que $n\neq 0$, répéter : +\begin{itemize} +\item Division euclidienne de $m$ par $n$ : soit $m = +nq+r$. +\item Remplacer $(m,n,u,v,u',v') \leftarrow (n,r,u',v',u-qu',v-qv')$. +\end{itemize} +\item Vérifier $m=1$ (le pgcd est bien $1$). +\item Les coefficients recherchés sont $u$ et $v$ (on a $au+bv = 1$). +\end{itemize} + +\textbf{Invariants :} $au+bv=m$ et $au'+bv'=n$. + +% +% +% +\end{document} |