Nombre de solutions entière d'une équation elliptique

[jkevinlb]

Bonjour,

j'ai un problème que j'aimerais arriver à résoudre mais je sèche totalement.

Malheureusement je suis informaticien et pas mathématicien et vu la nature du problème une solution "brutte force" est peu envisageable dans le cas présent.

J'ai une équation de la forme:
3 x^2 + 4 y^ 2 = p

La première question est, comment trouver efficacement l'ensemble des x et y qui satisfont cette équation (p sera un grand nombre ~10^20) (x et y devant être des entiers) ?

Mais la vraie question n'est pas celle là.

Le problème est de trouver une valeur de p pour laquelle on a exactement z réponses possibles à cette équation.

J'avoue que je ne sais absolument pas comment le faire mathématiquement (ni le programmer efficacement d'ailleurs).

Merci pour toutes les indications que vous pourriez me donner.
JK

[chan79]

Salut
Juste une remarque:
Si p n'est pas entier, tu ne pourras pas trouver x et y entiers tels 3x²+4y²=p

[jkevinlb]

Salut
Juste une remarque:
Si p n'est pas entier, tu ne pourras pas trouver x et y entiers tels 3x²+4y²=p

Oui bien sûr j'ai corrigé. Merci

[Sylviel]

J'ai adapté le titre au contenu exact de ta question. J'espère que tu auras plus de lecteurs :-)

[Dlzlogic]

Salut
Juste une remarque:
Si p n'est pas entier, tu ne pourras pas trouver x et y entiers tels 3x²+4y²=p

Si j'ai bien compris, on est un contexte informatique. En ce cas, la notion de réel n'existe pas, il n'y a que des flottants. Or, un flottant est un entier que l'on multiplie par une puissance de 10.
Ceci étant dit, la relation proposée est l'équation d'une ellipse, je ne vois pas trop comment il ne pourrait y avoir que 2 couples (x,y) qui satisfont l'équation, par contre, la question "trouver une valeur de p ... " me parait intéressante.
Cette information que p est un grand nombre est souhait ou une certitude ? La difficulté est qu'on ne sait pas vraiment calculer des nombres dont le nombre de chiffres est supérieur à 10, en tout cas avec des moyens habituels.

[leon1789]

La difficulté est qu'on ne sait pas vraiment calculer des nombres dont le nombre de chiffres est supérieur à 10, en tout cas avec des moyens habituels.

:ptdr: les moyens habituels, ça dépend pour qui : tu utilises une calculatrice de poche ? Un logiciel de calcul traite des nombres à 10, 100 ou 1000 chiffres si on veut.

Avec des nombres à 10 chiffres seulement, par simple factorisation de la clé publique, on casserait instantanément le code RSA qui est le plus utilisés des algorithmes de cryptage sur le web ! http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman

Si j'ai bien compris, on est un contexte informatique.

tu as mal compris. Le comptage des solutions entières d'une équation elliptique (ou de degré plus grand) est un grand, beau, vieux, difficile sujet de mathématiques.

[leon1789]

J'ai une équation de la forme:
3 x^2 + 4 y^ 2 = p

le sujet est "nombre de solutions entière d'une équation elliptique".
Or, l'équation que tu présentes n'est pas elliptique, car elle est de degré 2 en les deux variables.
Je dirais que c'est "nombre de solutions entière d'une conique".

[jlb]

y=0,5(p-3x²)^0,5 ( tu cherches des couples(x,y) entiers) et tu testes y pour les valeurs de x de 0 à (p/3)^0,5
après, je ne suis pas doué en info: est-ce facile de tester si un résultat est entier, est-ce possible pour p très grand?

[leon1789]

J'ai une équation de la forme:
3 x^2 + 4 y^ 2 = p

Si est un point rationnel sur la conique (ie. )
alors tous les autres points rationnels (pas forcément entiers) de la conique sont
où , et est un rationnel quelconque.

Comment choisir pour que et soient des entiers (lorsque x0 et y0 sont entiers) ?
Je ne sais pas si c'est une bonne piste...

[Sylviel]

e sujet est "nombre de solutions entière d'une équation elliptique". Or, l'équation que tu présentes n'est pas elliptique, car elle est de degré 2 en les deux variables. Je dirais que c'est "nombre de solutions entière d'une conique".

Hum c'est moi qui ai modifié le titre. Il me semble que les courbes coniques sont un cas particuliers des elliptiques ? Je ne suis pas sûr des définitions... Bref si l'auteur veut changer c'est à sa discrétion : ça me semblait plus clair ainsi.

[leon1789]

Il me semble que les courbes coniques sont un cas particuliers des elliptiques ?

