$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Lien copié  ✅

Tests de primalité : les tests faciles

Division et crible d'Erathosthène

A part peut-être Gauss, on a tous commencé par tester la primalité d'un entier de façon naïve. Rappelons que :

Un entier $n$ est premier si et seulement si ses seuls diviseurs sont $1$ et $n$.

Il suffit donc de parcourir tous les entiers entre $2$ et $n-1$, puis de tester si cet entier divise $n$. Bien sûr, il est facile d'améliorer cet algorithme : si $n$ n'est pas premier, un de ces diviseurs est plus petit que $sqrt(n)$. Il ne suffit donc que de tester les entiers entre $2$ et $sqrt(n)$. La complexité de l'algorithme (le nombre d'opérations qu'il doit faire) est donc en :

$$\sqrt n = \exp\left(\frac{1}{2} \log n \right)$$

Ceci est beaucoup plus grand que le $C(\log n)^k$ voulu : l'algorithme est ici exponentiel.

Dans le même ordre d'idées, citons le crible d'Erathostène, qui permet de fabriquer tous les premiers entre $2$ et $n$. Rappelons comment il fonctionne : on écrit tous les entiers entre $2$ et $n$. Le premier entier écrit est $2$ : il est premier, et on barre tous ses multiples. L'entier suivant non barré est $3$ : il est premier et on barre tous ses multiples. On continue ainsi de suite, les entiers non barrés (et donc premiers) suivants sont : $5$, $7$, ...

Les divisions et le crible d'Erathotène sont assez efficaces pour de petits entiers. Mais dès que ces entiers dépassent $50$ chiffres, ils deviennent inutilisables : ils sont donc insuffisants puisque on a besoin couramment de fabriquer des nombres premiers à plusieurs milliers de chiffres. Pour de tels nombres, il faut totalement changer de méthode.

Les plus grands nombres premiers du monde
Définition : Si $p$ est un nombre premier, le nombre de Mersenne d'indice $p$ est le nombre $M_p = 2^p-1$.

Ces nombres de Mersenne ne sont pas tous premiers (ce serait trop faciles), et d'ailleurs il y en a relativement peu qui le sont effectivement : on ne sait même pas s'il y en a une infinité. En revanche, on dispose d'un test particulièrement efficace pour tester s'ils sont premiers, le test de Lucas-Lehmer :

Théorème : On définit une suite $(S_n)$ en posant :
  • $S_2 = 4.$
  • $S_n = (S_{n-1})^2 - 2.$
Alors $M_p$ est premier si et seulement si $M_p$ divise $S_p$.

Avec des notations plus mathématiques, $M_p$ est premier si, et seulement si, $S_p = 0 [ M_p ].$

Ce test est polynômial en le nombre de chiffres de $M_p$, puisqu'il faut calculer $p$ termes de la suite, et que $p$ est justement de l'ordre du nombre de chiffres de $M_p$. En outre, son implémentation informatique exploitant au mieux les particularités de l'arithmétique binaire est particulièrement efficace. C'est pourquoi le record du plus grand nombre premier jamais obtenu est toujours battu à l'aide de nombres de Mersenne. A titre d'exemple, $M_{13466917}$ possède $4 053946$ chiffres décimaux !

Pourtant, ces nombres premiers ne sont jamais utilisés pour la cryptographie. Ils sont bien trop particuliers, puisque l'on sait que ($M_{p}+1$) est une puissance de $2$. Les chasseurs de code auraient alors beaucoup trop d'informations ! Non, pour de telles applications, il n'y a rien de mieux qu'un nombre premier choisi totalement au hasard. Et pour cela, il n'y a rien de mieux que de tirer aléatoirement un nombre de $1000$ chiffres, puis de tester s'il est premier. Nous revoici à notre point de départ....