Arithmétique

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 13:00

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:



SimonB
Membre Irrationnel
Messages: 1180
Enregistré le: 25 Mai 2007, 22:19

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.

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 13:00

par lapras » 17 Sep 2007, 17:07

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

Flodelarab
Membre Légendaire
Messages: 6574
Enregistré le: 29 Juil 2006, 15:04

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?

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 13:00

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:

Flodelarab
Membre Légendaire
Messages: 6574
Enregistré le: 29 Juil 2006, 15:04

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

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite