Somme des carrés

[alice02]

Un professeur distrait se laisse enfermer dans le Musée du
CNAM. Un gardien remarque sa présence et lui fait observer
qu’il lui est interdit d’être dans le musée à cette heure. Il lui
propose de le laisser sortir s’il résout l’énigme suivante.
« Voici un nombre : . La machine à congruences des
frères Carissan vous établira rapidement qu’il est égal à
, mais aussi à
. Mais sauriez-vous trouver
deux nombres entiers plus grands que dont il est le produit ? »
Quels sont ces deux nombres ?

[Ben314]

Salut,
Avec un logiciel de calcul moderne, c'est "les doigts dans le nez" de décomposer un tel nombre, mais je suppose qu'il faut le faire à la main.

Dans ce cas, j'utiliserais la formule (correspondant au fait que dans C, on a |zz'|=|z||z'|) :

En conjecturant plus que très fort que les quatre entiers sont en fait 1172 ; 1587 ; 907 et 1752 ;
On obtient alors :
dont on cherche le pgcd via Euclide :
1462-1247=215 ; 6x215-1247=43 ; 215-5x43=0.
Le pgcd est 43 et on vérifie que marchent.
Donc

[nodgim]

Grillé.
Le produit de 2 nombres, chacun somme de 2 carrés, est une somme de 2 carrés.

[chan79]

Salut
Cette formule permet de trouver la solution de cet exo de finale de championnat international 2002

:grillé aussi

[alice02]

Merci Ben314. Je l'ai finalement résolu de cette façon
J'ai étudié
et la première valeur pour laquelle est supérieur à et est
et
donc

[nodgim]

Merci Ben314. Je l'ai finalement résolu de cette façon
J'ai étudié
et la première valeur pour laquelle est supérieur à et est
et
donc

Tu as eu un sacré coup de chance que le 1er carré supérieur à ton nombre convienne. Dans le cas général, ça ne marche pas, sinon ça serait facile de décomposer un produit, et le cryptage RSA n'existerait pas. Donc la réponse attendue était tout de même de se servir des sommes de carré.

[Ben314]

Tu as eu un sacré coup de chance que le 1er carré supérieur à ton nombre convienne. Dans le cas général, ça ne marche pas, sinon ça serait facile de décomposer un produit, et le cryptage RSA n'existerait pas. Donc la réponse attendue était tout de même de se servir des sommes de carré.

O.K. (évidement) concernant la partie bleue : si on donne deux décompositions de N en somme de deux carrés, c'est sans doute qu'il faut s'en servir (ou alors c'est vraiment le GROS piège...)

Sinon, concernant R.S.A. et la décomposition d'un grand nombre, la réponse est tout de même à moduler : si tu cherche à décomposer un très grand entier N et que tu soupçonne qu'il se décompose en deux facteur de taille "à peu prés équivalente", la méthode utilisé par alice02 est foudroyante pour trouver ces facteurs et tout les logiciels tentant de "casser" les grand nombres essayent d'utiliser (parmi d'autres) cette méthode là "au cas où...".
Et ça explique aussi que dans R.S.A., la clef doit être le produit de deux entiers premiers "très grands" mais qui ne doivent surtout pas être "relativement proche l'un de l'autre".

[nodgim]

Bien sûr, et ça je l'avais vu depuis longtemps. Aussi, j'imagine bien dans le protocole des entreprises qui cherchent et trouvent des nombres premiers, qu'ils associent à un nombre "a" pris dans une tranche donnée, un autre nombre" b" pris dans une autre tranche éloignée de la tranche de "a". Ce qu'on peut faire facilement quand on travaille avec des nombres de plusieurs centaines de chiffres.