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} |