Philou38 a écrit :
Un peu de maths après le Week-End...Pas de réponse tranchée pour moi (pour la théorie des nombres et les liens entre nombres premiers et la fonction Zeta, envoyez un MP à wil7
, mais un peu de réflexion:
Soit n le nombre produit de 2 facteurs premiers p1 et p2. Soit M=racine_carree_de(n).
n=p1.p2
Supposons p1<=p2
alors p1<=M car sinon p1.p2>M² c'est à dire n>M² ce qui est absurbe.
Ainsi, si on prend n<10000, alors p1<100
Les nombres premiers sont répartis de manière sporadique dans l'ensemble N.Cette sporadicité va en croissant avec le max du cardinal du sous-ensemble de N que l'on examine.
Ainsi, dans [|1;10|], il y a 4 nombres premiers : 2,3,5,7. Si on range 1 (nombre à part) dans les nombres premiers, ca fait unr proportion de 5 sur 10, soit une probabilité de 0.5 de tomber sur un nombre premier.
Dans [|1;20|], il y a : 2,3,5,7,11,13,17,19. Ca fait (en comptant 1) : une probabilité de 0.45
Dans [|1;30|], il y a : 2,3,5,7,11,13,17,19,23,29. Ca fait (en comptant 1) : une probabilité de environ 0.37
Dans [|1;40|], il y a : 2,3,5,7,11,13,17,19,23,29,31,37. Ca fait (en comptant 1) : une probabilité de 0.325
Autrement dit : un nombre n croit beaucoup plus vite que le nombre de nombres premiers inférieurs à ce nombre n. On a surement du en trouver un équivalent (que je pressens à la sauce logarithmique), mais je suis pas assez cultivé pour ça (
www.google.fr pour les fanatiques et les autistes ).
Donc : même si on n'a pas de méthode systématique pour trouver les nombres p1 et p2 à partir du nombre n, une méthode exhaustive de recherche de p1 dans l'intervalle [|1;E(M)|] où M est défini plus haut et E(x) désigne la partie entière de x, donne des résultats satisfaisants, pour des valeurs modestes de n.
Pour n=10000, M=100. On a fait l'intervalle [|1;40|], déjà...ca va vite. De plus, j'ai volontairement mis de côté les bons candidats dans la suite des nombres premiers.
Je m'explique. Si on mets l'ensemble [|1;20|] de côté (il est de cardinal trop faible pour illustrer les critères di-dessous), on constate que les nombres
- impairs
- se finissant par 1,3,7,9
- non multiples évident de 3 et 11 (pour 3, la somme des chiffres doit être divisible par 3, pour 11, la symétrie du nombre peut amener à creuser sur la divisibilité par 11)
sont de bons condidats au caractère premier (ou pas).
De plus, il existe des nombres premiers dont on a trouvé une formule systématique (malheureusement, je n'en ai pas en tête pour illustrer). Il faut donc les rajouter à la liste des critères indicatifs mentionnés pour haut.
On arrive donc à dénombrer avec des règles élémentaires (à la portée d'un écolier en 5ème) des nombres premiers d'une valeur peu élevée.
Par suite, la divisibilité de n par un nombre premier p1 trouvé de la manière exposée ci-dessus est accessoire et rapide. Le facteur p2 en découle simplement, le cas échéant.
Pour les grands nombres (n très grand), cette manière de faire marche encore, mais elle est inadaptée. Du moins pour le cerveau humain. La machine trouve là une application parfaite, mais ses extraordinaires capacités de calcul sont limités devant le caractère aléatoire de la répartition des nombres premiers dans N. C'est tout l'intérêt du codage à base de nombres premiers. C'est aussi sa faiblesse, dans la mesure où, tout code peut être brisé si on en possède les moyens calculatoires. Et la loi de Moore dit bien que les capacités calculatoires et mémorielles des machines croit de manière géométrique avec le temps. Le renouvellement des procédures et autres mesures liées à la sécurité croit de manière beaucoup moins rapide, et en tout cas de manière moins adaptée, ce qui rend les systèmes usuels de transaction sécurisée beaucoup moins sûrs qu'on ne le croit, compte tenu de la démocratisation de la capacité de calcul.
par contre je te rassure concernant la loi de moore. Travaillant dans le semiconducteur je peux t'annoncer qu'elle a de fortes chances de ne plus être valables d'ici à 3 ans, les difficultés techniques à la miniaturisation et à la course à la vitesse commençant à être trop importantes... donc ça ralentit