Test de primalité

[kangourex]

Bonjour je suis un étudiant en informatique, j'aimerai effectuer un test de primalité sur des nombres composé de 200 chiffres environ.
Dans mon post N voudra dire le nombre testé il sera forcément impair.
Un test de primalité permet de dire si un nombre est premier ou pas.
Il y a plusieurs façon de procéder pour vérifier si un nombre est premier ou pas en informatique.
On fait une boucle avec un modulo dedans mais bon comprenez que je ne vais pas faire une boucle de 2 jusqu'à un nombre composé de 200 chiffres on ferai aller un processeur peut-être pour rien au final juste pour tester un nombre.
Bon ensuite il y a une technique qui consiste à faire la racine carré de N et de tester tous les nombres premier inférieur à racine de N sur N bon déjà faut connaitre ses antécédents ça nous donne toujours une boucle immense.

Ensuite j'ai trouvé un test Solovay-Strallen qui dit soit un nombre premier A^((N -1)/2) mod(N)= 1 alors N est premier mais bon faire une puissance d'un nombre composé de 200 chiffres est très très long encore une fois. Donc je voulais vous demander un algorithme ou un théorème qui permet de définir si N est premier ou non et cela sans être dans dans gigantesques calculs longs.

Je vous remercie de l'attention que vous porterai à ce post. Cela me permettra de faire un programme qui crypte les messages.

[adrien69]

Le meilleur que je connaisse c'est le test AKS. Mais faut s'accrocher pour l'encoder, et encore plus pour l comprendre...

[Ben314]

bonsoir,

... mais bon faire une puissance d'un nombre composé de 200 chiffres est très très long encore une fois.

Non, c'est très rapide : pour calculer , tu utilise le fait que :

Si est de l'ordre de , ça te demande (au pire) de faire multiplications pour avoir (donc moins de 2000 si n est au environ de )

[adrien69]

Ah et Solovay-Strallen, c'est du probabiliste. Il ne te dira pas à coup sûr si ton nombre est premier. Tandis qu'AKS si.

[kangourex]

Merci de vos réponses mais j'ai trouvé le théorème d'Euclide ^^