First part: integers.

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}