Comment vérifier si un nombre est premier?

Se terminant lorsque le carré du nombre premier est supérieur au nombre que vous vérifiez — Pour vérifier si un nombre est premier, divisez-le par chaque nombre premier commençant par 2 et se terminant lorsque le carré du nombre premier est supérieur au nombre que vous vérifiez.

Les nombres premiers ne sont divisibles que par eux-mêmes et par 1. Tous les autres nombres sont appelés nombres composés. Il existe de nombreuses façons de tester si un nombre est premier, mais il y a un compromis à faire. D'une part, il existe des tests parfaits mais extrêmement lents pour les grands nombres. Par contre, il existe des tests beaucoup plus rapides mais qui peuvent donner des résultats faux. Voici quelques options parmi lesquelles choisir en fonction de la taille du nombre que vous testez.

Partie 1 sur 3: premiers tests

Un nombre premier se terminera par 1, 3, 7 ou 9, mais tous ces nombres ne sont pas premiers.

Remarque: dans toutes les formules, n est le nombre testé pour la primalité.

1

Test de division de première instance. Divisez n par chaque nombre premier de 2 à floor( ${\sqrt {n}}$ ).
2
Le petit théorème de Fermat. Attention: des faux positifs sont possibles, même pour toutes les valeurs de a.
- Choisissez une valeur entière pour a telle que 2 a ≤ n - 1.
- Si a ⁿ (mod n) = a (mod n), alors n est probablement premier. Si ce n'est pas vrai, n n'est pas premier.
- Répétez avec différentes valeurs de a pour augmenter la confiance dans la primalité
3
Test de Miller-rabin. Attention: des faux positifs sont possibles mais rarement pour plusieurs valeurs de a.
- Trouvez des valeurs pour s et d telles que $N-1=2^{s}*d$ .
- Choisissez une valeur entière pour a telle que 2 a ≤ n - 1.
- Si a ^d = +1 (mod n) ou -1 (mod n), alors n est probablement premier. Passer au résultat du test. Sinon, passez à l'étape suivante.
- $Un^{{2d}}$ votre réponse au $carré$ ( $a2d{\displaystyle a^{2d}}$ ). Si cela est égal à -1 (mod n), alors n est probablement premier. Passer au résultat du test. Sinon, répétez ( $Un^{{4d}}$ etc.) jusqu'à $A^{{2^{{s-1}}d}}$ .
- Si jamais vous mettez au carré un nombre qui n'est pas $\pm 1$ (mod n) et que vous vous retrouvez avec +1 (mod n), alors n n'est pas premier. Si $A^{{2^{{s-1}}d}}\neq \pm 1$ (mod n), alors n n'est pas premier.
- Résultat du test: Si n réussit le test, répétez avec différentes valeurs de a pour augmenter la confiance.

Le nombre est premier — S'il n'est pas divisé également par un nombre entier autre que 1 ou lui-même, le nombre est premier.

Partie 2 sur 3: comprendre les tests principaux

1
Comprendre la méthode de la division d'essai. Par la définition de la primalité, n n'est premier que s'il ne peut pas être divisé de manière égale par des entiers 2 ou plus. La formule donnée permet de gagner du temps en supprimant les tests inutiles (par exemple, après le test 3, il n'est pas nécessaire de tester 9).
- Floor(x) arrondit x à l'entier le plus proche ≤ x.
2
Comprendre l'arithmétique modulaire. L'opération "x mod y" (abréviation de "modulo") signifie "diviser x par y et trouver le reste". En d'autres termes, en arithmétique modulaire, les nombres "s'enroulent" jusqu'à zéro lorsqu'ils atteignent une certaine valeur, appelée module. Une horloge compte en modulo 12: elle passe de 10 à 11 à 12, puis revient à 1.
- De nombreuses calculatrices ont un bouton de modification, mais consultez la fin de cette section pour savoir comment résoudre ce problème à la main pour les grands nombres.
3

