Page 1 sur 1

[CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 14:59
par M@rion
bonjour

ma question est la suivante : sachant que l'on définit un nombre premier comme étant un nombre entier naturel qui n'admet que deux diviseurs, lui-même, et 1, peut-on affirmer qu'un nombre premier (en partant du principe qu'on ne le connait pas) est identifiable du fait qu'il n'est ni divisible par 2 (et ses multiples), ni par 3 (et ses multiples), ni par 5, ainsi que l'ensemble des nombres premiers qui le précède ?

je crois qu'il n'existe pas de méthode pour cela, sans passer par les nombres premiers inférieurs, pouvez-vous confirmer, ou infirmer ? :mrgreen:

merci

Re: [CRPE] exercice nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 15:12
par guiguiche
Un entier $n\geqslant2$ est premier s'il n'est divisible par aucun nombre premier $p\leqslant\sqrt n$.
C'est un peu le principe du crible d'Ératosthène ton affaire !

Re: [CRPE] exercice nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 15:28
par M@rion
merci

oui mais ça ça fonctionne pour des nombres relativement petits, mais pour un nombre à quinze chiffres par exemple, comment fait-on en temps limité ?

Re: [CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 16:03
par guiguiche
Un programme à écrire ou déjà écrit (je ne sais pas si Maxima fait cela).

Re: [CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 16:16
par M@rion
merci, donc pour les grands nombres, à moins d'avoir un pc à disposition, pas de solution ?

pour l'exercice 1 page 2 est-ce que ma définition convient ?

Re: [CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 16:42
par guiguiche
On peut appliquer la méthode du crible à 3737 (avec une calculatrice au besoin)





















... si on n'a pas remarqué que : $3737=3700+37=37\times100+37\times1=37\times101$

Re: [CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 17:15
par M@rion
merci mais pour la 1ère question, pour justifier, je peux m'appuyer sur cette définition ou il faut appliquer la méthode du crible directement ?

Re: [CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 17:34
par rebouxo
Il y a des algorithmes efficaces pour prouver qu'un nombre est premier. Il y en a un qui est en temps polynomial en terme de temps de calcul vu comme un fonction de la taille des nombres. Par contre, on pense qu'il n'y a pas d'algorithme permettant de factoriser un nombre en produit de facteurs premiers en un temps qui ne soit pas exponentiel. Ça tombe bien certains algorithmes de cryptage reposent sur cette impossibilité.

Bref c'est un problème compliqué.

Olivier

Re: [CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 17:46
par guiguiche
Pour les premiers, on applique les critères de divisibilité habituels par 2, 3, 5, 9.

Re: [CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 19:21
par Framboise
Bonjour,

guiguiche a donné la réponse "élémentaire"dans son principe mais lourde à appliquer pour les grands nombres.
Pour des grands nombres, il y a des méthodes permettant d'accélérer au moyen de quelques astuces le crible d'Érastosthène. Cela permet de factoriser en ~1sec des nombres de 15 chiffres. J'ai eu fait de tels programmes en Visual Basic.

Au delà cela nécessite des techniques particulières.
Il faut cependant distinguer la recherche des facteurs premiers ( éventuels ) et déterminer qu'un nombre est premier ou non.
Si l'on connait ses facteurs premiers, on sait immédiatement si le nombre est premier ou non.
Il existe des méthodes prouvant qu'un nombre est ( seulement probablement parfois ) premier ou non sans que l'on connaisse pour autant ses facteurs.

Pour info:
http://www.alpertron.com.ar/ECM.HTM
on peut y factoriser des nombres de plus de 100 chiffres...

Re: [CRPE] Nombres premiers

MessagePosté: Mardi 22 Septembre 2009, 19:38
par M@rion
Merci à vous trois pour vos réponses :D

C'est intéressant ! cela doit passionner les cryptographes

Framboise, peux-tu (vous :?: ) m'expliquer un peu comment on procède pour améliorer la méthode du crible d'Eratosthène s'il te plait ?

Re: [CRPE] Nombres premiers

MessagePosté: Mercredi 23 Septembre 2009, 08:01
par Framboise
Le crible peut être considéré de diverses manières.
- Le crible très naïf: on teste tous les nombres jusqu'au nombre à factoriser
- on voit très vite que l'on peut s'arrêter à la racine carrée du nombre à factoriser compte tenu que l'on balaye tous les nombres depuis 2 jusqu'à la racine carrée.
- on voit ensuite que l'on peut se limiter aux nombres impairs ( donc non multiples de 2 ).
- on peut l'étendre aux nombres non multiples de 3, 5, 7, ...
- à la limite, on teste avec tous les nombres premiers jusqu'à la racine carrée.

Vu que tester avec strictement les nombres premiers est très lourd, la liste étant lourde à générer/manipuler, il est pratique de se limiter aux nombres non multiples des premiers nombres premiers 2, 3, 5, 7,..., plus ces nombres eux-mêmes.
Cela "pollue" ainsi le test de factorisation par un petite proportion de nombres qui ne sont en fait pas premier.
On gagne du temps avec un ordi ainsi tant que l'on prend des petits nombres premiers, mais on arrive très vite à une sorte de saturation où l'on ne gagne plus rien et même régresse au delà. La limite optimale, qui dépend des compilateurs, est autour des facteurs premiers 7 à 23.

Le gain en vitesse par rapport à la méthode naïve, avec arrêt à la racine carrée, est de l'ordre de 5, ce qui reste très modeste.
Cette méthode présente surtout un intérêt pédagogique car d'autres méthodes "pro" de factorisation sont largement plus efficaces

C'est le principe de la Wheel factorization ( -> Google... ).

Re: [CRPE] Nombres premiers

MessagePosté: Jeudi 24 Septembre 2009, 06:42
par M@rion
merci beaucoup :D

pour la racine carrée on en avait déjà parlé à propos d'un exercice il me semble (avec Olivier)

les compilateurs ?

Re: [CRPE] Nombres premiers

MessagePosté: Jeudi 24 Septembre 2009, 08:02
par Framboise
pour la racine carrée on en avait déjà parlé à propos d'un exercice il me semble (avec Olivier)

Oui au début du fil de discussion, je l'ai repris pour mémoire afin de montrer la graduation des méthodes.

les compilateurs ?

J'ai fait des essais avec différents compilateurs et interpréteurs:
Microsoft C7.0
QBASIC
UBASIC
Visual C 6.0
Visual Basic 6.0
avec des performances très variables.
C'est un peu ancien vu que cela fait quelques années que j'ai fait cela.

Re: [CRPE] Nombres premiers

MessagePosté: Jeudi 24 Septembre 2009, 16:21
par M@rion
merci pour toutes ces explications :D