Tests de simplicité de Fermat et Miller-Rabin

Salut aux citoyens de Habrovsk! Aujourd'hui, nous continuons à partager du matériel utile, dont une traduction a été préparée spécifiquement pour les étudiants du cours "Algorithmes pour les développeurs" .



Étant donné un certain nombre n , comment comprendre que ce nombre est premier? Supposons que n initialement impair, car sinon la tâche est assez simple.

L'idée la plus évidente serait de rechercher tous les diviseurs de n , cependant, jusqu'à présent, le problème principal est de trouver un algorithme efficace.

---

Test à la ferme

Selon le théorème de Fermat , si n est un nombre premier, alors pour tout a l'égalité suivante vaut: a n−1 =1 (mod n) . De là, nous pouvons dériver la règle de test de Fermat pour vérifier la simplicité d'un nombre: prendre un aléatoire a ∈ {1, ..., n−1} et vérifier si l'égalité a n−1 =1 (mod n) est vraie. Si l'égalité n'est pas respectée, alors n est très probablement composite.

Néanmoins, la condition d'égalité peut être remplie même si n n'est pas simple. Par exemple, prenez n = 561 = 3 × 11 × 17 . Selon le théorème du reste chinois:

Z 561 = Z 3 × Z 11 × Z 17

, où chacun a ∈ Z ^∗ ₅₆₁ correspond à ce qui suit:

(x,y,z) ∈ Z ∗ 3 ×Z ∗ 11 11×Z ∗ 17 .

Selon le théorème de Fermat, x 2 =1 , y 10 =1 z 16 =1 . Puisque 2, 10 et 16 sont tous 560 diviseurs, cela signifie que (x,y,z) 560 = (1, 1, 1) , en d'autres termes a 560 = 1 pour tout a ∈ Z ∗ 561 .

Peu importe quel a nous choisissons, 561 passera toujours le test de Fermat, malgré le fait qu'il soit composite, tant que a est mutuellement simple avec n . De tels nombres s'appellent des nombres de Carmichael et il s'avère qu'il y en a un nombre infini.

Si a pas coprime avec n , alors il ne passe pas le test de Fermat, mais dans ce cas, nous pouvons refuser les tests et continuer à rechercher les diviseurs de n , en calculant le GCD ( a, n ).

Test de Miller-Rabin

On peut améliorer le test en disant que n est premier si et seulement si les solutions x 2 = 1 (mod n) sont x = ±1 .

Ainsi, si n réussit le test de Fermat, c'est-à-dire a n−1 = 1 , alors on vérifie également que a (n−1)/2 = ±1 , car a (n−1)/2 est la racine carrée de 1.

Malheureusement, des nombres comme, par exemple, 1729 - le troisième nombre de Carmichael peut encore tromper ce test amélioré. Et si nous répétons? Autrement dit, jusqu'à ce que cela soit possible, nous réduirons l'exposant de moitié, jusqu'à ce que nous atteignions un nombre différent de 1. Si nous obtenons à la fin quelque chose d'autre que -1, alors n sera composite.

Plus formellement, soit 2 ^S la plus grande puissance de 2, divisible par n-1, c'est-à-dire n−1=2 S q pour un nombre impair q . Chaque numéro de la séquence

a n−1 = a (2^S)q , a (2^S-1)q , ..., aq .

Il s'agit de la racine carrée du membre précédent de la séquence.

Ensuite, si n est un nombre premier, alors la séquence doit commencer par 1 et chaque nombre suivant doit également être 1, ou le premier membre de la séquence peut ne pas être 1, mais alors c'est -1.

Le test de Miller-Rabin prend un a∈ Z n aléatoire. Si la séquence ci-dessus ne commence pas par 1, ou si le premier membre de la séquence n'est pas 1 ou -1, alors n n'est pas simple.

Il s'avère que pour tout composite n , y compris les nombres de Carmichael, la probabilité de réussir le test de Miller-Rabin est d'environ 1/4. (En moyenne, beaucoup moins.) Ainsi, la probabilité que n réussisse plusieurs tests diminue de façon exponentielle.

Si n ne réussit pas le test de Miller-Rabin avec une séquence commençant par 1, alors nous avons une racine carrée non triviale de 1 modulo n , et nous pouvons trouver efficacement les diviseurs de n . Par conséquent, les nombres de Carmichael sont toujours pratiques à prendre en compte.

Lorsque le test est appliqué à des nombres de la forme pq , où p et q sont de grands nombres premiers, ils ne réussissent pas le test de Miller-Rabin dans presque tous les cas, car la séquence ne commence pas par 1. Donc, nous ne serons pas en mesure de casser le RSA.

En pratique, le test de Miller-Rabin est implémenté comme suit:

1. Étant donné n , nous devons trouver s tel que n – 1 = 2 S q pour un q impair.
2. Prendre un aléatoire a ∈ {1,...,n−1}
3. Si a ^q = 1, alors n réussit le test et nous arrêtons l'exécution.
4. Pour i= 0, ... , s−1 vérifiez l'égalité a (2^i)q = −1 . Si l'égalité est vérifiée, n réussit le test (arrêt de l'exécution).
5. Si aucune des conditions ci-dessus n'est remplie, alors n est composite.

Avant d'effectuer le test de Miller-Rabin, il vaut la peine d'effectuer quelques divisions plus triviales en petits nombres premiers.

À strictement parler, ces tests sont des tests pour déterminer si un nombre est considéré comme composite, car ils ne prouvent pas en fait que le nombre contrôlé est premier, mais ils prouvent définitivement qu'il peut se révéler composite.

Il existe encore des algorithmes déterministes travaillant en temps polynomial pour déterminer la simplicité (Agrawal, Kayal et Saxena ), mais aujourd'hui ils sont considérés comme peu pratiques.