Comment faire un test de primalité ?
Réponse publiée sur Quora
Ca dépend ce que vous appelez “faire un test de primalité”.
Si vous avez un seul nombre à tester, vous allez sur Wolfram|Alpha et vous tapez “is (le nombre) prime”
Si vous en avez plusieurs, vous pouvez installer Python et utiliser par exemple ma fonction Goulib.math2.is_prime qui est très efficace (elle utilise le Test de primalité de Miller-Rabin pour les “petits” nombres, et le Baillie–PSW primality test pour les grands)
Si vous en avez besoin dans un autre langage, par exemple en C pour un bidule cryptographique, vous pouvez aller sur Rosetta code par exemple
Et si vous voulez vraiment faire votre propre algorithme de test, alors vous allez devoir sérieusement étudier la théorie des nombres, avec les Courbes elliptiques et tout le toutim, et je vous souhaite bonne chance pour votre Médaille Fields …
Sur le même sujet
- Comment prouver que 2^1572383111-1 est premier (ou pas)? Tout les tests de primalité que j'ai trouvé prennent un temps ridiculement long…
- Puis-je vous adresser un résumé des résultats auxquels ont abouti des recherches pour élaborer des algorithmes générant des nombres premiers ?
- Est-ce qu'un ordinateur portable peut calculer tout les chiffres du plus grand nombre premier connu ?
- Que feriez-vous si vous inventiez un algorithme capable de factoriser n'importe quel nombre semi-premier quasi-instantanément ?
- Comment expliquer les nombres de Lychrel et les palindromes ?