Contenu

• Pas
• Partie 1 sur 3: Tests de simplicité
• Partie 2 sur 3: Comment fonctionnent les tests de simplicité
• Partie 3 sur 3: Utilisation du théorème des restes chinois
• Conseils
• De quoi avez-vous besoin

Les nombres premiers sont des nombres qui 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 déterminer si un nombre est premier, et elles ont toutes leurs propres avantages et inconvénients. D'une part, certaines méthodes sont très précises, mais elles sont assez complexes si vous avez affaire à de grands nombres. D'un autre côté, il existe des moyens beaucoup plus rapides, mais ils peuvent conduire à des résultats incorrects. Le choix de la méthode appropriée dépend de la taille des nombres avec lesquels vous travaillez.

Pas

Partie 1 sur 3: Tests de simplicité

Noter: dans toutes les formules m désigne le numéro à vérifier.

1. 1 Dénombrement des diviseurs. Il suffit de diviser m à tous les nombres premiers de 2 à la valeur arrondie (${ displaystyle { sqrt {n}}}$).
2. 2 Le petit théorème de Fermat. Attention : parfois le test identifiera à tort des nombres composés comme premiers, même pour toutes les valeurs de a.
   • Choisissons un entier unetel que 2 a ≤ n - 1.
   • Si a (mod n) = a (mod n) alors le nombre est probablement premier. Si l'égalité n'est pas satisfaite, le nombre n est composé.
   • Vérifier l'égalité donnée pour plusieurs valeurs unepour augmenter la probabilité que le nombre testé soit effectivement premier.
3. 3 Essai de Miller-Rabin. Attention : parfois, bien que rarement, pour plusieurs valeurs de a, le test identifiera à tort les nombres composés comme premiers.
   • Trouver les quantités s et d telles que ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Sélectionnez un nombre entier une dans la plage 2 ≤ a ≤ n - 1.
   • Si a = +1 (mod n) ou -1 (mod n), alors n est probablement premier. Dans ce cas, accédez au résultat du test. Si l'égalité ne tient pas, passez à l'étape suivante.
   • Mettez votre réponse au carré (${ displaystyle a ^ {2d}}$). Si vous obtenez -1 (mod n), alors n est probablement un nombre premier. Dans ce cas, accédez au résultat du test. Si l'égalité échoue, répétez (${ displaystyle a ^ {4d}}$ et ainsi de suite) jusqu'à ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Si à une certaine étape après avoir mis au carré un nombre autre que ${ style d'affichage pm 1}$ (mod n), vous avez +1 (mod n), donc n est un nombre composé. Si ${ displaystyle 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-le pour d'autres valeurs unepour augmenter la confiance.

Partie 2 sur 3: Comment fonctionnent les tests de simplicité

1. 1 Dénombrement des diviseurs. Par définition, le nombre m n'est simple que s'il n'est pas divisible par 2 et d'autres entiers sauf 1 et lui-même. La formule ci-dessus permet de supprimer les étapes inutiles et de gagner du temps : par exemple, après avoir vérifié si un nombre est divisible par 3, il n'est pas nécessaire de vérifier s'il est divisible par 9.
   • La fonction floor (x) arrondit x à l'entier le plus proche inférieur ou égal à x.
2. 2 En savoir plus sur l'arithmétique modulaire. L'opération "x mod y" (mod est une abréviation du mot latin "modulo", c'est-à-dire "module") signifie "diviser x par y et trouver le reste". En d'autres termes, en arithmétique modulaire, lorsqu'on atteint une certaine valeur, que l'on appelle module, les nombres "se remettent" à zéro. Par exemple, l'horloge compte à rebours avec le module 12 : elle affiche 10, 11 et 12 heures, puis revient à 1.
   • De nombreuses calculatrices ont une clé de mod. La fin de cette section vous montre comment calculer manuellement cette fonction pour les grands nombres.
3. 3 Découvrez les pièges du petit théorème de Fermat. Tous les nombres pour lesquels les conditions de test ne sont pas remplies sont composites, mais le reste des nombres ne sont que Probablement sont simples. Si vous voulez éviter des résultats incorrects, recherchez m dans la liste des "nombres de Carmichael" (nombres composés qui satisfont à ce test) et des "nombres pseudopremiers de Fermat" (ces nombres ne remplissent les conditions du test que pour certaines valeurs une).
4. 4 Si cela vous convient, utilisez le test de Miller-Rabin. Bien que cette méthode soit assez lourde pour les calculs manuels, elle est souvent utilisée dans les programmes informatiques. Elle fournit une vitesse acceptable et moins d'erreurs que la méthode de Fermat. Un nombre composé ne sera pas considéré comme un nombre premier si les calculs sont effectués pour plus de ¼ valeurs une... Si vous choisissez au hasard des valeurs différentes une et pour tous le test donnera un résultat positif, nous pouvons supposer avec un degré de confiance assez élevé que m est un nombre premier.
5. 5 Pour les grands nombres, utilisez l'arithmétique modulaire. Si vous n'avez pas de calculatrice mod à portée de main, ou si la calculatrice n'est pas conçue pour gérer des nombres aussi grands, utilisez les propriétés de puissance et l'arithmétique modulaire pour faciliter les calculs. Ci-dessous un exemple de ${ style d'affichage 3 ^ {50}}$ 50 :
   • Réécrivez l'expression sous une forme plus pratique : ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Les calculs manuels peuvent nécessiter des simplifications supplémentaires.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ 50 = ${ style d'affichage (3 ^ {25}}$ 50 ${ style d'affichage * 3 ^ {25}}$ mod 50) mod 50. Ici, nous avons pris en compte la propriété de multiplication modulaire.
   • ${ displaystyle 3 ^ {25}}$ 50 = 43.
   • ${ style d'affichage (3 ^ {25}}$ 50 ${ style d'affichage * 3 ^ {25}}$ mod 50) mod 50 = ${ style d'affichage (43 * 43)}$ module 50.
   • ${ style d'affichage = 1849}$ module 50.
   • ${ style d'affichage = 49}$.

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

1. 1 Choisissez deux nombres. L'un des nombres doit être composé et l'autre doit être exactement celui que vous souhaitez tester pour la simplicité.
   • Nombre1 = 35
   • Nombre2 = 97
2. 2 Sélectionnez deux valeurs supérieures à zéro et, respectivement, inférieures aux nombres Number1 et Number2. Ces valeurs ne doivent pas être les mêmes.
   • Valeur1 = 1
   • Valeur2 = 2
3. 3 Calculez le MMI (Mathematical Multiplicative Inverse) pour Number1 et Number2.
   • Calculer le MMI
     • MMI1 = Numéro2 ^ -1 Mod Numéro1
     • MMI2 = Numéro1 ^ -1 Mod Numéro2
   • Pour les nombres premiers uniquement (cela donnera un nombre pour les nombres composés, mais ce ne sera pas son MMI) :
     • MMI1 = (Nombre2 ^ (Numéro1-2))% Nombre1
     • MMI2 = (Nombre1 ^ (Nombre2-2))% Nombre2
   • Par exemple:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Créez une table pour chaque MMI jusqu'aux modules log2 :
   • Pour MMI1
     • F (1) = Nombre2% Nombre1 = 97% 35 = 27
     • F (2) = F (1) * F (1) % Nombre1 = 27 * 27 % 35 = 29
     • F (4) = F (2) * F (2) % Nombre1 = 29 * 29 % 35 = 1
     • F (8) = F (4) * F (4) % Nombre1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8) % Nombre1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16) % Nombre1 = 1 * 1% 35 = 1
   • Calculer les nombres appariés 1 - 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) = Nombre1 % Nombre2 = 35 % 97 = 35
     • F (2) = F (1) * F (1) % Nombre2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2) % Nombre2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4) % Nombre2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8) % Nombre2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16) % Nombre2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Nombre2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Nombre2 = 35 * 35 mod 97 = 61
   • Calculer le nombre apparié 2 - 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. 5 Calculer (Valeur1 * Nombre2 * MMI1 + Valeur2 * Nombre1 * MMI2)% (Nombre1 * Nombre2)
   • Réponse = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Réponse = (2619 + 4270)% 3395
   • Réponse = 99
