Belgique: Un homme a résolu un casse-tête mathématique du MIT imaginé en 1999

Bernard Fabrot, un programmeur belge, a réussi le 20 avril à résoudre un casse-tête cryptographique imaginé en 1999 par des chercheurs du MIT. Le créateur de cette énigme estimait pourtant qu’il faudrait 35 ans pour résoudre ce défi mathématique, rapporte Wired.

L’autodidacte belge aura été plus rapide que ça. Ayant appris l’existence de cette énigme, baptisée « LCS35 Time Capsule Crypto-Puzzle », en 2015, il n’aura mis que trois ans et demi à la résoudre.

Une capsule temporelle
« Pendant toutes ces années, je n’ai dit à personne que je tentais de résoudre le casse-tête, à part à des amis proches », explique Bernard Fabrot. « Je savais que j’avais mes chances. Mais si j’en parlais à qui que ce soit, ils auraient pu utiliser une unité centrale plus puissante. »

L’énigme consistait à trouver le résultat d’une opération impliquant de mettre un nombre au carré 80.000 milliards de fois, sans s’appuyer sur des calculs parallèles par ordinateur. Une fois la solution trouvée, le programmeur l’a envoyée au laboratoire du MIT – qui avait entre-temps été remplacé par une autre structure. La nouvelle directrice n’avait d’ailleurs jamais entendu parler de ce casse-tête.

La « LCS35 Time Capsule Crypto-Puzzle » servait aussi de serrure virtuelle à une capsule temporelle. Parmi les objets qu’elle renferme figurent une série de jeux vidéo et plusieurs dizaines d’objets choisis notamment par Bill Gates ou Tim Berners-Lee, inventeur du World Wide Web. La capsule sera ouverte ors d’une cérémonie organisée le 15 mai prochain.

source

Est-ce qu'il y a des détails quelque part sur la façon dont il a implémenté sa solution ?

C'est chaud quand même sans utiliser le calcul parallèle, je suppose qu'il a dû prévoir un onduleur et un mécanisme de reprise du calcul en cas de coupure de courant mdr.

J'espère que le résultat n'est pas 42

il y a 4 minutes, Quasi-Modo a dit :

Est-ce qu'il y a des détails quelque part sur la façon dont il a implémenté sa solution ?

C'est chaud quand même sans utiliser le calcul parallèle, je suppose qu'il a dû prévoir un onduleur et un mécanisme de reprise du calcul en cas de coupure de courant mdr.

J'espère que le résultat n'est pas 42

Au final, il n’a mis que 3 ans et demi pour y arriver en y dédiant un cœur de son processeur et en laissant tourner son PC 24h/24 et 7 jours sur 7 en dehors des vacances et des coupures d’électricité.

a résolution de l’énigme partait d’un numéro de départ, qu’il fallait ensuite élever au carré des millions de fois successivement. Le calcul nécessaire était séquentiel, c’est-à-dire que sans le nombre initial, il était impossible de trouver le nombre au carré lui correspondant et sans ce dernier, le nombre suivant ne pouvait également pas être calculé, et ainsi de suite.

Je viens de trouver la formulation du puzzle : https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

Ils sont délirants au MIT quand même lol

il y a 1 minute, Quasi-Modo a dit :

Je viens de trouver la formulation du puzzle : https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

on se revoit dans 3 ans 

Apparemment pour gagner du temps il faudrait calculer (en parallèle) la décomposition en facteur premier de n qui vaut (516 chiffres ptdr).

n = 631446608307288889379935712613129233236329881833084137558899
    077270195712892488554730844605575320651361834662884894808866
    350036848039658817136198766052189726781016228055747539383830
    826175971321892666861177695452639157012069093997368008972127
    446466642331918780683055206795125307008202024124623398241073
    775370512734449416950118097524189066796385875485631980550727
    370990439711973361466670154390536015254337398252457931357531
    765364633198906465140213398526580034199190398219284471021246
    488745938885358207031808428902320971090703239693491996277899
    532332018406452247646396635593736700936921275809208629319872
    7008292431243681

il y a 1 minute, Quasi-Modo a dit :

Apparemment pour gagner du temps il faudrait calculer (en parallèle) la décomposition en facteur premier de n qui vaut (516 chiffres ptdr).

n = 631446608307288889379935712613129233236329881833084137558899
    077270195712892488554730844605575320651361834662884894808866
    350036848039658817136198766052189726781016228055747539383830
    826175971321892666861177695452639157012069093997368008972127
    446466642331918780683055206795125307008202024124623398241073
    775370512734449416950118097524189066796385875485631980550727
    370990439711973361466670154390536015254337398252457931357531
    765364633198906465140213398526580034199190398219284471021246
    488745938885358207031808428902320971090703239693491996277899
    532332018406452247646396635593736700936921275809208629319872
    7008292431243681

Moi tu sais je me suis arrêté à la table de 5 alors ....

Il dit qu'il a trouvé la solution, mais vu que même les chercheurs ne connaissent pas le résultat... 

Il y a 1 heure, Fuck Them All a dit :

Il dit qu'il a trouvé la solution, mais vu que même les chercheurs ne connaissent pas le résultat... 

Il y a dans la réponse du calcul un message ascii codé qui décrit la façon de factoriser n.

Et il y a aussi cette histoire de capsule temporelle dont le code d'accès est le résultat si j'ai bien compris.

Il y a 2 heures, Imaginaerum a dit :

Moi tu sais je me suis arrêté à la table de 5 alors ....

Dire que je comptais sur toi

Avec la décomposition en facteurs premiers ce serait sans doute plus court (mais je ne sais pas de combien!) puisqu'on pourrait calculer l'indicatrice d'Euler et réduire le 2^t a une valeur inférieure.

Des chercheurs ont publié en 2002 qu'ils ont décomposé en facteurs premiers un nombre de 158 chiffres (mais là il y en a 616 apparemment) C'est un problème tellement compliqué que c'est sur ça que se basent les algorithmes de chiffrement pour crypter et sécuriser nos connexions actuelles.

Reste plus qu'à faire des essais vite fait au hasard pour peut-être trouver la réponse rapidement sinon

il y a 1 minute, Quasi-Modo a dit :

Il y a dans la réponse du calcul un message ascii codé qui décrit la façon de factoriser n.

Et il y a aussi cette histoire de capsule temporelle dont le code d'accès est le résultat si j'ai bien compris.

Dire que je comptais sur toi

Avec la décomposition en facteurs premiers ce serait sans doute plus court (mais je ne sais pas de combien!) puisqu'on pourrait calculer l'indicatrice d'Euler et réduire le 2^t a une valeur inférieure.

Des chercheurs ont publié en 2002 qu'ils ont décomposé en facteurs premiers un nombre de 158 chiffres (mais là il y en a 616 apparemment) C'est un problème tellement compliqué que c'est sur ça que se basent les algorithmes de chiffrement pour crypter et sécuriser nos connexions actuelles.

Reste plus qu'à faire des essais vite fait au hasard pour peut-être trouver la réponse rapidement sinon

J adore les langues etrangeres

Finalement je vais jouer au loto j'aurai plus de chances et davantage à gagner