Connaître les pièges du petit théorème de Fermat. Tous les nombres qui échouent à ce test sont composites (non premiers), mais malheureusement, les nombres qui réussissent ce test ne sont probablement que des nombres premiers. Si vous voulez être sûr d'éviter les faux positifs, recherchez n dans une liste de "nombres de Carmichael" (qui réussissent ce test à chaque fois) et de "pseudoprimes de Fermat" (qui réussissent ce test uniquement pour certaines valeurs de a).
4

Utilisez le test meunier-rabin chaque fois que cela est possible. Bien que fastidieux à réaliser à la main, ce test est couramment utilisé dans les logiciels. Cela peut être effectué à une vitesse pratique et donne moins de faux positifs que la méthode de Fermat. Un nombre composé ne donne jamais un faux positif pour plus de 0,25 des valeurs de a. Si vous choisissez plusieurs valeurs de a au hasard et qu'elles réussissent toutes ce test, vous pouvez être assez sûr que n est premier.
5
Effectuer l'arithmétique modulaire pour les grands nombres. Si vous n'avez pas accès à une calculatrice avec une fonction mod, ou si votre calculatrice ne peut pas afficher des nombres aussi élevés, utilisez les propriétés des exposants et de l'arithmétique modulaire pour faciliter le processus. Voici un exemple pour 350{\displaystyle 3^{50}} $3^{{50}}$ mod 50:
- Réécrivez l'expression avec des exposants plus gérables: $(3^{{25}}*3^{{25}})$ mod 50. (Vous devrez peut-être la décomposer davantage si vous calculez à la main).
- $(3^{{25}}*3^{{25}})$ mod 50 = $(3^{{25}}$ mod 50 $*3^{{25}}$ mod 50) mod 50. (Ceci est une propriété de la multiplication modulaire.)
- $3^{{25}}$ mod 50 = 43.
- $(3^{{25}}$ mod 50 $*3^{{25}}$ mod 50) mod 50 = $(43*43)$ mod 50
- $=1849$ mod 50
- $=49$

Partie 3 sur 3: test du théorème des restes chinois

1
Choisissez deux nombres. L'un des nombres n'est pas premier et le deuxième nombre est le nombre qui doit être testé pour la primalité.
- "Prime1" = 35
- Premier2 = 97
2
Choisissez deux points de données supérieurs à zéro et inférieurs à prime1 et prime2 respectivement. Ils ne peuvent pas s'égaler.
- Données1 = 1
- Données2 = 2
3
Calculer MMI (inverse multiplicatif mathématique) pour prime1 et prime2
- Calculer le MMI
  - MMI1 = Prime2 ^ -1 Mod Prime1
  - MMI2 = Prime1 ^ -1 Mod Prime2
- Pour les nombres premiers uniquement (il donnera un nombre pour les nombres non premiers mais ce ne sera pas son MMI):
  - MMI1 = (Prime2 ^ (Prime1-2))% Prime1
  - MMI2 = (Prime1 ^ (Prime2-2))% Prime2
- par exemple
  - MMI1 = (97 ^ 33)% 35
  - MMI2 = (35 ^ 95)% 97
4
Créer une table binaire pour chaque MMI jusqu'au log2 du module
- Pour MMI1
  - F(1) = Prime2% Prime1 = 97% 35 = 27
  - F(2) = F(1) * F(1)% Prime1 = 27 * 27% 35 = 29
  - F(4) = F(2) * F(2)% Prime1 = 29 * 29% 35 = 1
  - F(8) = F(4) * F(4)% Prime1 = 1 * 1% 35 = 1
  - F(16) =F(8) * F(8)% Prime1 = 1 * 1% 35 = 1
  - F(32) =F(16) * F(16)% Prime1 = 1 * 1% 35 = 1
- Calculer le binaire de Prime1 - 2
  - 35 -2 = 33 (10001) base 2
  - MMI1 = F(33) = F(32) * F(1) mod 35
  - MMI1 = F(33) = 1 * 27 Mod 35
  - MMI1 = 27
- Pour MMI2
  - F(1) = Prime1% Prime2 = 35% 97 = 35
  - F(2) = F(1) * F(1)% Prime2 = 35 * 35 mod 97 = 61
  - F(4) = F(2) * F(2)% Prime2 = 61 * 61 mod 97 = 35
  - F(8) = F(4) * F(4)% Prime2 = 35 * 35 mod 97 = 61
  - F(16) = F(8) * F(8)% Prime2 = 61 * 61 mod 97 = 35
  - F(32) = F(16) * F(16)% Prime2 = 35 * 35 mod 97 = 61
  - F(64) = F(32) * F(32)% Prime2 = 61 * 61 mod 97 = 35
  - F(128) = F(64) * F(64)% Prime2 = 35 * 35 mod 97 = 61
- Calculer le binaire de Prime2 - 2
  - 97 - 2 = 95 = (1011111) base 2
  - MMI2 = (((((F(64) * F(16)% 97) * F(8)% 97) * F(4)% 97) * F(2)% 97) * F(1)% 97)
  - MMI2 = (((((35 * 35)%97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
  - MMI2 = 61
5
Calculer (data1 * prime2 * mmi1 + data2 * prime1 * mmi2)% (prime1 * prime2)
- Réponse = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
- Réponse = (2619 + 4270)% 3395
- Réponse = 99
6
Vérifiez que "prime1" n'est pas premier
- Calculer (Réponse - Données1)% Prime1
- 99 -1% 35 = 28
- Puisque 28 est supérieur à 0, 35 n'est pas premier
7
Vérifiez si prime2 est premier
- Calculer (Réponse - Données2)% Prime2
- 99 - 2% 97 = 0
- Puisque 0 est égal à 0, 97 est potentiellement premier
8
Répétez les étapes 1 à 7 au moins deux fois de plus.
- Si l'étape 7 est 0:
  - Utilisez un "prime1" différent où prime1 est un non-premier
  - Utilisez un nombre premier différent où premier 1 est un nombre premier réel. Dans ce cas, les étapes 6 et 7 doivent être égales à 0.
  - Utilisez des points de données différents pour data1 et data2.
- Si l'étape 7 vaut 0 à chaque fois, il y a une probabilité extrêmement élevée que prime2 soit premier.
- Les étapes 1 à 7 sont connues pour échouer dans certains cas lorsque le premier nombre est un nombre non premier et le deuxième nombre premier est un facteur du nombre non premier «premier1». Cela fonctionne dans tous les scénarios où les deux nombres sont premiers.
- La raison pour laquelle les étapes 1 à 7 sont répétées est qu'il existe quelques scénarios où, même si premier1 n'est pas premier et premier2 n'est pas premier, l'étape 7 est toujours égale à zéro, pour un ou les deux nombres. Ces circonstances sont rares. En changeant prime1 en un nombre non premier différent, si prime2 n'est pas premier, prime2 ne sera rapidement pas égal à zéro à l'étape 7. À l'exception du cas où "prime1" est un facteur de premier2, les nombres premiers seront toujours égaux à zéro à l'étape 7.

Si jamais vous mettez au carré un nombre qui n'est pas (mod n) et que vous obtenez +1 (mod n), alors n n'est pas premier.

Conseils

Les 168 nombres premiers inférieurs à 1000 sont: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991,997
Bien que la division d'essai soit plus lente que les méthodes plus sophistiquées pour les grands nombres, elle reste assez efficace pour les petits nombres. Même pour les tests de primalité de grands nombres, il n'est pas rare de vérifier d'abord les petits facteurs avant de passer à une méthode plus avancée lorsqu'aucun petit facteur n'est trouvé.

Choses dont vous aurez besoin

Outils de travail, tels que du papier et un stylo ou un ordinateur

Lisez aussi: Comment décomposer les nombres?