Somme des carrés

Olympiades mathématiques, énigmes et défis
alice02
Membre Naturel
Messages: 55
Enregistré le: 28 Aoû 2017, 17:28

Somme des carrés

par alice02 » 19 Déc 2017, 17:12

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 ?



Avatar de l’utilisateur
Ben314
Le Ben
Messages: 18332
Enregistré le: 11 Nov 2009, 22:53

Re: Somme des carrés

par Ben314 » 19 Déc 2017, 18:09

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
Modifié en dernier par Ben314 le 19 Déc 2017, 18:29, modifié 2 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

nodgim
Vétéran
Messages: 1644
Enregistré le: 27 Jan 2008, 11:21

Re: Somme des carrés

par nodgim » 19 Déc 2017, 18:12

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

Avatar de l’utilisateur
chan79
Modérateur
Messages: 9803
Enregistré le: 04 Mar 2007, 20:39

Re: Somme des carrés

par chan79 » 19 Déc 2017, 18:22

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

:grillé aussi

alice02
Membre Naturel
Messages: 55
Enregistré le: 28 Aoû 2017, 17:28

Re: Somme des carrés

par alice02 » 23 Déc 2017, 11:49

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
Vétéran
Messages: 1644
Enregistré le: 27 Jan 2008, 11:21

Re: Somme des carrés

par nodgim » 23 Déc 2017, 18:21

alice02 a écrit: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é.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 18332
Enregistré le: 11 Nov 2009, 22:53

Re: Somme des carrés

par Ben314 » 23 Déc 2017, 19:14

nodgim a écrit: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".
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

nodgim
Vétéran
Messages: 1644
Enregistré le: 27 Jan 2008, 11:21

Re: Somme des carrés

par nodgim » 24 Déc 2017, 10:36

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.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite