jeudi 11 juillet 2013

Complément d'information fictionnel et réel concernant "Nombres Premiers SAS"

Bonjour à tous,

Si vous lisez cet article, vous êtes de ceux qui ont lu et apprécié (ou non) Nombres Premiers SAS, une petite fiction que publiée il y a quelques temps ici :

http://www.fibretigre.com/primes/

Pour aller plus loin dans l'aventure, je voulais vous faire part de l'idée initiale de la nouvelle, qui fait au moins autant rêver que le résultat final, mais que j'ai été incapable de mener à bien.

Initialement, la nouvelle s'appelait "Les cartographes de Pi".

une cartographie possible de Pi


Comme vous le savez, Pi  est un nombre qui commence par 3,1415...et qui continue ainsi en alignant, sans fin, les chiffres. Pi se retrouve un peu partout (même dans la répartition des nombres premiers...) donc beaucoup de gens lui attribuent des vertus mystiques, c'est le cas du film Pi.

(mais il dit n'importe quoi sur Pi)

De façon plus pragmatique, les critiques de la récente loi Hadopi avaient déclaré de façon à moitié potache qu'il était impossible désormais de générer Pi avec un ordinateur. Effectivement, un mp3 protégé de Johnny est stocké, de façon informatique, sous forme de 0 et de 1 sur votre machine.



Donc on va avoir 0010011101001...et ainsi de suite. Or, dans l'infinité des chiffres alignés après la virgule du nombre Pi, en binaire, on trouvera une séquence identique au Mp3 protégé. C'est certain. Et comme l'infini, c'est un truc vraiment grand, non seulement on la trouvera une fois, mais on la trouvera plusieurs fois...une infinité de fois.

Après avoir souri sur cette conjecture, mon imagination a galopé : je me suis dit d'abord, mais mince, ce serait une très chouette façon de stocker des données.

Au lieu de stocker un film comme nous le faisons aujourd'hui, c'est à dire en compressant de partout et en se retrouvant avec un fichier de 800 Mo, on pourrait avoir juste télécharger l'information de sa localisation dans les décimales de Pi et le générer à la volée. Vous dites simplement à votre lecteur de film (ou à votre télé) : "va à 3 x 10^156 des décimales de Pi et lis le film" et le film est généré sous vos yeux.

Donc j'avais pensé raconter l'histoire de gens qui cherchent des œuvres culturelles dans les décimales de Pi afin de contourner la loi du copyright  (ce pendant je veux bien l'avis d'un avocat sur le sujet) et surtout de résoudre des problèmes de stockage / download.

Pour donner un exemple concret, voici un résultat bien connu (il y en a d'autres). Si vous convertissez Pi en base 26, et que vous faites A=0, B=1...etc... jusqu'à Z=25, vous trouverez à la décimale 2,5 x 10^18 :

TO BE OR NOT TO BE


Il y a quelque chose de pourri au Royaume du Danemark
et Hamlet va faire le ménage !


Le twist de l'histoire que j'avais prévu étant que non seulement Pi détient des informations des films / chansons / livres déjà produits mais surtout, des films qui n'ont pas encore été produits et peut-être ne le seront jamais...

Cependant l'enjeu de l'histoire étant un peu trop monumental, et au fil de mes renseignements, je me suis replié sur les nombres premiers.

J'ai eu le plaisir d'avoir un feedback de Hugo, normalien agrégé de maths et surtout dans le club très select d'écrivains de fictions interactives ;-). Son thème de recherche est précisément la cryptographie et par conséquent l'utilisation des nombres premiers.

Il m'a informé des éléments suivants :

- Il existe d'ores et déjà des systèmes alternatifs à l'utilisation des nombres premiers dans le cadre de la cryptographie. Le chiffrement par courbes elliptiques (Arthur, un autre lecteur doctorant en maths, m'en avait parlé !) qui est utilisé par la NSA (notez-le, j'en reparle plus bas) et par Gmail (encore des américains, comme par hasard) :-)



- Il existe des systèmes de cryptages encore plus performants : les réseaux euclidiens. Ces systèmes sont si sécurisés qu'ils résisteraient à des algorithmes de déchiffrage sur des ordinateurs quantiques (qui ne sont même pas encore construits à grande taille).

Il m'est difficile d'expliquer simplement ces deux systèmes (sinon que le premier est basé sur des courbes, et que le deuxième traite de concepts mathématiques larges) et a fortiori de faire une fiction sur le sujet. Mais je vais y réfléchir !

- En fait, le système de cryptographie par nombres premiers est déjà très vulnérable, sans même ma "fictive faille" de nombres non triviaux que j'ai imaginé pour l'histoire.

Comme c'est expliqué dans la nouvelle, aujourd'hui on rend public des produits de nombres premiers. Ainsi, votre carte bancaire a dans sa puce un nombre à 232 chiffres et si je m'en souviens bien il commence par un 2252...etc...

Toute la difficulté est de "casser" ce chiffre dans les deux gros nombres premiers dont il est composé. C'est tout l'enjeu des héros de la nouvelle : ils livrent des gros nombres premiers qu'ils découvrent pour qu'ils puissent être intégrés dans des chiffrements.

Cependant il existe une faille toute bête.

Imaginez 3 nombres premiers très gros : A, B et C.

Mastercard utilise pour son chiffrement le nombre M = A x B

Visa utilise le nombre V = B x C

En fait il suffit de trouver le plus grand diviseur commun de M et de V et cela se fait de façon très rapide avec des algorithmes performants. On trouvera donc B, puis ensuite rapidement A et C par division.



Là où la guerre internationale du secret arrive (et notre ami l'angliche, mais en l'occurence c'est plutôt l'amerloque) c'est que la NSA depuis très longtemps avait découvert cette faille et est passée sur des autres types de chiffrement (ellipse). Elle en a profité pour le chuchoter à son ami Google...

Ils se sont bien gardés, tout comme notre héros en fin de nouvelle, de révéler la faille du système...trop heureux de pouvoir plonger dans le secret des autres, jusqu'à ce que cette faille soit redécouverte récemment.

Les fous des maths pourront avoir le détail technique de l'histoire dans ce document un peu hermétique ici : http://eprint.iacr.org/2012/064.pdf

- Enfin, un mot sur les nombres premiers "jumeaux". Dans ma nouvelle, je parle de "filons" de nombres premiers. C'est à dire quand on en trouve un, il y en a à coté. Il y a pas mal de premiers jumeaux dans les petits chiffres, par exemple 11 et 13 sont premiers et très proches, séparés que d'un seul chiffre (le 12), il sont donc jumeaux. Il y a aussi des nombres proches, séparés par quelques chiffres...

Mais y-a-t-il une infinité de jumeaux ? On en sait rien...ou presque. J'avais lu que oui, alors j'étais mal à l'aise pour ma faille, et pour moi le jumeau d'un trivial reste un trivial, par exemple.

A vrai dire, récemment, un mathématicien inconnu a démontré que oui, il y a une infinité de premiers jumeaux (au delà du chiffre 71 000 000 ...).

Le mathématicien en question ne travaillait pas dans un Quick, mais dans un Subway.

Ce subway pour être plus précis.

Il a aussi été concierge de nuit dans un Motel. Un job dont rêverait Grigori Perelman, enfermé dans son taudis à St Petersbourg.


Il s'appelle Zhang. 


6 commentaires:

  1. De rien, mais je suis doctorant en informatique, pas en math.
    Et surtout, il n'y a pas un nombre infini de premiers jumeaux au delà de 71 000 000 (ce qui ne veut strictement rien dire, puisque s'il y en a une infinité, alors il y en a une infinité au delà de n'importe quel position)
    Par contre, il y a une infinité de paire de nombre premier dont la différence est moins de 71 000 000, donc en quelque sorte, de nombre presque jumeaux (en tout cas, pas trop éloignés l'un de l'autre)

    RépondreSupprimer
  2. J'ai oublié de répondre au début de l'article, comme je comptais le faire.
    Théoriquement, il n'est pas intéressant du tout de donner une position dans pi. Admettons, pour l'intérêt de la reflexion, qu'une fois donné la position on soit capable de donner les décimales de pi sans difficulté (ce qui n'est déjà pas évident, mais je ne connais pas assez le domaine)

    Une simple intuition de la théorie de l'information va nous dire que, pour l'immense majorité des films, le nombre de bit nécessaire pour donner la position sera plus grand que le nombre de bits nécessaire pour directement transmettre le film, donc on n'est informatiquement parlant totalement perdant.

    Connaissez vous la bibliothèque de Babel, de Borges ? Car ce que vous décrivez, rechercher des films/livres dans Pi, ça s'apparente beaucoup à la recherche de sens dans sa bibliothèque, qui contient tous les livres possibles, et même ceux qui ont une signification. (Vous pourrez trouver un livre pris au hasard sur mon blog à:
    http://www.milchior.fr/blog/?post/Un-livre-de-Babel%2C-de-Borges )

    RépondreSupprimer
  3. Mon commentaire entre les similitudes entre la nouvelle avec les Bitcoin miners a été supprimé.

    Censure ou filtre anti-spam foireux ?

    RépondreSupprimer
  4. @Daniel : je ne censurerais pas ce type de commentaires !

    Après vérification, merci Arthur, tu as raison, j'avais mal compris le message de Hugo.

    Je comprends que tu dis, Arthur, c'est à dire que pour trouver Last Action Hero dans Pi, sa décimale sera plus éloignée que la 700 millionième décimale de Pi, donc on est perdant en terme d'espace.

    Mais il est possible d'imaginer de factoriser le nombre indiquant cette position de décimale :-)

    RépondreSupprimer
  5. "Factoriser" ?
    "Compresser" non ? (On peut aussi trouver les facteurs premiers, mais c'est pas le sujet ici)

    Sauf surprise, le nombre qui correspond à un film va être "aléatoire". Donc incompressible. (ou alors on le compresse en "le code binaire du film", et on récupère la position dans Pi en la cherchant à partir du film, mais c'est pas intéressant en pratique, même si ça répond théoriquement à la question.)

    RépondreSupprimer
  6. Wahou. J'ai eu du mal vers la fin à suivre les maths ( auxquels je suis assez hermétique ), mais c'est passionnant. L'idée d'utiliser l'infini de Pi est très intéressante ! Et puis cette façon de mettre des enjeux considérables autour de simples nombres que nous avons pris avec le numérique ne peux qu'inspirer de grandes histoires.

    RépondreSupprimer

Merci de lire mon blog