Discussion :

[duchere]

Tout est dit dans le sujet.
En fait on peut y'aller à la bourrin.....
Tester tous les carrés supérieurs à n. Leur retrancher n et vérifier si on trouve un carré auquel cas c'est bon.
Mais bon.... c'est trop long pourt ce que je veux faire.
Merci d'avance.

[progfou]

Non, tu n'as pas dit ce à quoi tu as pensé.
On n'est pas là pour faire les exos des autres.

Edit: C'est trouver 1 i ou trouver tous les i ?
C'est quoi le but ?

[duchere]

J'ai édité mon message dessuite parce que je me suis rendu compte que je l'avais pas dit....
C'est juste que vu que j'y réfléchis depuis 1H ....
Voili voilo.
Merci

[duchere]

Non, c'est juste trouver un i.
DOnc en clair, il faut trouver un carré supérieur à n tel que si on lui retranche n, on a un carré et ce carré c'est i².
Et on on trouve donc i.
Par exemple : 12 + i² = k²
eh bien mon algorithme devra trouver i=2
de maniere à avoir 12 + 2² = 16 = 4²
Voila....
Mais cela devient plus embettant quand c'est 15864284256413 + i² = k²
Voilà.
Merci d'avance.
J'ai entendu parler de l'équation de pell-fermat je sais pas si ca peut m'aider.
Je vais regarder.

[duchere]

En fait il s'agit de résoudre x² - y² = n
C'est pas possible rapiudement ca ?

[Selenite]

Tu cherche i et a vérifiant n + i² = a².
Donc n = a² - i² = (a + i)(a - i) .
Il suffit donc que tu arrive à décomposer n en deux facteurs p et q de même parité vérifiant n = p*q, et p <= q.
Tu as alors a + i = q et a - i = p.
Tu en tire a = (p + q)/2 et i = (q - p)/2.

Je ne suis pas sûr que ce soit plus rapide que la méthode que tu proposes... Des carrés, il n'y en a pas beaucoup. L'entier a que tu cherche est compris entre sqrt(n) et n/2. L'écart n'est pas très grand. Tout dépend de la taille de n.

[duchere]

lol
En fait le but est justement de décomposer un entier n=pq

[duchere]

J'ai peut-être une piste.... qui est plus rapide...Je reviens.

[Selenite]

Evidemment, j'aurais dû m'en douter...

[duchere]

lol....
Bon, en conclusion, il vaut mieux tester tous les nombres entre 0 et sqrt(n) et de voir s'ils divisent n plutot que de faire la technique je m'étais piteusement imaginée.... Car ma technique ne vaut le coup que si p et q sont proches de la racine carré de n.....
Bref....
Merci quand même.

[ToTo13]

Bonjour,

décomposer un entier n=pq

mmmmmmm.....

ça ressemble très étrangement à l'attaque d'un chiffre RSA.
regarde donc tout ce qui traite du RSA, tu trouvera ainsi toute les différentes attaques du cryptage et surtout les méthodes pour trouver n=pq

[duchere]

Toujours pas d'idée d'algo plus rapide ?
Ca m'intéresse

[yann2]

Des carrés, il n'y en a pas beaucoup.

Rien à voir avec le sujet, mais ça m'a fait réagir !
C'est vrai, c'est super marrant ça ! Il ya beaucoup moins de carrés que d'entiers mais pourtant il y en a une infinité .................... ???

[Selenite]

Quand disais qu'il n'y a pas beaucoup de carré, je parlais en terme de densité. En termes cantoriens, il y a autant de carrés que d'entiers : il existe une bijection de l'un dans l'autre.

[10_GOTO_10]

Toujours pas d'idée d'algo plus rapide ?
Ca m'intéresse

Si tu trouves un algorithme rapide de factorisation des nombres (et ton problème est équivalent), je crois que ça interesserait pas mal de gens (militaires, gouvernements, ...). Et en plus ya des sous à se faire.

Pour commencer, tu peut regarder ici

[j.p.mignot]

On donne n et on cherche (i,j) tel que n = i²-j².
si on note a=(i+j)/2 et d=(i-a) (ici a et d sont tels que 2.a et 2.d sont dans N car on peut toujours dire i>=j donc d>=0 )
on recherche donc
(a,d) tel que n = 4.a.d = (2.a) * (2.d) avec 2.a dans N et 2.d dans N
Si on fait maintenant la décomposition en facteurs 1er de n on a tous les diviseurs de n donc toute la série des 2.a et 2.d associés. On limite de plus à a>=d

par exemple si n=12 n = 2²*3 => diviseur possibles 2, 3, 4, 6. avec a>=d il reste 2 choix
1-
2a= 4 2d=3 => a=2 d=1.5 => i=3.5 et j=0.5 i² -j² = 3.5²-.5² = 12.25-.25=12
2-
2a=6 => a=3 et 2d=2 =>d=1 => i=4 et j=2 ( 4²-2²)

si on limite i et j aux entiers, il suffit de choisir les diviseurs paires de n afin que a et d soient des éléments de N.
Une (série de) solution(s) est alors possible que si n est un multiple de 4 soit n est impaire ( a ET d non entiers). Ceca est par ailleurs en relation avec le fait qu'un carré est congru à 0 ou 1 modulo 4

[young077]

Bonjour si j'ai bien compris, tu cherche le premier i tq n + i^2 soit un carré.
Remarque: Le problème n'admet pas toujour de solution il suffit de prendre comme contre exemple n=2.
Dans le cas où la solution existe, voici un algorithme en vb répondant à votre problème :
Public Sub recherchNombre()
Dim j As Integer
Dim n As Integer
n = InputBox("Tapez votre nombre n")
j = 0
Do While Fix(Sqr(n + j ^ 2)) < Sqr(n + j ^ 2)
j = j + 1
Loop
MsgBox ("le nombre i cherché est " & j)

End Sub

voici les résultats obtenus pour les nombres 100 101 102 103 104

valeur de n le nombre i trouvé
100 0
101 50
102 pas de solution
103 51
104 11