371. Le test de Miller

Il s’agit d’un test de calcul modulaire qui permet de démontrer, sans effectuer de divisions successives, qu’un nombre donné n’est pas premier.

Démontrez un lemme

Pour tout entier naturel $n$ supérieur ou égal à $2$ vous notez $\mathscr{P}(n)$ la propriété « il existe un entier naturel $t$ et un entier naturel impair $q$ tels que $n = 2^t q$ ».

Initialisation. Pour $n=2\comma$ vous posez $t = 1$ et $q=1.$ Vous avez bien $2^t q = 2^1 \times 1 = 2 = n.$ Donc $\mathscr{P}(2)$ est vraie.

Hérédité. Soit $n$ un entier supérieur ou égal à $2.$ Supposez que $\mathscr{P}(2),\dots, \mathscr{P}(n)$ soient vraies.

Notez déjà que $n+1\geq 3.$ Si $n+1$ est impair, alors vous posez $t = 0$ et $q = n+1.$ Vous avez immédiatement $2^t q = 2^0 \times (n+1) = n+1.$

Si $n+1$ est pair, il s’ensuit que $n+1\geq 4.$ Alors $m = \frac{n+1}{2}$ est un entier supérieur ou égal à $2.$

Comme $n\geq 1$ il vient $2n \geq n+1$ et donc $\frac{n+1}{2}\leq n.$

Comme $m\in\llbracket 2, n\rrbracket$ vous appliquez l’hypothèse de récurrence. Il existe un entier naturel $t’$ et un entier naturel impair $q$ tels que $m = 2^{t’} q.$ Du coup $2m = 2^{1+t’}q$ ce qui s’écrit $n+1 = 2^{1+t’} q.$ En posant $t = 1+t’$ vous constatez que $t\in\N$ et vous avez bien $n+1 = 2^t q.$

Dans les deux cas, $\mathscr{P}(n+1)$ est vraie.

Conclusion. Par récurrence forte, il a été démontré que :

\boxed{\forall n\in\N, n\geq 2\implies (\exists t \in\N, \exists q\in\N, n = 2^tq\text{ et }q\text{ est impair}).}

Soient $t, q, u, r$ quatre entiers naturels avec $2^t q = 2^u r$ et $q$ et $r$ impairs.

Si $t\gt u$ alors $t\geq u+1.$ En simplifiant par $2^u\comma$ vous avez $2^{t-u} q = r.$ Or, $t-u \geq 1$ donc $2^{t-u}q$ est pair. Or $r$ est impair, contradiction.

Si $u\gt t$ alors $u\geq t+1.$ En simplifiant par $2^t\comma$ vous avez $q = 2^{u-t} r.$ Or, $u-t \geq 1$ donc $2^{u-t}r$ est pair. Or $q$ est impair, contradiction.

Du coup, $u=t.$ Ainsi $2^t q = 2^t r$ et $q=r.$

En définitive l’unicité est démontrée.

\boxed{\forall n\in\N, n\geq 2\implies (\exists ! (t,q) \in\N^2, n = 2^tq\text{ et }q\text{ est impair}).}

Descriptif du test de Miller en base $b$

Soit $b$ un nombre entier supérieur ou égal à $2$ appelé base.

Soit $n$ un entier naturel impair supérieur ou égal à $3.$ Comme $n-1\geq 2\comma$ d’après le lemme, il existe un unique entier naturel $t$ et un unique entier naturel impair $q$ tels que $n-1 = 2^t q.$ Notez que $t=0$ entraîne $n-1 =q$ et $n-1$ serait impair donc $n$ serait pair ce qui est absurde, donc $t \geq 1.$

Vous direz que $n$ passe le test de Miller en base $b\comma$ si et seulement si :

\boxed{(b^q\equiv 1 \mod n) \text{ ou } (\exists s\in\llbracket 0, t-1\rrbracket, b^{2^s q}\equiv -1 \mod n).}

Note. Un nombre entier impair supérieur ou égal à $3$ qui passe le test de Miller en base $b$ peut ne pas être premier. Dans ce dernier cas précis, il est qualifié de nombre pseudo-premier fort en base $b.$

L’intérêt du test de Miller réside dans le théorème ci-dessous.

Tout nombre premier $p$ impair passe le test de Miller en base $b$ dès que $b$ n’est pas multiple de $p$

Soit $b$ un nombre entier supérieur ou égal à $2$ appelé base.

Soit $p$ un nombre premier impair tel que $b$ ne soit pas un multiple de $p.$

Comme $p$ est impair, $p\geq 3$ et $p-1\geq 2.$ D’après le lemme, il existe un unique entier naturel $t$ et un unique entier naturel impair $q$ tels que $p-1 = 2^t q.$ Comme $p-1$ est pair, $t\geq 1.$

