Extrait COSINUS

37 Que se passe-t-il si l’on s’intéresse à l’opération inverse ? Par exemple, si l’on veut trouver si 527 est le produit de deux nombres, s’il est FACTORISABLE  ? Une solution est évidente, 527 x 1, mais cela vous prendra sûrement un certain temps pour vous apercevoir que 527 est également le produit de 17 par 31 ! Ces deux derniers chiffres ne peuvent eux-mêmes d’ailleurs pas s’écrire sous forme de produit de deux nombres autres qu’eux-même et 1. Ils sont dits premiers . Le temps nécessaire pour factoriser un nombre croît très vite avec le nombre n de chiffres du nombre à factoriser, même avec les algorithmes les plus efficaces. Ici, l’évolution du temps de calcul n’est pas polynomiale mais exponentielle. La factorisation est ainsi un problème fondamentalement plus difficile à résoudre que la multiplication. FACTORISER un nombre revient à l’écrire sous la forme d’une multiplication de deux ou plusieurs nombres premiers. La PUISSANCE d’un nombre est le résultat de la multiplication de ce nombre plusieurs fois par lui-même. Ainsi, 27 est factorisable en 3 x 3 x 3, ou autrement dit 3 3 , « 3 à la puissance 3 ». Polynomiale Exponentielle Temps de calcul Complexité Le temps de calcul d’opérations évolue différemment selon leur nature. La durée d’une factorisation, qui est de nature exponentielle, augmente très rapidement avec sa complexité. Les ordinateurs quantiques vont-ils rendre nos machines actuelles aussi obsolètes que celles d’il y a 20 ans ? Rien de moins sûr ! Étranges, leur fonctionnement très compliqué à comprendre, les ordinateurs quantiques suscitent l’émerveillement mais aussi de nombreuses questions. Fonctionnent-ils avec des chats de Schrödinger ? Surtout, pourront-ils faire tourner les derniers jeux vidéos avec les options graphiques poussées au maximum ? Malheureusement pour les joueurs parmi vous, un ordinateur quantique n’est pas un ordinateur personnel. Ici, pas de traitement de texte : les ordinateurs quantiques sont dédiés à un certain nombre de tâche très spécifiques, trop longues à résoudre pour les ordinateurs classiques. Découvrons donc ces problèmes pour lesquels l’ordinateur quantique fera des merveilles. Le temps de calcul Qu’elle soit réalisée par un humain ou un ordinateur, une opération prends un certain temps. Multiplier à la main deux nombres à six chiffres est ainsi plus long que s’il s’agit de deux nombres à deux chiffres. Quel est le rapport R entre ces deux durées ? Si l’on suit la méthode apprise au primaire, le temps de calcul est proportionnel au carré du nombre de chiffres. Dans notre exemple, le rapport vaudrait 6 x 6 36– = – = 9.  2 x 2 4 Multiplier 256845 par 965824 prend donc environ 9 fois plus de temps que 65 par 78 ! De manière générale, si le temps de calcul augmente comme une PUISSANCE de la taille des données (comme dans l’exemple ci-dessus), on dit que l’évolution est polynomiale . © Bramgino/Fotolia