Voir la source de LCS35

'''LCS35''' est un défi [[Cryptographie|cryptographique]] ou casse-tête posé par [[Ronald Rivest]] en 1999. Le défi est de calculer la valeur
:<math>w=2^{2^t} \pmod n</math>,

où ''t''={{formatnum:79685186856218}} est un entier de 14 chiffres décimaux (ou 47 bits), et où ''n'' est un entier de  616 chiffres décimaux (ou 2048 bits) qui est le produit de deux grands [[Nombre premier|nombres premiers]] (qui ne sont pas donnés). 

== Description ==
La valeur de  ''w'' peut servir à décrypter une donnée chiffrée ''z'', elle-même un entier de 616 chiffres décimaux. Le texte en clair  fournit les informations cachées sur la factorisation de ''n'', ce qui permet de vérifier facilement la solution. La motivation initiale étant de tester la possibilité de créer un fichier dont la lecture est garantie impossible avant une date fixée<ref name = "PLS"/>.

L'idée à la base du défi est que la seule façon connue de trouver la valeur de ''w'' sans connaître la factorisation de ''n'' est d'effectuer les ''t'' carrés successifs en commençant par 2 ; autrement dit on pose
: <math>W(0) = 2</math>
: <math>W(i+1) = W(i)^2 (\bmod n)</math> pour  <math>i>0</math>,
et on calcule <math>w= W(t)</math>.

La valeur de ''t'' a été choisie pour faire en sorte que ce calcul de force brute prenne environ 35 ans, en prenant comme point de départ les vitesses des puces électroniques de 1999 et en tenant compte de la [[loi de Moore]]. Rivest note que « tout comme un ralentissement dans la loi de Moore pourrait rendre le [[Jeu vidéo de réflexion|puzzle]] plus difficile à résoudre que prévu, une percée dans l'art de la [[factorisation]] rendrait le puzzle plus facile que prévu ». Dans les faits, c'est la mise au point de [[hardware]] spécifiquement conçu pour ce type de calcul qui va accélérer la conclusion de l'expérience<ref name = "PLS"/>.

== Historique ==

Le défi a été lancé à l'occasion des célébrations du {{35e}} anniversaire du Laboratoire d'informatique du MIT, laboratoire qui fait maintenant partie du [[MIT Computer Science and Artificial Intelligence Laboratory]]  (MIT CSAIL)<ref>Ronald L. Rivest [http://theory.lcs.mit.edu/~rivest/lcs35-puzzle-description.txt « Description of the LCS35 Time Capsule Crypto-Puzzle »], 4 avril 1999.</ref>.

Il a été confirmé, sur le site du MIT CSAIL que Bernard Fabrot a résolu le défi LCS35<ref>{{Lien web |titre=Programmers solve MIT’s 20-year-old cryptographic puzzle {{!}} MIT CSAIL |url=https://www.csail.mit.edu/news/programmers-solve-mits-20-year-old-cryptographic-puzzle |website=www.csail.mit.edu}}</ref> 15 ans plus tôt qu'estimé par Rivest<ref name = "PLS">{{Article|langue = français|périodique = [[Pour la Science]]|auteur = [[Jean-Paul Delahaye]]|titre = Envoyer des messages à retardement|numéro = 518|mois = décembre|année = 2020}}.</ref>.

== Notes et références ==
{{Références}}
{{Traduction/Référence|en|LCS35|note}}

== Liens externes ==
* [https://hitek.fr/42/lcs35-time-capsule-crypto-puzzle-bernard-fabrot_6678 LCS35 Time Capsule Crypto-Puzzle : le casse-tête du MIT datant de 1999 a été résolu]
* [https://www.developpez.com/actu/258210/Un-programmeur-belge-resout-le-casse-tete-cryptographique-du-MIT-vieux-de-20-ans-emis-par-un-professeur-de-l-universite-en-1999/ Un programmeur belge résout le casse-tête cryptographique du MIT vieux de 20 ans]

{{portail|mathématiques|informatique théorique}}

[[Catégorie:Cryptographie]]