Salade de fruits ​

Énoncé ​

Source et ressources : hackropole.fr

Analyse ​

Notre objectif revient à résoudre $x$, $y$ et $z$ pour l'équation :

avec comme critères

En d'autres termes moins formels :

• $x,y,z$ des nombres entiers positifs
• $x$ supérieure à $y,z$

En théorie des nombres, ce problème fait partie de la famille des équations diophantiennes :

Une équation diophantienne, en mathématiques, est une équation polynomiale à une ou plusieurs inconnues dont les solutions sont cherchées parmi les nombres entiers, éventuellement rationnels, les coefficients étant eux-mêmes également entiers.

Source : Wikipédia

Transformation en courbe elliptique ​

Après quelques recherches, on peut découvrir que, par (géométrie birationnelle)[https://fr.wikipedia.org/wiki/Géométrie_birationnelle], il est possible de (transformer notre équation en courbe elliptique)[https://math.stackexchange.com/questions/1195035/large-initial-solutions-to-x3y3-nz3] :

Récupération du zéro ​

De mon côté j'ai utilisé Magma dans un soucis de simplicité, car le code était disponible dans un (thread stackexhange)[https://math.stackexchange.com/questions/1195035/large-initial-solutions-to-x3y3-nz3] :

Q<x> := PolynomialRing(Rationals()); 
E00 := EllipticCurve(x^3-432*94^2); 
Q00 := Generators(E00); 
P := Q00[1];

Q<x> := PolynomialRing(Rationals()); 
E00 := EllipticCurve(x^3-432*94^2); 
Q00 := Generators(E00); 
P := Q00[1];

Par opération inverse, on en déduit $x0,y0,z0$ qu'on peut par ailleurs vérifier

from gmpy2 import *

x0 = mpz(15642626656646177)
y0 = mpz(-15616184186396177)
z0 = mpz(590736058375050)

assert x ** 3 + y ** 3 == 94 * z ** 3

from gmpy2 import *

x0 = mpz(15642626656646177)
y0 = mpz(-15616184186396177)
z0 = mpz(590736058375050)

assert x ** 3 + y ** 3 == 94 * z ** 3

Cependant, ce n'est pas notre solution car $y0\le 0$

Solution ​

Il nous suffit maintenant de récupérer un point de notre courbe permettant de respecter les critères de l'exercice.

En jouant sur magma, on peut récupérer le $k$ point de notre courbe $Q00$, avec $k$ un entier positif.

Par la suite il suffit de transposer le résultat en notre équation diophantienne afin d'en déterminer si les critères sont respectés.

Dans le mille, le pot 16 permet d'obtenir le flag

Q<x> := PolynomialRing(Rationals()); 
E00 := EllipticCurve(x^3-432*94^2); 
Q00 := Generators(E00); 
P := Q00[1];
16*P

Q<x> := PolynomialRing(Rationals()); 
E00 := EllipticCurve(x^3-432*94^2); 
Q00 := Generators(E00); 
P := Q00[1];
16*P

Il suffit ensuite de récupérer le flag

z = .... # log_2(z) = 16000
h = sha256(str(z).encode()).hexdigest()
print(f"FCSC{{{h}}}")

z = .... # log_2(z) = 16000
h = sha256(str(z).encode()).hexdigest()
print(f"FCSC{{{h}}}")

Remarques ​

• Mon choix d'utiliser Magma Online n'était pas intéressante pour ma part m'obligeant à jouer entre mon python local et l'éditeur Magma pour chaque transformation. La solution plus simple serait d'utiliser SageMath pour ce faire
• J'ai dans un premier temps essayé de jouer sur la détermination des possibles valeurs positives de l'équation en utilisant le (théorème de Stagé)[https://math.stackexchange.com/questions/1190385/algorithm-for-positive-integer-solutions-of-equation-a3b3-22c3]. Mais warning, certaines solutions sautent, dont celle attendue ! J'ai fini par trouvé une solution avec un $lo{g}_2(z)=1,000,000,000$.. Effectivement le modérateur a du bien rigoler