arithmetique/testsPrimalite.tex

   1
   2
   3
   4 \section{Théorème de Fermat}
   5
   6 \begin{Th}[Petit théorème de Fermat]
   7  \index{théorème!petit théorème de Fermat}
   8 Si $n$ est premier et si $a\neq 0$, $a^n\equiv 1\ [n]$.
   9 \end{Th}
  10
  11 \begin{Exo}[Théorème de Fermat]
  12 Soit $n$ un nombre premier,
  13 \begin{enumerate}
  14 \item montrer que, pour $p$ entier tel que $0<p<n$, $n$
  15 divise $\cnp_n^p$
  16 \item montrer que, pour tout $a\in\N$, $(a+1)^n-a^n-1$ est
  17 divisible par $n$.
  18 \item montrer que, pour tout $b\in\N$, si
  19 $b^n-b$ est divisible par $n$, $(b+1)^n-(b+1)$ l'est aussi.
  20 \item En déduire le théorème de Fermat: pour $n$ premier et $a\in
  21 \N$, $a^n \equiv a\ [n]$.
  22 \end{enumerate}
  23 \end{Exo}
  24
  25
  26
  27 \begin{Exo}[Théorème de Wilson]
  28 Soit $p$ un nombre entier strictement supérieur à 1.
  29
  30 $(p-1)!+1$ est divisible par $p$ si et seulement si $p$ est premier.
  31
  32 On demande la démonstration de ce théorème.
  33 \end{Exo}
  34
  35
  36
  37
  38 Ce théorème ne peut servir de test de primalité, mais seulement de test de non-primalité. C'est-à-dire que si l'on trouve un nombre $a\not\equiv 0\ [n]$ tel que $a^{n-1}\not\equiv 1\ [n]$, on en conclut que $n$ est composé.\\
  39
  40 Les nombres $a$ tels que $a^{n-1}\equiv 1\ [n]$ alors que $n$ n'est pas premier ne sont pas nombreux. C'est pourquoi si, après l'essai de quelques valeurs de $a$, on trouve toujours $a^{n-1}\equiv 1\ [n]$, ce nombre $n$ sera envoyé à un véritable test de primalité.\\
  41
  42 Ce pré-test a l'avantage d'être simple et rapide.
  43
  44 \section{Test de Miller-Rabin}
  45 \index{test!de Miller-Rabin}
  46 Soit $n$ un nombre impair, que l'on met sous la forme $n-1=2^tm$, avec $m$
  47 impair.\\
  48
  49 \begin{Def}[Nombre pseudo-premier fort]
  50 Ce nombre $n$ est dit \emph{pseudo-premier fort dans la base $a$} \index{nombre!pseudo-premier fort} si l'on peut trouver $a$ tel que :
  51 \begin{itemize}
  52  \item ou bien $a^m\equiv 1\ [n]$,
  53 \item ou bien on peut trouver $u$ tel que $0\leqslant u\leqslant t-1$, $a^{2^um}\equiv -1\ [n]$.
  54 \end{itemize}
  55 \end{Def}
  56
  57
  58 On montre que :
  59
  60 \begin{Th}
  61 Tout nombre premier est pseudo-premier fort dans n'importe quelle base et qu'un nombre composé est pseudo-premier fort dans au plus $\fr n4$ bases différentes, et \og en général\fg{} aucune.
  62 \end{Th}
  63
  64
  65
  66 Bien entendu, dès que $n$ est un tant soit peu grand, il est exclu de tester autant de bases.\\
  67
  68 Il n'en reste pas moins que si, après une dizaine de bases, $n$ est pseudo-premier fort dans chacune de ces bases, il a de \og très bonnes chances\fg{} d'être premier.\\
  69
  70 Ce test n'est cependant pas, lui non plus, un véritable test de primalité, mais il est presque aussi rapide que celui de Fermat, et il sert d'aiguillage entre les nombres que l'on enverra à un algorithme de décomposition et ceux que l'on enverra plutôt à un véritable test de primalité.
  71
  72 \section{Tests de Lucas, Selfridge et Pocklington}
  73
  74
  75 Le test de Lucas peut s'exprimer de la manière suivante :
  76
  77 \begin{Th}[Test de Lucas]
  78 \index{test!de Lucas}
  79  Si on peut trouver un entier $a$ pour lequel $a^{n-1}\equiv 1\ [n]$, mais
  80 $a^{n-1\over q}\not\equiv 1\ [n]$ pour tous les diviseurs premiers $q$ de $n-1$, alors $n$ est premier.
  81 \end{Th}
  82
  83 \begin{Rem}
  84 Selfridge a montré qu'il n'était pas nécessaire d'utiliser la même valeur de $a$ pour tous ces diviseurs.
  85 \end{Rem}
  86
  87
  88
  89 Ce test est théoriquement satisfaisant (c'est un test qui peut répondre : \og oui, $n$ est premier\fg{}), pratiquement il l'est beaucoup moins : il exige la décomposition en facteurs premiers de $n-1$ qui est une opération en général longue et difficile (voir les algorithmes qui suivent).\\
  90
  91 De plus, il connaît un cas d'échec, dans lequel il ne donne pas de réponse.\\
  92
  93
  94 Le critère de Pocklington permet d'atténuer cette difficulté :
  95
  96 \begin{Th}[Critère de Pocklington]
  97  \index{critère!de Pocklington}
  98 Si $n$ n'est que \og partiellement décomposé \fg{}, dans le sens où il a été mis sous la forme $n=FR$, où $F$ est totalement décomposé en facteurs premiers, mais $R$ n'est pas premier, alors :
  99 \begin{itemize}
 100  \item si le critère de Selfridge appliqué aux diviseurs premiers de $F$ aboutit à un succès,
 101 \item et si $F>R$,
 102 \end{itemize}
 103  alors $n$ est premier.
 104 \end{Th}
 105
 106
 107 \gsaut
 108 \centerline{\x{Fin du Chapitre}}
 109