S’il existe $s\in\llbracket 0, t-1\rrbracket$ tel que $b^{2^s q}\equiv -1 \mod p$ alors $p$ passe le test de Miller en base $b.$

Si un tel entier $s$ n’existe pas, cela signifie ce qui suit :

\forall s\in\llbracket 0, t-1\rrbracket, b^{2^sq}\not\equiv -1 \mod p.

Pour tout entier naturel $u$ vous notez $\mathscr{P}(u)$ la propriété « $b^{2^u q} \equiv 1 \mod p$ ». Vous procédez par récurrence descendante.

Initialisation. Pour $u = t$ vous cherchez à évaluer $b^{2^uq} = b^{2^tq} = b^{p-1}.$ Comme $\pgcd(b,p)$ divise $p\comma$ ce nombre vaut $1$ ou $p$ car $p$ est premier. Si $\pgcd(b,p)=p$ alors $p$ divise $b$ ce qui est absurde. Donc $\pgcd(b,p)=1.$ L’application du petit théorème de Fermat fournit $b^{p-1} \equiv 1\mod p$ ce qui prouve que $\mathscr{P}(t)$ est vraie.

Caractère descendant. Soit $u$ un nombre entier appartenant à l’intervalle $\llbracket 1, t \rrbracket.$ Supposez $\mathscr{P}(u)$ vraie.

Alors $b^{2^u q} \equiv 1 \mod p.$ Vous en déduisez que :

\begin{align*} \left(b^{2^{u-1} q}\right)^2 \equiv 1 \mod p\\ \left(b^{2^{u-1} q}\right)^2 -1^2 \equiv 0 \mod p\\ \left(b^{2^{u-1} q}-1\right)\left(b^{2^{u-1} q}+1\right) \equiv 0 \mod p. \end{align*}

Donc $p$ divise le produit $\left(b^{2^{u-1} q}-1\right)\left(b^{2^{u-1} q}+1\right).$

Cependant, notez que $u-1\in\llbracket 0, t-1\rrbracket$ donc, par hypothèse, $b^{2^{u-1}q}\not\equiv -1 \mod p$ donc $p$ ne divise pas $b^{2^{u-1} q}+1.$

En utilisant le lemme d’Euclide, vous déduisez que $p$ divise $b^{2^{u-1} q}-1$ et donc $b^{2^{u-1} q}\equiv 1 \mod p.$

La propriété $\mathscr{P}(u-1)$ est vraie.

Conclusion. Il a été démontré par récurrence descendante que $\mathscr{P}(0)$ est vraie, autrement dit $b^{2^0 q} \equiv 1 \mod p$ ce qui fournit $b^{ q} \equiv 1 \mod p.$

Ainsi $p$ passe le test de Miller en base $b.$

Application : démontrez que $1387$ n’est pas un nombre premier

Tout nombre premier impair $p$ passe le test de Miller en base $b$ dès que $\pgcd(b,p)=1.$

Par contraposée, si $n$ est un nombre entier impair supérieur ou égal à $3$ de sorte que :

il existe une base $b$ vérifiant $\pgcd(b,n)=1$
le nombre $n$ ne passe pas le test de Miller en base $b$

alors $n$ n’est pas premier.

Note. En pratique la base $b$ est choisie pour être strictement inférieure à $n$. S’il s’avère que $\pgcd(b,n)\geq 2$ alors ce nombre est déjà un diviseur de $n$ compris entre $2$ et $n-1.$ Il est inutile de pratiquer le test de Miller puisque $n$ est déjà non premier.

Pour le nombre $n = 1387$ vous choisissez $b=2$ pour base. Comme $1387$ est impair, $\pgcd(n,b)=1.$ Vous appliquez le test de Miller à $1387$ en base $2.$

Tout d’abord :

\begin{align*} n-1 &= 1386\\ &= 2\times 693. \end{align*}

Comme $693$ est impair, vous avez $t = 1$ et $q = 693.$ Le test se réduit donc à vérifier si $2^{693}$ est congru à $1$ ou à $-1$ modulo $1387.$

Vous évaluez $2^{693} \mod 1387.$

D’une part :

\begin{align*} 2^{10}&\equiv 1024 \mod 1387\\ 2^{20}&\equiv 1024^2 \mod 1387\\ 2^{20}&\equiv 1048576 \mod 1387\\ 2^{20}&\equiv 756\times 1387+ 4 \mod 1387\\ 2^{20}&\equiv 2^2 \mod 1387. \end{align*}

Comme $\pgcd(2, 1387)=1$ vous pouvez simplifier la congruence deux fois par $2$ grâce au théorème de Gauss, ce qui fournit :