6. 6 Vérifiez que Number1 n'est pas premier
   • Calculer (Réponse - Valeur1)% Nombre1
   • 99 – 1 % 35 = 28
   • Puisque 28 est supérieur à 0, 35 n'est pas un nombre premier.
7. 7 Vérifiez que Number2 est premier.
   • Calculer (Réponse - Valeur2)% Nombre2
   • 99 – 2 % 97 = 0
   • Puisque 0 est 0, 97 est très probablement un nombre premier.
8. 8 Répétez les étapes 1 à 7 au moins deux fois de plus.
   • Si vous obtenez 0 à l'étape 7 :
     • Utilisez un Number1 différent si Number1 n'est pas premier.
     • Utilisez un autre Number1 si Number1 est premier. Dans ce cas, vous devriez obtenir 0 aux étapes 6 et 7.
     • Utilisez des Signification1 et Signification2 différentes.
   • Si à l'étape 7, vous obtenez systématiquement 0, alors le numéro 2 est très probablement premier.
   • Les étapes 1 à 7 peuvent entraîner une erreur si Number1 n'est pas premier et Number2 est un diviseur de Number1. La méthode décrite fonctionne dans tous les cas lorsque les deux nombres sont premiers.
   • La raison pour laquelle vous devez répéter les étapes 1 à 7 est que dans certains cas, même si Number1 et Number 2 ne sont pas premiers, à l'étape 7, vous obtiendrez 0 (pour un ou les deux nombres). Cela arrive rarement.Choisissez un autre Nombre1 (composite), et si Nombre2 n'est pas premier, alors Nombre2 ne sera pas égal à zéro à l'étape 7 (sauf dans le cas où Nombre1 est un diviseur de Nombre2 - ici, les nombres premiers seront toujours égaux à zéro à l'étape 7).

Conseils

• Nombres premiers de 168 à 1000 : 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 le test de force brute soit un test fastidieux lorsque vous travaillez avec de grands nombres, il est assez efficace pour de petits nombres. Même dans le cas de grands nombres, commencez par tester de petits diviseurs, puis passez à des méthodes plus sophistiquées pour vérifier la simplicité des nombres (si de petits diviseurs ne sont pas trouvés).

De quoi avez-vous besoin

• Papier, stylo ou ordinateur