Jan Buiting

Le talon d’Achille quantique de la cryptographie touché

25 mars 2016, 05:52
L’algorithme de Shor pour ceux qui ont piscine dans 5 minutes.
L’algorithme de Shor pour ceux qui ont piscine dans 5 minutes.
Les systèmes cryptographiques à clé publique reposant sur la multiplication de grands nombres premiers, RSA par exemple, sont considérés comme sûrs et même incassables. On sait pourtant que l’invulnérabilité de ces systèmes serait mise à mal si l’algorithme de Shor, un algorithme quantique de factorisation des nombres entiers, était un jour implanté dans un ordinateur quantique. Voilà qui est fait : en modifiant par laser l’état de cinq ions calcium représentant des qbits, des chercheurs de l’université d’Innsbruck (Autriche) et du MIT sont parvenus à factoriser le nombre 15 avec l’algorithme de Shor.
 
Cette factorisation quantique n’est certes pas une véritable première, puisqu’il y a 15 ans déjà des chercheurs du MIT avaient eux aussi réussi à factoriser le nombre 15 en utilisant une molécule et un système à base de résonance magnétique nucléaire. L’expérience n’avait toutefois pas été jugée transposable à plus grande échelle, contrairement à la méthode évolutive proposée par l’équipe austro-américaine.
 
Les ordinateurs classiques sont généralement incapables de factoriser les nombres entiers de façon efficace car ils doivent procéder par étapes successives. Avec les ordinateurs quantiques, ces étapes se font en quelque sorte en parallèle, donc beaucoup plus rapidement. Certaines méthodes cryptographiques se servent de grands nombres premiers multipliés entre eux. Il faut des mois, voire des années, à un ordinateur non-quantique pour re-décomposer le produit de cette multiplication en nombres premiers.
 
Les travaux ayant permis cette avancée ont été publiés dans le magazine Science sous le titre Realization of a scalable Shor algorithm. [HM]
 
Chargement des commentaires
articles apparentés