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 ?
Réponses
-
Tu penses bien que non, sinon ça se saurait...
-
Cela semble maintenant facile, mais je n'ai vu ce raisonnement nulle part ailleurs. Remarque qu'on peut avoir un algo déterministe et les calculs ne sont vraiment pas difficiles. Je pense qu'on ne mettrait pas beaucoup de temps à décoder un nombre composé.
Merci. -
Tu te moques de nous, babsgueye ?
-
babsgueye écrivait:
> 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. -
En disant des choses aussi peu précises, on ne dit rien. Il faut arrêter de se payer de mots.
-
Mais avec cette équation, à coup sur tu as la décomposition de n'importe quel composé. Il reste tout simplement à vouloir écrire l'algo, pour qui ça intéresse !
Il serait même intéressant de donner la liste des 2kk' + k + k' pour récupérer un crible des nombres premiers. -
Ecrire un tel algo est facile, mais un algo qui programmé ne mettra pas dix mille ans pour factoriser un nombre de 20 chifffres, c'est une toute autre paire de manches.
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. -
Bonne nuit,
Pourquoi n'écris tu pas toi même ton algo au lieu de nous le demander ?
Et que signifie ''relativement'' ?
Cordialement,
Rescassol -
C'est ridicule : l'équation est trivialement équivalente à $p=nn'$. La seule reformulation n'apporte strictement rien sans une idée supplémentaire (absente dans ce fil).
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. -
$\dfrac{p-1}{2}=t=2kk' + k + k'=k(2k'+1)+k'$
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. -
Ce n'est pas « très peu efficace », c'est absolument, irrémédiablement inapplicable.
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...) -
Bonne nuit,
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 -
En effet, cette estimation plus renseignée rend les choses « 100 fois pires ».
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). -
Bonne nuit,
Je dirais plutôt "100 fois moins pires", mais ce n'est pas mieux.
Cordialement,
Rescassol -
Euh, oui : ça permet d'attendre 100 fois plus, c'est chouette !
-
Bonne nuit,
Très bien, Jer, cette vidéo, je l'aurais bien montré à mes élèves si je l'avais connue.
Cordialement,
Rescassol -
Merci... pour Mickaël Launay !
-
Mais enfin @Fin de partie, on peut bien améliorer ta programmation en remarquant que Si k = 1, la plus grand valeur possible de k' est connu et est (p-1)/6 et qu'n plus k et k' occupent des positions symétriques dans léquation ( k varie de 1 jusqu'à rencontrer k')
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 -
Merci !
-
Encore une fois, « totalement inefficace» signifie « totalement impraticable, infaisable, impossible ».
(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.) -
Je pense que mainant tu parles en tant que informaticien, mais pas en temps que mathématicien.
Que je sache, j'ai pas encore ici proposé d'algorithme !. -
Je renforçais le mot employé par Fin de partie.
-
Non j'ai remarqué dans ce forum qu'il y a certains gars qui se permettent de juger des résultats mathématiques par leur seul potentiel interet informatique et pensent sur cette base véhiculer du savoir. Que je sache c'est un forum de maths et pas exclusivement d'info. Que je sache ce sont leurs maths qui sont mère de l'info et pas l'inverse. tenir un jugement mathématiques sur un résultat, c'est s’intéresser et critiquer s'il le faut le raisonnement. Quand t'as l'importance,..à chacun ce qu'il cherche.
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.....! -
Tiens, voici un morceau de connaissance dont je ne veux pas rester le détenteur. Cherchons les nombres triangulaires dont la moitié est un nombre triangulaire. Cela revient à chercher les couples $(n,p)$ tels que
\[\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 ? -
Un habillage de ce problème est le vol des canards http://www.les-mathematiques.net/phorum/read.php?2,161504
Il faut les prendre l'aile dans le sac. -
En effet, c'est d'ailleurs sous cette forme que je l'ai appris (il y a encore plus de dix ans).
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). -
Oui, sûr des deux. Il ne s'agit pas d'une norme euclidienne mais d'une norme au sens de la théorie des corps.
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. -
Il existe des méthodes très efficaces pour résoudre les équations de Fermat-Pell.
( https://fr.wikipedia.org/wiki/Équation_de_Pell-Fermat ) -
N'oublions pas l'alpertron : http://www.alpertron.com.ar/CUAD.HTM
-
@jer dans la transformation de ton équation, à la place de = -1, c'est plutôt = +1. Sinon y'a pas besoin de beaucoup chercher pour voir qu'il n'y a pas de solution. il suffit de tracer un segment gradué de mettre n et n+1. Il est clair que la moyenne que tu cherches n(n+1)/2 est entre n et n+1. Où vas-tu alors trouver ton p ? ailleurs . p(p+1)/2 est un entier +1/2. tu le divise par 2, tu tombe sur un entier +1/4 ou un entier +3/4 Donc pas de solution si tu parle d'équation diophantienne.
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$? -
C'est vrai Excuse J'ai en fait raisonné avec la moyenne arithmétique !
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 -
Non : $(2p+1)^2-2(2n+1)^2=-1 \Leftrightarrow 4p^2+4p+1-8n^2-8n-2=-1\Leftrightarrow 4p^2+4p-2(4n^2+4n)=0$.dans la transformation de ton équation, à la place de $=-1$, c'est plutôt $= +1$.
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 !).Il y a une grande différence entre ce que tu proposes et ce dont je parle. -
Je pense qu'il y a une infinité de solutions $(n,p)$ au problème posé plus haut. -
En fait avec mon calcul j'ai trouvé que, pour que n(n+1)/2 = 1/2p(p+1), les valeurs de p possibles sont supérieures à n et donc de la forme p = n + k0. Et par suite de calculs il faut k0 = [racine carré de (8n2 +8n +1 -(2n+1)}/2 et donc pour une valeur de n telle que ce k0 existe,ça marche. J'ai vérifié pour l'exemple que tu m'as donné !
''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? -
Salut pour info !
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 ? -
Babsgueye a écrit:j'ai démontré la conjecture de Legendre
Ce genre d'affirmation ne remplace pas une preuve. B-)- -
Tu tapes "conjecture de Legendre" dans le moteur de recherche de Wikipedia et tu verras.
-
Merci. j'y vais de ce pas !
-
Salut.
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. -
Babsgueye a écrit:j'ai démontré la conjecture de Legendre
Et donc? -
Et donc ?
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 14
+9 Invités