Nombres premiers

[qaterio]

Bonjour,
J'aurai aimé savoir quel est le moyen le plus optimal que l'on ai pour vérifier si un nombre quelconque est premier, disons jusqu'à 10000. On vérifie avec la racine, on utilise le théorème de Wilson (enfin, ça me paraît compliqué parce que 9999! ça fait beaucoup), ou autre chose ?

Merci d'avance.

PS: (je vais travailler à la BU, je regarderai vos réponses ce soir)

[LB2]

Les tests de primalité : il n'y a pas de moyen "simple"

Théorème de wilson = impraticable
Crible d'Eratosthène
Test de Fermat (mais donne aussi des nombres composés appelés nombres de Carmichael)
Test de Rabin-Miller (c'est un test probabiliste)

et plein de raffinements (mais cela utilise de l'arithmétique modulaire généralement)

[Ben314]

Salut,
Juste pour compléter ce que dit aviateur : N=10 000 c'est "très petit".
Si on teste bêtement la divisibilité par les nombres premiers inférieurs à , ça peut même se faire à la main en un temps "raisonnable" (je dirais de l'ordre du quart d'heure pour un mec pas trop nul en calcul mental).
Et évidement, avec un ordi, quelque soit la méthode employée (autre que des truc aussi peu futés que le théorème de Wilson), ça va être totalement instantané.

Avec les critère actuels de sécurité, les clef de cryptages RSA employé par les ordi. pour communiquer entre eux de façon confidentielles sont des nombres de 2 048 bits (= environ 600 chiffres en base 10) qui sont le produit de deux nombres premiers (d'environ 300 chiffres en base 10 chacun)

[pascal16]

dans les algos basiques
en s'arrêtant à racine(n), on va plus vite
en ne testant que les nombres impairs, on va plus vite
en ne testant pas les multiples de 3, on va plus vite

entrer n
vérifier si n%2=0
vérifier si n%3=0
max= partie entière(racine carré de n)
k=5
tant que k<=max
__ vérifier si n%k=0
__ k=k+2
__ vérifier si n%k=0
__ k=k+4
fin tant que

ceci est de l'algorithmique, la partie "vérifier" suppose qu'on arrête le programme, dans un cas réel, il y a des modifications à faire.

On teste 2 nombres sur 6, jusqu'à racine(n), c'est simple et rapide.

Comme la liste des nombres premiers est connue, on peut passer aussi directement par la liste des nombres premiers connus, il n'y a alors qu'une seule vérification et elle est minimale.

[qaterio]

@LB2, Ben314, pascal16,

Merci tout le monde. Mais je suis un peu déçu, je pensais qu'il y aurait une autre méthode que celle que l'on utilise depuis le lycée... Enfin bon.

[Ben314]

@LB2, Ben314, pascal16,
Merci tout le monde. Mais je suis un peu déçu, je pensais qu'il y aurait une autre méthode que celle que l'on utilise depuis le lycée... Enfin bon.

Test de Rabin-Miller (c'est un test probabiliste)

Le test de Rabin-Miller que cite LB2, ça m'étonnerais un peu qu'on le voit au Lycée...
Et il y en a des tas d'autres en plus de ceux cités par LB2 : tape "test de primalité" dans ton moteur de recherche favori et tu va voir la quantité impressionnante de résultats que tu aura, du plus simple au plus compliqué en passant par certains spécifiques à certains type de nombres (comme les nombres premiers de Mersene où il y a des tests spécifiques très rapides ce qui explique que les plus grand nombres premiers connus soient de ce type).

Et s'il y en a un qui te semble "à peu prés accessible" à ton niveau (qu'on ne connaît pas), on pourra sans doute t'expliquer plus en détail.

[qaterio]

@Ben314,
Je viens de regarder le test de Rabin-miller qu'avait proposé LB2 (j'avais pas regarder celui-là à cause du mot "probabiliste"), mais ça me semble compliqué de l'utiliser sans l'algorithme sur le PC.

[Ben314]

Je sais pas où tu as regardé, mais normalement, à peu prés quelque soit la présentation "théorique" du résultat, l'algo. en découle de façon complètement immédiate.
Le théorème est en fait quasiment un algorithme, modulo de connaître l'astuce archi classique qu'on utilise en en info. pour calculer des puissance avec un très grand exposant consistant à ne surtout pas écrire que (donc à monter de 1 en 1 dans les exposants), mais à écrire plutôt et (donc à multiplier les exposants par 2 à chaque itération)