\boxed{2^{18}\equiv 1\mod 1387.}

D’autre part, vous effectuez la division euclidienne de $693$ par $18$ ce qui fournit :

693 = 18\times 38 + 9.

Du coup :

\begin{align*} 2^{693} &\equiv 2^9 \times (2^{18})^{38} \mod 1387\\ &\equiv 512\mod 1387. \end{align*}

Comme $2^{693}$ n’est ni congru à $1$ ni congru à $-1$ modulo $1387\comma$ $1387$ ne passe pas le test de Miller en base $2$ donc $1387$ n’est pas premier.

Application : démontrez que le nombre $1\,373\,653$ n’est pas premier

Il s’agit de déterminer $t$ et $q.$

Vous notez $n = 1\,373\,653$ et par suite :

\begin{align*} n-1 &= 1\,373\,652 \\ &= 2\times 686\,826\\ &= 4\times 343\,413. \end{align*}

Comme $343\,413$ est impair, vous avez $t=2$ et $q=343\,413.$ Le nombre $n$ passe le test de Miller en base $b$ si et seulement si $b^{343\,413}$ est congru à $1$ ou à $-1\comma$ ou si $b^{686\,826}$ est congru à $-1$ modulo $n.$

Vous choisissez $b=5$ pour base. Le chiffre des unités de $1\,373\,653$ étant $3\comma$ ce nombre n’est pas divisible par $5\comma$ qui est premier, donc $\pgcd(5, n)=1.$ Vous allez effectuer le calcul de $5^{343\,413}$ modulo $1\,373\,653.$ Pour plus de lisibilité, les congruences qui suivent sont toutes effectuées modulo $1\,373\,653.$

\begin{align*} 5^2 &= 25\\ 5^4 &= 25^2 =625 \\ 5^8 &= 625^2 = 390\,625\\ 5^{16} &\equiv 390\,625^2 \equiv 152\,587\,890\,625 \equiv 1\,373\,653\times 111\,081 + 1\,141\,732\\ 5^{16} &\equiv 1\,141\,732\\ 5^{32} &\equiv 1\,141\,732^2 \equiv 1\,303\,551\,959\,824 \equiv 948\,967\times 1\,373\,653+593\,373\\ 5^{32} &\equiv 593\,373\\ 5^{64} &\equiv 593\,373^2 \equiv 352\,091\,517\,129 \equiv 256\,317\times 1\,373\,653+901\,128\\ 5^{64} &\equiv 901\,128\\ 5^{128} &\equiv 901\,128^2 \equiv 812\,031\,672\,384 \equiv 591\,147\times 1\,373\,653+822\,393\\ 5^{128} &\equiv 822\,393 \end{align*}

\begin{align*} 5^{256} &\equiv 822\,393^2 \equiv 676\,330\,246\,449 \equiv 492\,358\times 1\,373\,653 + 1\,202\,675\\ 5^{256} &\equiv 1\,202\,675\\ 5^{512} &\equiv 1\,202\,675^2 \equiv 1\,446\,427\,155\,625 \equiv 1\,052\,978\times 1\,373\,653+ 766\,991\\ 5^{512} &\equiv 766\,991\\ 5^{1024} &\equiv 766\,991^2 \equiv 588\,275\,194\,081 \equiv 428\,256\times 1\,373\,653+ 54\,913\\ 5^{1024} &\equiv 54\,913\\ 5^{2048} &\equiv 54\,913^2 \equiv 3\,015\,437\,569 \equiv 2\,195\times 1\,373\,653+ 269\,234\\ 5^{2048} &\equiv 269\,234\\ 5^{4096} &\equiv 269\,234^2 \equiv 72\,486\,946\,756 \equiv 52\,769\times 1\,373\,653+ 651\,599\\ 5^{4096} &\equiv 651\,599 \end{align*}

\begin{align*} 5^{8192} &\equiv 651\,599^2 \equiv 424\,581\,256\,801 \equiv 309\,089\times 1\,373\,653 + 224\,684\\ 5^{8192} &\equiv 224\,684\\ 5^{16384} &\equiv 224\,684^2 \equiv 50\,482\,899\,856 \equiv 36\,750\times 1\,373\,653 + 1\,152\,106\\ 5^{16384} &\equiv 1\,152\,106\\ 5^{32768} &\equiv 1\,152\,106^2 \equiv 1\,327\,348\,235\,236 \equiv 966\,290\times 1\,373\,653 + 1\,077\,866\\ 5^{32768} &\equiv 1\,077\,866\\ 5^{65536} &\equiv 1\,077\,866^2 \equiv 1\,161\,795\,113\,956 \equiv 845\,770\times 1\,373\,653 + 616\,146\\ 5^{65536} &\equiv 616\,146\\ 5^{131072} &\equiv 616\,146^2 \equiv 379\,635\,893\,316 \equiv 276\,369\times 1\,373\,653 + 787\,359\\ 5^{131072} &\equiv 787\,359 \end{align*}