L'équation d'une courbe elliptique est de la forme , donc avec un terme en et un autre en . Du coup, il y a toujours un point à l"infini dans une courbe elliptique (0:1:0), mais pas forcément pour une conique : par exemple, l'équation qui nous intéresse ici n'a pas de point à l'infini (car ellipse réelle).

[lapras]

Je ne pense pas qu'il existe une caractérisation simple des entiers représentés par la forme quadratique 3x^2+4y^2 de discriminant -48 : à équivalence près (changement de variable par SL2(Z)) il y a deux formes (à coefficients premiers entre eux) de discriminant -48 : x^2+12y^2 et 3x^2+4y^2

Si on regarde les congruences modulo 48 prises par ces deux formes prennent le même ensemble de valeurs : on ne peut rien distinguer modulo 48 (autrement dit les deux formes ont le même "genre").
Tout ce que tu peux dire, c'est que si p est un carré modulo 48 (et p premier avec 48), alors p est soit de la forme x^2+12y^2 soit de la forme 3x^2+4y^2 mais je ne peux pas te dire laquelle par une condition "simple" (du type congruence).

Voir le très bon et détaillé livre (qui est orienté "pratique") de Alain Faisant "L'équation diophantienne du second degré".

PS : Comme l'a dit Léon, c'est bien une équation conique et non elliptique (le nom courbe elliptique vient des intégrales elliptiques pour calculer le périmètre d'une ellipse, mais c'est tout pour le lien entre courbes elliptiques et coniques).

[chan79]

Le problème est de trouver une valeur de p pour laquelle on a exactement z réponses possibles à cette équation.

J'avoue que je ne sais absolument pas comment le faire mathématiquement (ni le programmer efficacement d'ailleurs).

Bonjour
Si tu travailles dans un cadre informatique et si par exemple tu cherches une valeur de p pour laquelle il existe exactement deux solutions, ça se fait en programmant une petite routine.
Par exemple: si on veut exactement deux solutions avec des entiers positifs, p=91 convient, avec comme solutions (3,4) et (5,2). Evidemment, si p est très grand, il faut les outils nécessaires.

[leon1789]

Par exemple: si on veut exactement deux solutions avec des entiers positifs, p=91 convient, avec comme solutions (3,4) et (5,2).

Pourquoi chercher des entiers positifs uniquement ? Pour p=3, on a effectivement 2 solutions : . Idem pour p=4.

[leon1789]

Si est un point entier sur la conique (en posant )
alors tous les autres points rationnels (pas forcément entiers) de la conique sont
où , et est un rationnel quelconque.

Comment choisir pour que et soient des entiers (lorsque x0 et y0 sont entiers) ?

Si on pose a = e/f avec pgcd(e,f)=1 alors b et c sont entiers si et seulement si
divise .

Mais j'ai l'impression que ça tourne un peu en rond...

[skwouale]

si on veut faire un programme pour trouver tous les couples pour un p donné, et donc le nombre z :
On prend y comme variable de l'ensemble des entiers.

on peut écrire : x = racine( [p-(2y)²]/3)

* Tous les nompres p pairs n'ont aucune solution : ca si p pair, 2y pair aussi, et p-(2y)² pair donc non divisible par 3 pour donner un entier...

* p-(2y)² doit aussi être multiple de 3
c'est à dire que la somme des chiffres doit être égale à 3 (...M/3 = Ent(M/3))
pour un grd nombre (10^M) de environ 20 chiffres,avec un chti prog ca revient à faire au max M x 2 opérations pour checker si c'est multiple de 3...

* on fait varier y au maximum entre y=0 à y = racine(p)/2
pour un p de l'ordre de 10^20 , ca nous ramène à un ymax de 10^(10-1) = l'ordre du milliard ...

j'y réfléchis...
on doit pouvoir encore le réduire en travaillant sur les proprités de p-(2y)²
avec ces conditions, ca te supprime déjà un bonne partie des p qui n'ont à coup sur pas de solutions...

on peut je pense avec un peu de travail trouver des conditions sur y pour ne pas le faire varier jusqu'à

[Doraki]

J'appelle j = (-1+sqrt(-3))/2.

3x²+4y² = |(2y+x)+2xj|² donc il s'agit de compter les éléments du réseau <2,1+2j> qui sont de norme N.
Z[j] étant un anneau euclidien, on a la décomposition unique en inversibles et facteurs premiers dans Z[j].
Les inversibles sont les racines 6èmes de l'unité, 1,j+1,j,-1,j²,j²+1.

