Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:tds:cryptographie:get_n_bits_prime [2023/04/11 10:41] – [Fonctionnement des tests] goupillwiki
+++ nsi:tds:cryptographie:get_n_bits_prime [2023/04/11 10:47] (Version actuelle) – [Principe mathématique du test] goupillwiki
@@ Ligne 40: / Ligne 40: @@
 Vous pouvez sauter si ça vous paraît trop compliqué/</WRAP>
-<wrap tip>On note $a \equiv b [c]$ si $a \mod c = b$.</wrap>
+<wrap tip>On note $a \equiv b [c]$ ou $a \overset{c}{\equiv} b$ si $a \mod c = b$.</wrap>
 Soit $p$ un nombre premier. Le [[https://fr.wikipedia.org/wiki/Petit_th%C3%A9or%C3%A8me_de_Fermat|petit théorème de Fermat]] nous dit que pour $2 \leqslant a < p$, on a $a^{p-1} = 1 [p]$.
-On sait aussi que si $X^2 \equiv 1 [p]$ alors $X \equiv 1 [p]$ ou $ \equiv -1 [p] \equiv p - 1 [p]$.
+On sait aussi que si $X^2 \overset{p}{\equiv} 1$ alors $X \overset{p}{\equiv} 1$ ou $X \overset{p}{\equiv} -1 \overset{p}{\equiv} p - 1$.
 L'idée est donc de chercher les racines carrés modulo des $p-1$ et de vérifier que le résultat est toujours $1$ ou $-1$.
-Pour cela on détermine $d$ et $s$ tels que $p - 1 = d \times 2^s$, avec $d$ impair. Ainsi, pour un nombre $a$ comme précédemment, $a^{d\times 2^{s-1}}$ est la racine de $a^{d \times 2^s} = a^{p-1}$ et donc $a^{d\times 2^{s-1}} \equiv 1 \text{ ou } -1 [p]$. Et si c'est $1$ alors on peut poursuivre avec la racine suivante, c'est à dire $a^{d\times 2^{s-2}}$. Et ainsi de suite jusque $a^{d}.
+Pour cela on détermine $d$ et $s$ tels que $p - 1 = d \times 2^s$, avec $d$ impair. Ainsi, pour un nombre $a$ comme précédemment, $a^{d\times 2^{s-1}}$ est la racine de $a^{d \times 2^s} = a^{p-1}$ et donc $a^{d\times 2^{s-1}} \overset{p}{\equiv} 1 \text{ ou } -1$. Et si c'est $1$ alors on peut poursuivre avec la racine suivante, c'est à dire $a^{d\times 2^{s-2}}$. Et ainsi de suite jusque $a^{d}$.
 Donc, soit tous les $a^{d\times 2^{s-i}}$ sont égaux à 1 modulo $p$, soit il y en a qui est égal à $-1$ modulo $p$, c'est à dire à $p-1$.
@@ Ligne 55: / Ligne 55: @@
 <WRAP box>Si $p$ premier, soit $d$ impair et $s$ tels que $p - 1 = d \times 2^s$, alors on a :
-\[a^d \equiv 1 [p] \quad \text{ou} \quad \exists i \text{ tel que } 0 \leqslant i \leqslant s - 1, a^{d\times 2^i} \equiv p - 1 [p]\]
+\[a^d \overset{p}{\equiv} 1 \quad \text{ou} \quad \exists i \text{ tel que } 0 \leqslant i \leqslant s - 1, a^{d\times 2^i} \overset{p}{\equiv} p - 1\]
 Si on trouve $a$ qui ne vérifie pas cette propriété, il prouve que $p$ n'est pas premier. On qualifie un tel nombre de **témoin de Miller**. Il peut aussi arriver que $p$ ne soit pas premier et que l'on choisisse $a$ vérifiant la propriété. Ce $a$ nous fait croire à tort que $p$ est premier. C'est un **menteur**.