Arithmétique

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: lapras

Bonsoir, amis arithméticiens, je vous demande quelle est la meilleur méthode pour calculer une liste de nombres premiers.
la méthode qui consiste à diviser N par tous les nombres premiers en dessous de sqrt(N), ou bien la crible d'érathostene ?
Existe il d'autres méthodes ?
Sinon, existe il des nombres un peu comme les nombres de fermat qui laissent penser que tous les nombres de cette forme sont premiers ?

Merci


Posted by: SimonB

Citation:
Posté par lapras
la méthode qui consiste à diviser N par tous les nombres premiers en dessous de sqrt(N), ou bien la crible d'érathostene ?


Au niveau complexité algorithmique (c'est-à-dire temps d'exécution), c'est TRES mauvais. Ca veut dire que ces méthodes ne fonctionnent plus pour des nombres de plusieurs centaines de chiffres.

Citation:
Existe il d'autres méthodes ?


Oui, c'était l'objet de mon TIPE l'an dernier

En particulier (c'est celle qui est utilisée en cryptographie, c'est-à-dire qui a des applications comme le paiement par internet et en général dans tout ce qui est bancaire), tu peux chercher du côté de l'algorithme de Rabin-Miller, expliqué sur http://cermics.enpc.fr/polys/oap/node91.html . Attention, cette fois il s'agit d'un algorithme non déterministe, i.e. on n'est pas sûr que la réponse "N est premier" est juste ! (Mais on est "presque" sûr, la probabilité d'erreur étant vraiment très très faible ;) ).


Sans ça, théoriquement, il y a eu une avancée théorique qui permet de faire un test de primalité qui donne une réponse sûre en un temps "raisonnable" (algorithmiquement parlant, c'est-à-dire polynômial ; cherche deu côté de la complexité temporelle si tu ne comprends pas ce que cela veut dire) : http://www.adastral.ucl.ac.uk/~helg...y_tests/aks.php .
Mais c'est encore tout théorique et il n'y a pas de programme pratique qui permette de réaliser cet algorithme.


Citation:
Sinon, existe il des nombres un peu comme les nombres de fermat qui laissent penser que tous les nombres de cette forme sont premiers ?


Regarde du côté des nombres de Mersenne : http://fr.wikipedia.org/wiki/Nombre_premier_de_Mersenne

Tu peux aussi aller voir sur internet ou dans des livres ce que sont les nombres de Carmichaël...


Enfin, tous ces sujets de primalité sont vraiment intéressants, je trouve.


Posted by: lapras

Merci beaucoup, ca m'interesse :)
Je reposterai sur ce sujet je pense
A+


Posted by: Flodelarab

Citation:
Posté par lapras
Merci beaucoup, ca m'interesse :)
Je reposterai sur ce sujet je pense
A+
La question est mal posée de toute façon
( c'est juste hisoire de faire une entame de message agréable)


Le crible d'Erathostène sert à faire la liste des nombres premiers.
Tester les nombres de 2 à racine de n est un test de primauté.

Les 2 ne sont pas opposables, ni échangeables. Ils ne font pas la même chose.


ok?


Posted by: lapras

Oui, mais en quelque sorte les deux méthodes ont le même but : liste des nombres premiers ou test de primauté, les deux servent à voir si un nombre est premier, (on rregarde dans la liste avec la crible d'érathosthene)


Posted by: Flodelarab

Citation:
Posté par lapras
Oui, mais en quelque sorte les deux méthodes ont le même but : liste des nombres premiers ou test de primauté, les deux servent à voir si un nombre est premier, (on rregarde dans la liste avec la crible d'érathosthene)
C'est exactement le contraire de ce que j'exprime.

Le but du test de primauté n'est pas de faire une liste...
D'autre part, faire une liste (infinie) juste pour savoir si un nombre est premier ...


Non, vraiment, les 2 choses ne peuvent pas etre mises dans le même panier










-