Reprise du message précédent :
Bon j'oriente la question : trouver des voies alternatives permettrait peut-être de dépasser les performances de la technique des nombres de Mersenne.  
 
Le test des 3 indiens s'appelle "AKS" (http://membres.lycos.fr/villemingerard/Premier/testprim.htm?#t2002) mais c'est un test déterministe, et non probabiliste. Utiliser des tests probabilistes (comme Miller-Rabin) est beaucoup plus rapide.

... le seul moyen d'aller plus vite que les tests probabilistes, c'est de trouver des nombres de forme particulière auxquels on peut appliquer un test particulier (et non généraliste). ça marche avec les nombres de Mersenne (et le test particulier de Lucas-Lehmer) mais c'est assez rare. En effet, il est difficile de trouver des nombres dont la forme est telle qu'on peut imaginer un test de primalité simple et rapide.  

Effectivement.
Sur cette inutilité (j'exégère !) du test AKS, je crois qu'il ya avit un article dans Pour la Science (ou la Recherche ?) bien documenté. Il devait indiquer que ce genre de test restait plus long à exécuter que des test Probabilistes, qui eux-même sont plus long que des test genre Lucas-Lehmer, s'appliquant à des entiers d'une forme bien déterminées !

0 est il premier ?
 
est il pair ou impair /D

et 0 + 0 égale la tête à toto !

 
1 non plus n'est pas premier, d'ailleurs, alors qu'en cours de math en 5ème, la prof avait dit qu'il l'était

vous savez, les nombres premiers sont la structure même des mathématiques. le squelette. l'ossature. qui comprend les nombres premiers, comprend l'univers.

bof  
sources ?

Ca me rapelle mon prof de philo qui se touchait avec le nombre d'or ...

 
 
T'en rajoutes un peu la    
En étant un peu plus raisonable, on peut dire qu'ils sont la structure même de l'arithmétique.

Déterrage de topic maths.
 
C pas si con que ca ce qu'il dit Stephen.
Si a,b, c d, ... sont des premiers assez grands alors n=1+ab... ne le sera pas forcément.
Par contre ... Il sera EXTREMEMENT facile de démontrer que n est premier (s'il l'est).
 
En effet, n est premier ssi le groupe multiplicatif de Z/nZ est cyclique d'ordre ab.
i.e. ssi il existe un x de Z/nZ* d'ordre ab.
i.e. i.e. tel que x^ab=1 et x^a<>1 et x^b<>1 et mod n.
Or, sur les ab entiers x possibles de Z/nZ*,  la quasi totalité génèrent Z/nZ*
donc en choisissant un x au pif, et en faisant 3 multiplications, tu as un test pour la primalité de n.
Si n est premier , tu le prend a la place du b d'avant.
Si n est pas premier, tu cherche avec d'autres a, b, c, d ... (en prendant soin de prendre a=2 bien sur ...)
 
ca te permet de proche en proche de déterminer des nombres premiers de plus en plus gros.
 
Par contre, pour des nbres avec des millions de chiffres, j'ai jamais entendu parler d'autres premiers que les mersenne.

 
 
Y aurai moyen d'expliquer rapidement, en gros, pourquoi, pour un profane comme moi ?

C'est vraiment une mauvaise implémentation du crible d'Eratosthène.
Une implémentation autrement plus efficace est celle-ci :  
Pour trouver tous les premiers jusqu'à N:
 - créer un tableau des entiers impairs jusqu'à N,
 - rayer tous les multiples de 3 jusqu'à N,
 - rayer tous les multiples de 5 jusqu'à N,
...
etc jusqu'à racine(N).
Les nombres premiers sont alors les nombres restants (non rayés).
Cet algo est bcp plus rapide que le précédent car les opérations se limitent à une seule racine carrée, des additions, des multiplications des comparaisons et des assignations.
 
Sinon, petit rappel du théorème des nombres premiers :  
Gauss lorsqu'il avait 15 ans, a conjecturé que le nombre Pi(n) de nombres premiers inférieurs à N tend vers n/Ln n.
Plus tard, il a raffiné sa conjecture en postulant que Pi(N) ~ Li(n) = intégrale (2 à n) de dx / Ln x, démontrée plus tard.
 
Plus d'infos  sur http://mathworld.wolfram.com/PrimeNumberTheorem.html
http://numbers.computation.free.fr [...] rimes.html

 
Mais à moins que a ou b ne soit égal à 2, n ne sera jamais premier car paire non?

Oui, tout a fait, tu es obligé de prendre l'un des a, b, c ,d ... égal a 2.
Après renseignements, il s'avère que ces nombres premiers sont assez connus et que le test de primalité qui leur correspond est le test de Lucas-Lehmer cité par initial.
J'aurais donc du préciser que des x primitifs, yen a qu'environ 1 sur 2 dans Z/nN*
(précisemment (b-1)(c-1)... sur un total de 2bc...)
que la mise a la puissance b c'est log(b) opérations ...
Bref, je me suis un peu enflammé.

prenez garde : la recherche de nombres premiers peut agir sur vous comme une drogue...
 
A l'heure actuelle, les 2 voies qui sont potentiellement capables de détrôner la méthode Mersenne, sont : le développement des tests par courbes elliptiques et le développement des ordinateurs quantiques. Autrement dit, c'est pas pour tout de suite.  
 
Je rappelle qu'une récompense de 100 000 $ sera attribuée à celui/celle qui trouvera un nombre premier d'au moins 10 millions de chiffres. Je rappelle aussi que cette somme n'est rien en comparaison des bénéfices que pourrait en tirer le vainqueur s'il est l'auteur d'une nouvelle méthode plus rapide. La totalité des communications importantes (transmissions militaires, gouvernementales, bancaires, etc.) sont de nos jours protégées par des cryptages basés sur les nombres premiers.  
 

up