Arithmétique

par **lapras** » 16 Sep 2007, 19:25

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 :we:

par **SimonB** » 16 Sep 2007, 21:45

lapras a écrit: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.

Existe il d'autres méthodes ?

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

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/~helger/crypto/link/primality_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.

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.

par **lapras** » 17 Sep 2007, 17:07

Merci beaucoup, ca m'interesse

Je reposterai sur ce sujet je pense
A+ :++:

par **Flodelarab** » 17 Sep 2007, 17:42

lapras a écrit:Merci beaucoup, ca m'interesse
Je reposterai sur ce sujet je pense
A+ :++:

La question est mal posée de toute façon
(:lol: 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?

par **lapras** » 18 Sep 2007, 07:23

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) :id:

par **Flodelarab** » 18 Sep 2007, 10:45

lapras a écrit: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) :id:

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

Arithmétique

Arithmétique

Qui est en ligne