Fonction isPrime

[Bisam]

Je le répète : à part le test naïf et le test de Fermat (qui est rarement utilisé en pratique à cause des nombres de Carmichaël), il n'y a rien qui soit mathématiquement à la portée d'un élève du lycée.
Le test de Miller-Rabin peut être facilement implémenté... mais il est bien plus difficile de comprendre pourquoi il fonctionne.
Les autres (Solovay-Strassen, Lucas-Lehmer, cyclotomique, courbes elliptiques,...) sont hors de portée du lycéen, même excellent.
Le test AKS est, à la rigueur, compréhensible... mais très difficile à implémenter (sauf si l'on dispose d'un CAS...) mais de toute façon, il n'est pas intéressant en pratique car il est moins rapide que bien d'autres, et nécessite beaucoup de mémoire.

[Lionel Debroux]

APRT-CL(E) n'est pas trivial non plus.

[pierrotdu18]

Et quel est l'algorithme (même si je ne peux pas le comprendre) déterministe le plus rapide?

[Lionel Debroux]

Le test de primalité générique (= applicable à des nombres qui n'ont pas une forme spéciale - par exemple, Lucas-Lehmer ne fonctionne que sur les nombres de Mersenne 2^p-1 avec p premier) déterministe le plus rapide doit être Elliptic Curve Primality Proving, puisque c'est ça qu'on utilise jusqu'aux alentours de 20000 digits (à cette longueur-là, il faut des mois avec un ordinateur normal). Avec une machine récente, ECPP peut prouver la primalité d'un nombre de 3000 digits en une heure environ, probablement un peu plus.
APRT-CL(E) fonctionne raisonnablement sur des nombres jusqu'à quelques centaines de digits.

Voir https://en.wikipedia.org/wiki/Primality_testing .

[Bisam]

... et aucun des deux ne peut être implémenté sans de solides connaissances post-Bac, à moins de trouver un pseudo-code tout tapé et de le copier !

[pierrotdu18]

Et comment ils font avec des nombres de millions de chiffres??

[Lionel Debroux]

... et ECPP utilise un crible qui, si on pousse un peu les paramètres, consomme facilement plus de mémoire qu'une pauvre petite Nspire en a ^^

Avec des nombres de millions de chiffres, soit ils sont des nombres de Mersenne et on utilise Lucas-Lehmer (voir http://mersenne.org ), soit ils sont des nombres susceptibles d'être traités par l'algorithme de Proth et ses variantes... soit on n'a pas le choix, il faut utiliser des tests probabilistes, en général Miller-Rabin

Quant aux algorithmes de factorisation des nombres, je te pointerai vers le programme YAFU, qui implémente, ou utilise dans des programmes externes, la plupart des algorithmes intéressants de factorisation: TF jusqu'à une limite très basse, l'heuristique Rho de Pollard, ECM (délégué à GMP-ECM), P+1, P-1, des variantes de QS, ou NFS (délégué à GGNFS + msieve)

[pierrotdu18]

Ok.....
Donc en fait c'est vraiment un domaine de recherche...


Mais ça marche comment en gros Lucas-Lehmer ?

Je le répète : à part le test naïf et le test de Fermat (qui est rarement utilisé en pratique à cause des nombres de Carmichaël), il n'y a rien qui soit mathématiquement à la portée d'un élève du lycée.
Le test de Miller-Rabin peut être facilement implémenté... mais il est bien plus difficile de comprendre pourquoi il fonctionne.
Les autres (Solovay-Strassen, Lucas-Lehmer, cyclotomique, courbes elliptiques,...) sont hors de portée du lycéen, même excellent.
Le test AKS est, à la rigueur, compréhensible... mais très difficile à implémenter (sauf si l'on dispose d'un CAS...) mais de toute façon, il n'est pas intéressant en pratique car il est moins rapide que bien d'autres, et nécessite beaucoup de mémoire.

C'est quoi les nombres de Carmichaël ?


EDIT Lionel: regroupé 3 posts en 1.

[Lionel Debroux]

En effet, c'est un domaine de recherche en activité permanente
Même si ça fait une vingtaine d'années qu'il n'y a pas eu de nouvel algorithme de factorisation intéressant (NFS reste l'algorithme d'usage général qui permet de traiter les plus gros nombres, les particuliers pouvant monter jusqu'aux alentours de 170 digits, les grilles de calcul vers 215-220 digits, et les chercheurs à la pointe du domaine en sont certainement actuellement un peu au-delà des 232 digits de RSA-768 en 2006-2009), pour le test de primalité, AKS est sorti en 2002.
Et qui sait si quelqu'un trouvera un moyen d'appliquer à la factorisation des nombres entiers un résultat récent qui a beaucoup accéléré le traitement des logarithmes discrets (auquel cas RSA serait en danger ^^)

[pierrotdu18]

Et qui sait si quelqu'un trouvera un moyen d'appliquer à la factorisation des nombres entiers un résultat récent qui a beaucoup accéléré le traitement des logarithmes discrets (auquel cas RSA serait en danger ^^)

Heu.. A tes souhaits... J'ai pas pigé un broc