Bonjour,
Je cherche un programme fonctionnel rapide pour tester si un nombre est premier (autre que de diviser ce nombre par tous les nombres premiers précédents inférieurs à la racine de ce nombre). Il me semble que AKS fait ça bien http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_AKS En creusant j'ai trouvé ceci http://fatphil.org/maths/AKS/#Implementations mais les liens sont morts. Crandall Full implementation notes a l'air intéressant. Bref je fais appel à votre aide.
Précision: il faut aussi que ce test soit généraliste.
J'ai trouvé ce code présenté ici: http://math.stackexchange.com/questi...imality-prover
En plus l'auteur explique en détail sa démache sur son blog, donc plutot cool
Par contre c'est codé en Scheme, pas le truc le plus courant au monde, mais bon..,après avoir testé l'algorithme avec le compilateur Scheme MIT-Gnu, ca semble fonctionner avec des valeurs simples , après j'ai pas cherché a comprendre toute la théorie
Super ! Très intéressant le blog. Merci pour cette jolie trouvaille je vais examiner tout ça !
ça me parait gérable de le programmer soi même (a priori en utilisant la lib gmp) à partir de l'article wikipedia anglais https://en.wikipedia.org/wiki/AKS_primality_test
et AKS n'est pas rapide : pour prouver qu'un nombre composé n'est pas premier, un test non déterministe sera en général beaucoup plus rapide, je pense qu'il faut lancer AKS uniquement après que miller-rabin ait renvoyé "probablement premier"
Dernière modification par acx01b ; 18/07/2014 à 17h02.