\begin{align*} 5^{262144} &\equiv 787\,359^2 \equiv 619\,934\,194\,881 \equiv 451\,303\times 1\,373\,653 + 475\,022\\ 5^{262144} &\equiv 475\,022. \end{align*}

Vous décomposez $343\,413$ comme une somme de puissances de $2$ à l’aide de soustractions.

\begin{align*} 343\,413 -262\,144 &= 81\,269\\ 81\,269 – 65\,536&=15\,733\\ 15\,733 – 8\,192 &=7\,541\\ 7\,541 – 4\,096 &= 3\,445\\ 3\,445- 2\,048 &=1\,397\\ 1\,397-1\,024 &= 373\\ 373 – 256 &= 117\\ 117-64 &= 53\\ 53 – 32 &= 21\\ 21- 16 &= 5\\ 5- 4 &=1. \end{align*}

Cela montre que :

\begin{align*} 343\,413 &= 262\,144+65\,536+8\,192\\ &\quad+4\,096+2\,048+1\,024\\ &\quad+256+64+32\\ &\quad+16+4+1. \end{align*}

Vous calculez les puissances suivantes :

\begin{align*} 5^{262\,144}\times 5^{65\,536}\times 5^{8\,192} &\equiv 475\,022\times 616\,146 \times 224\,684\\ &\equiv 65\,761\,165\,874\,653\,008\\ &\equiv 47\,873\,200\,782\times 1\,373\,653 + 856\,362\\ &\equiv 856\,362 \end{align*}

\begin{align*} 5^{4\,096}\times 5^{2\,048}\times 5^{1\,024} &\equiv 651\,599\times 269\,234 \times 54\,913\\ &\equiv 9\,633\,530\,647\,480\,558\\ &\equiv 7\,013\,074\,369\times 1\,373\,653 + 1\,280\,601\\ &\equiv 1\,280\,601 \end{align*}

\begin{align*} 5^{256}\times 5^{64}\times 5^{32} &\equiv 1\,202\,675\times 901\,128 \times 593\,373\\ &\equiv 643\,076\,365\,633\,990\,200\\ &\equiv 468\,150\,519\,551\times 1\,373\,653 + 1\,200\,397\\ &\equiv 1\,200\,397 \end{align*}

\begin{align*} 5^{16}\times 5^{4}\times 5^{1} &\equiv 1\,141\,732 \times 625 \times 5\\ &\equiv 3\,567\,912\,500\\ &\equiv 2\,597\times 1\,373\,653 + 535\,659\\ &\equiv 535\,659. \end{align*}

Puis :

\begin{align*} 5^{343\,413} &\equiv 856\,362\times 1\,280\,601 \times 1\,200\,397 \times 535\,659\\ &\equiv 705\,154\,906\,313\,747\,945\,181\,126\\ &\equiv 513\,342\,821\,159\,163\,154 \times 1\,373\,653 +1\,199\,564\\ &\equiv 1\,199\,564. \end{align*}

Vous calculez $5^{686\,826}$ comme suit :

\begin{align*} 5^{686\,826} &\equiv 5^{343\,413\times 2}\\ &\equiv (5^{343\,413})^2\\ &\equiv 1\,199\,564^2\\ &\equiv 1\,438\,953\,790\,096\\ &\equiv 1\,047\,538\times 1\,373\,653+73\,782\\ &\equiv 73\,782. \end{align*}

Comme $-1\equiv 1\,373\,652$ modulo $1\,373\,653\comma$ il a été démontré que :

\left\{\begin{align*} 5^{343\,413}&\not\equiv 1\\ 5^{343\,413}&\not\equiv -1\\ 5^{686\,826}&\not\equiv -1. \end{align*} \right.

Cela prouve que le nombre $1\,373\,653$ ne passe pas le test de Miller en base $5.$ Ainsi $1\,373\,653$ n’est pas un nombre premier.

Prolongements

Première partie

Soit $n$ un nombre entier impair supérieur ou égal à $3$ et strictement inférieur à $2\,047.$

Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2.$

Deuxième partie

Soit $n$ un nombre entier impair supérieur ou égal à $3$ et strictement inférieur à $10\,000.$

Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2$ et s’il n’appartient pas à l’ensemble $A$ suivant :

A=\{2\,047, 3\,277, 4\,033, 4\,681, 8\,321\}.

Troisième partie

Soit $n$ un nombre entier impair supérieur ou égal à $3$ et strictement inférieur à $1\,373\,653.$

Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2$ et en base $3.$