L'équation diophantienne 2kk'+k+k'=(p-1)/2
Salut
La résolution de l'équation diophantienne 2kk'+k+k'= (p-1)/2 permet de décider si p est un nombre premier ou non, et d'en déduire la décomposition.
En effet l'ensemble { 2, 2k+1: k appartenant à N\{0} } contient l'ensemble des nombres premiers et tous nombre impair nom premier est produit de deux éléments de cet ensemble. Un nombre impair qui ne peut pas etre mis comme produit de deux éléments de cet ensemble est forcément premier.
Si p nombre impair est tel que; il existe (k,k') pair de N\{0}2 tel que p=(2k+1)(2k'+1)=4kk'+2k+2k'+1=2(2kk'+k+k')+1 alors p est composé. Et si p impair est tel que ce pair n'existe pas dans N\{0}2 alors p est premier.
Donc il suffira de résoudre l'équation diophantienne 2kk'+k+k'=(p-1)/2 pour décomposer ou décider si p est premier ou non.
Je voudrais savoir; est ce que le temps d'exécution d'un algo pour la résolution est relativement intéressant ?
La résolution de l'équation diophantienne 2kk'+k+k'= (p-1)/2 permet de décider si p est un nombre premier ou non, et d'en déduire la décomposition.
En effet l'ensemble { 2, 2k+1: k appartenant à N\{0} } contient l'ensemble des nombres premiers et tous nombre impair nom premier est produit de deux éléments de cet ensemble. Un nombre impair qui ne peut pas etre mis comme produit de deux éléments de cet ensemble est forcément premier.
Si p nombre impair est tel que; il existe (k,k') pair de N\{0}2 tel que p=(2k+1)(2k'+1)=4kk'+2k+2k'+1=2(2kk'+k+k')+1 alors p est composé. Et si p impair est tel que ce pair n'existe pas dans N\{0}2 alors p est premier.
Donc il suffira de résoudre l'équation diophantienne 2kk'+k+k'=(p-1)/2 pour décomposer ou décider si p est premier ou non.
Je voudrais savoir; est ce que le temps d'exécution d'un algo pour la résolution est relativement intéressant ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Merci.
Alors, à moi :
Tu te moques de nous, babsgueye ?
e.v.
> Je pense qu'on ne mettrait pas beaucoup de temps à décoder un nombre composé.
Moqueries mises à part et au lieu de penser, tu pourrais déjà te faire les dents sur cette page Web un peu ancienne.
Merci @remarque. je te trouve très intéressant par ton post plein d'enseignement.
Il serait même intéressant de donner la liste des 2kk' + k + k' pour récupérer un crible des nombres premiers.
Je ne suis même pas sûr qu'on puisse trouver un tel algo qui soit plus rapide que de tenter la division par des nombres impairs inférieurs à la racine carrée du nombre à factoriser.
Autant dire que cela n'a aucun intérêt.
Pourquoi n'écris tu pas toi même ton algo au lieu de nous le demander ?
Et que signifie ''relativement'' ?
Cordialement,
Rescassol
Paraphrase. Pour chercher les factorisations $p=nn'$, je pose $x=n$ et $y=n'$. Il suffit de résoudre l'équation $p=xy$ pour factoriser $p$ ou décider si $p$ est premier. Il reste tout simplement à vouloir écrire l'algo. Il serait même intéressant de donner la liste des $xy$, pour récupérer un crible de nombres premiers.
Si on connait $k'$ alors, sauf erreur, $k=\dfrac{t-k'}{2k'+1}$
Un algo simple:
On fait varier k' de $1$ à $t$ et pour chaque valeur de $k'$ on teste si $2k'+1$ divise $t-k'$, si c'est le cas on a trouvé un $k$, c'est le résultat de division.
Cela me semble être un algorithme très peu efficace et je doute qu'on puisse en trouver un plus efficace sur les mêmes fondements.
PS:
C'est du même tonneau, comme déjà indiqué que de tenter de diviser le nombre à factoriser par tous les nombres impairs inférieurs à ce nombre (ou inférieurs à sa racine carrée). C'est très peu efficace.
Les nombres qu'on veut factoriser en ce moment (disons pour RSA) ont environ 512 ou 1024 chiffres binaires, ce qui signifie qu'ils sont plus grands que $2^{512}\ge10^{154}$. Pour tester tous les $k'$, on peut compter sur environ $\sqrt{t}$ essais, plus de $10^{75}$. Avec un ordinateur surpuissant qui fait $10^9$ divisions par secondes, il faut $10^{65}$ secondes : c'est un nombre considérable de fois l'âge de l'univers (qui est de l'ordre de $10^{15}$ secondes d'après les estimations actuelles). (Bien sûr, on s'en fiche de l'âge de l'univers : attendre 1 siècle serait déjà trop long, ici le nombre de siècles s'écrit avec plus de 50 chiffres...)
L'âge de l'univers serait plutôt de l'ordre de $7.9\times10^{17}$ secondes , ce qui ne change pas grand chose à ton argument.
Cordialement,
Rescassol
Tiens, puisqu'on parle de grands nombres, il y en a de vraiment gigantesques chez
Micmaths (notamment le plus grand nombre répertorié dans une preuve mathématique).
Je dirais plutôt "100 fois moins pires", mais ce n'est pas mieux.
Cordialement,
Rescassol
Très bien, Jer, cette vidéo, je l'aurais bien montré à mes élèves si je l'avais connue.
Cordialement,
Rescassol
Sinon, n'est-il pas plus facile de tester une égalité après multiplication que de diviser et de tester si le quotient est entier ?
Merci
Tu te rends compte enfin que diviser par les entiers impairs jusqu'à $\sqrt{n}$ où $n$ est l'entier impair à factoriser est meilleur que la méthode que tu proposes?
Sachant que faire ces divisions est une méthode totalement inefficace.
On connait des méthodes beaucoup plus efficaces (mais pas assez cependant) que la méthode très naïve que tu proposes
(Je fais des tas de choses de façon très inefficace mais à la fin, elles sont faites quand même : ce n'est pas le cas ici.)
Que je sache, j'ai pas encore ici proposé d'algorithme !.
Donc un peu de retenu ! Et ne pas se considérer comme détenteur de la connaissance. D'après Socrate c'est l'attitude d'une personne qui a encore beaucoup à apprendre Y'a qui viennent ici comme s'ils aller à une partie d'échec tout simplement.
A bon entendeur.....!
\[\frac{n(n+1)}{2}=\frac12\,\frac{p(p+1)}2.\]
Une fois les dénominateurs chassés, on trouve l'équation : $2n^2+2n=p^2+p$.
Et là, l'astuce apparemment triviale consiste à multiplier par $4$ : l'équation devient $4p^2+4p-2(4n^2+4n)=0$, soit encore :
\[(2p+1)^2-2(2n+1)^2=-1.\]
Cela fait progresser les choses car on cherche désormais les solutions impaires de l'équation $P^2-2N^2=-1$ et on peut faire intervenir l'anneau (euclidien) $\Z[\sqrt{2}]$ et la norme $\Z[\sqrt{2}]\to\Z$, $P+N\sqrt2\mapsto P^2-2N^2$. Bref, l'astuce de multiplier par $4$ a fait apparaître une nouvelle structure que l'on peut exploiter.
Dans la situation de ce fil, on traduit une équation insoluble en pratique ($nn'=p$ avec $p$ impair) en une équation équivalente, à peine plus compliquée mais tout aussi insoluble en pratique ($(2k+1)(2k'+1)=p$). Quel est le gain à ce stade de réécriture, qu'il soit informatique ou mathématique ?
Il faut les prendre l'aile dans le sac.
Variante vue dans un congrès Math.en.jeans cette année : trouver les nombres triangulaires qui sont aussi des carrés (ou l'inverse).
Dans notre cas, où nous cherchons en gros les inversibles de $\Z[\sqrt2]$, un intérêt majeur de cette application, c'est qu'elle est multiplicative : si $(P+N\sqrt2)(P'+N'\sqrt2)=P''+N''\sqrt2$, alors $(P^2-2N^2)({P'}^2-2{N'}^2)={P''}^2-2{N''}^2$. Des applications du genre $P+N\sqrt2\mapsto P^2+2N^2$ ou $P^2+N^2$ ne le sont pas.
( https://fr.wikipedia.org/wiki/Équation_de_Pell-Fermat )
Lis attentivement. Il y a une grande différence entre ce que tu proposes et ce dont je parle. je te propose une méthode de crible, même si c'est pas relativement efficace en terme de calculabilité.
Vraiment?
Que penses-tu de $p=3$ et de $n=2$?
Mais je l'ai vu après et ça m'a fait chercher j'ai un résultat qui me dis que c'est pas possible c'est peut-être pour de plus grande valeurs de n.J'ai pas encore bien vérifié Je vais voir et je l'expose si ça colle
Oui : dans un cas, il y a une valeur ajoutée (une structure connue par ailleurs, celle du groupe des unités de l'anneau des entiers d'un corps quadratique), dans l'autre il n'y a rien de tangible (un crible ? ah ? c'est que tester tous les nombres impairs $n$ ou tous les nombres entiers $k$ et poser $n=2k+1$, ce n'est pas bien différent !).
Je pense qu'il y a une infinité de solutions $(n,p)$ au problème posé plus haut.
''excuse pour la rédaction. je connais pas Latex !''
Par ailleurs @Jer je parle d'une valeur mathématique d'un résultat. Si tu remplis le tableau des valeurs k et k variant de 1 à 15 par exemple (taura besoin que de la partie triangulaire), il y a des nombres entières (K0 ) qui n'apparaissent pas dans ce tableau et que tu ne pourra plus jamais atteindre. Ces K0 te fournissent des nombres premiers. C'est tout simplement ce qui dit ici.
Quant à l'exploitation informatique, c'était une question et je suis satisfait de la réponse......! MERCI.
Mais ce nombre n'est pas toujours un entier.
Il existe un moyen simple et très efficace de calculer toutes les solutions $(n,p)$ de l'équation ci-dessus, sans qu'on ait besoin d'extraire de racines carrées, ni même se demander si un nombre est entier. C'est magique n'est-ce pas?
je pense quand mème tout n solution sera tel que 8n2 + 8n + 1 - (2n + 1) est un carré parfait.
Avec le filtre que je propose avec les 2kk' + k + k', j'ai démontré la conjecture de Legendre. Existe-t-il déja une autre démonstration de La conjecture de Legendre ?
Ce genre d'affirmation ne remplace pas une preuve. B-)-
Pour @ Jer anonyme qui soutenais que mon raisonnement est équivalent à p = nn' et on cherche je sais quoi encore, j'ai joint comme fichier un tableau que j'ai pas pu faire avec Latex. Je pense que cela pourrait mieux t'édifier sur ce raisonnement.
Merci de relire.
Et donc?