si p est un nombre premier, si p = 1 mod 3 il y a deux idéaux premiers de norme p,
si p=2 mod 3 il y a un idéal premier (à savoir (p)) de norme p²,
et si p=3 il y a un idéal premier (à savoir (1+2j)) de norme 3.
Tout ceci permet de calculer le nombre d'éléments de Z[j] de norme N en regardant la factorisation de N en facteurs premiers (dans Z).

Seulement, tu cherches les éléments de la forme (2y+x)+2xj, c'est-à-dire ceux qui sont congrus à 0,1+2j,2 ou 3+2j modulo (4).

Donc, les éléments de la forme 4*x,
les éléments de la forme 2*x avec x congru à 1 mod 2 (c'est pas trop grave, il suffit de multiplier par l'un des 2 inversibles qu'il faut pour que ça marche).
les éléments de la forme x avec x congru à 1+2j ou 3+2j mod 4 (là il va falloir faire gaffe).

Bon finalement,
On décompose N en facteurs premiers, on appelle v(p) l'exposant de p dans la factorisation de N.
On calcule P = produit pour p=1 mod 3 des 1+v(p)

Si il y a un p=2 mod 3 avec v(p) impair, il y a 0 solutions.
Si N = 0 mod 16, il y a 6*P solutions
Si N = 4 mod 8, il y a 2*P solutions
Si N = 1 mod 4 il y a 0 solutions.
Si N = 3 mod 4 il y a 2*P solutions

[Dlzlogic]

Bonjour chan,

Si tu travailles dans un cadre informatique et si par exemple tu cherches une valeur de p pour laquelle il existe exactement deux solutions, ça se fait en programmant une petite routine.

C'est effectivement un petit programme très amusant à faire.
Je crois qu'il y a beaucoup de solutions, c'est à dire beaucoup de valeurs de p qui ont exactement 2 couples (x,y) correspondant à l'hypothèse. Il est naturellement sous-entendu que x et y sont positifs, sinon, étant donné qu'ils sont au carré, il y a 2 solution {(0;1);(0;-1)} = 4 et {(1;0);(-1;0)}=3 pas vraiment intéressantes.

PS, il est bien évident que je n'avais lu la réponse de Doraki avant d'écrire la mienne. (on l'a écrite en même temps).

[skwouale]

J'appelle j = (-1+sqrt(-3))/2.

3x²+4y² = |(2y+x)+2xj|² donc il s'agit de compter les éléments du réseau qui sont de norme N.
Z[j] étant un anneau euclidien, on a la décomposition unique en inversibles et facteurs premiers dans Z[j].
Les inversibles sont les racines 6èmes de l'unité, 1,j+1,j,-1,j²,j²+1.

si p est un nombre premier, si p = 1 mod 3 il y a deux idéaux premiers de norme p,
si p=2 mod 3 il y a un idéal premier (à savoir (p)) de norme p²,
et si p=3 il y a un idéal premier (à savoir (1+2j)) de norme 3.
Tout ceci permet de calculer le nombre d'éléments de Z[j] de norme N en regardant la factorisation de N en facteurs premiers (dans Z).

Seulement, tu cherches les éléments de la forme (2y+x)+2xj, c'est-à-dire ceux qui sont congrus à 0,1+2j,2 ou 3+2j modulo (4).

Donc, les éléments de la forme 4*x,
les éléments de la forme 2*x avec x congru à 1 mod 2 (c'est pas trop grave, il suffit de multiplier par l'un des 2 inversibles qu'il faut pour que ça marche).
les éléments de la forme x avec x congru à 1+2j ou 3+2j mod 4 (là il va falloir faire gaffe).

Bon finalement,
On décompose N en facteurs premiers, on appelle v(p) l'exposant de p dans la factorisation de N.
On calcule P = produit pour p=1 mod 3 des 1+v(p)

Si il y a un p=2 mod 3 avec v(p) impair, il y a 0 solutions.
Si v(2) >= 4, il y a 6*P solutions
Si v(2) = 2, il y a 2*P solutions
Si v(2) = 0 et si somme pour p=7 mod 12 des v(p) est pair, il y a 0 solutions.
Si v(2) = 0 et si somme pour p=7 mod 12 des v(p) est impair, il y a 2*P solutions

Ds ta réponse, je ne comprends pas au final avec tes v(2)...
: as tu toutes les solutions pour tous les p ?
ou as tu seulement un "si, alors...", qui te permets de ne couvrir seulement et d ene répondre qu'une partie des valeurs possibles de p ?

[chan79]

Le problème est de trouver une valeur de p pour laquelle on a exactement z réponses possibles à cette équation.

JK

J'arrive à ceci:
Si on veut exactement 6 solutions, la plus petite valeur de p qui convient est 16.
Si on veut exactement 12 solutions, la plus petite valeur de p qui convient est 112.
Quelqu'un est d'accord ?