La prise en compte de très grands nombres dans leurs premiers "blocs de construction" est extrêmement difficile pour les ordinateurs classiques, et cette difficulté sous-tend la sécurité de nombreux algorithmes cryptographiques. Bien qu'il soit facile de factoriser le nombre 20 comme le produit des nombres premiers 2 x 2 x 5, par exemple, factoriser de plus grands nombres devient exponentiellement plus difficile lors de l'utilisation d'algorithmes de factorisation classiques.

Dans un nouvel article publié dans Examen physique A , les physiciens Jose Luis Rosales et Vicente Martin ont développé une méthode qui peut rendre beaucoup plus facile la factorisation de très grands nombres connus pour avoir exactement deux facteurs premiers. La nouvelle méthode détermine la probabilité qu'un nombre premier soit l'un des deux facteurs premiers d'un nombre donné. Après avoir déterminé ces cotes, les candidats facteurs premiers les plus probables peuvent être testés en premier, permettant d'identifier les facteurs premiers beaucoup plus rapidement qu'auparavant.

"La théorie montre non seulement où se trouvent les nombres premiers, mais aussi la probabilité qu'un nombre premier soit un facteur d'un nombre donné, " Rosales a dit Phys.org . "Bien sûr, cela a des implications en cryptographie parce que [le cryptosystème] RSA ignore cette régularité."

L'un des aspects intéressants de la nouvelle méthode est qu'elle n'utilise aucun type d'ordinateur, classique ou quantique. Au lieu de cela, il s'agit d'un système quantique physique - un "simulateur quantique" - qui, lorsqu'il est encodé avec le nombre à factoriser, présente une distribution de probabilité des valeurs d'énergie qui est équivalente à la distribution de probabilité des candidats de facteurs premiers du nombre codé.

"Notre objectif est de développer une nouvelle théorie quantique du problème de factorisation à l'aide d'un simulateur quantique, " a déclaré Rosales. "Notre approche a découvert une propriété sans analogie classique dans la théorie des nombres. Chaque paire de nombres premiers qui résolvent le problème se réorganise pour former un motif régulier :le spectre de bande du simulateur quantique. »

L'idée générale derrière le simulateur quantique est ce qu'on appelle "l'ensemble de factorisation, " que les chercheurs ont introduit précédemment. Il est basé sur l'idée que les nombres premiers sont ordonnés du plus petit au plus grand (par exemple, 2 est le premier nombre premier, 3 est le deuxième nombre premier, et 101 est le 26 ^e premier). Il est également possible de prendre la racine carrée de n'importe quel nombre, puis comparer le résultat au nombre premier le plus proche. Par exemple, la racine carrée de 27 est un peu plus de 5, qui est le troisième premier. Par définition d'un ensemble de factorisation, cela signifie que 27 appartient à l'ensemble de factorisation de 3.

Les physiciens ont alors montré qu'ils pouvaient transformer la fonction d'ensemble de factorisation en une fonction issue de la physique quantique (la fonction d'oscillateur harmonique inversé). Après bien d'autres étapes, ils ont finalement montré que le spectre d'énergie prédit d'un système quantique correspond à la distribution des nombres premiers dans l'ensemble de factorisation d'un nombre. A partir de ces informations, les chercheurs peuvent déterminer la probabilité qu'un nombre premier soit un facteur de ce nombre. Pour tester la validité de leur méthode, les physiciens ont testé certains nombres et comparé leurs résultats aux distributions réelles obtenues à l'aide de tables de nombres premiers, et trouvé des distributions très similaires.

Les physiciens ont théoriquement démontré que le simulateur quantique proposé peut factoriser des nombres de plusieurs ordres de grandeur plus grands que ceux qui ont été factorisés avec des ordinateurs quantiques. Dans leur papier, ils rapportent les résultats de l'utilisation de leur méthode pour déterminer la distribution de probabilité des facteurs premiers d'un nombre à 24 chiffres. Plus loin, la méthode le fait avec beaucoup moins de ressources que celles requises par les algorithmes de factorisation classiques.

« En théorie quantique, la complexité algorithmique n'est que polynomiale avec le nombre de bits du nombre à factoriser, " dit Rosales. " En fait, nos premiers résultats semblent confirmer que le simulateur ne nécessite que (log√N) ³ états quantiques pour reproduire son spectre d'énergies, un résultat très encourageant."

Un dernier point intéressant est que la nouvelle méthode a des liens étroits avec l'hypothèse de Riemann, lequel, si vrai, suggérerait que les nombres premiers sont distribués de manière prévisible, de la même manière que la distribution des zéros de la fonction Riemann-zeta. Prouver (ou réfuter) l'hypothèse de Riemann est l'un des plus grands problèmes non résolus en mathématiques, et l'un des problèmes du prix du millénaire du Clay Mathematics Institute.

"Les nombres premiers devraient se comporter comme des nombres quantiques si la conjecture de Hilbert-Polya s'applique, " Rosales a dit, se référant à l'approche de longue date pour prouver l'hypothèse de Riemann.

Aller de l'avant, les chercheurs travaillent actuellement sur la mise en œuvre expérimentale du simulateur quantique en utilisant deux particules intriquées dans un piège de Penning.

"Le traitement entièrement quantique du simulateur nécessiterait une analyse optique quantique des interactions des photons avec deux (ou plus) ions intriqués dans un piège de Penning, " Rosales a dit. "Cette partie du programme est encore en développement. L'objectif est de construire expérimentalement un simulateur de factorisation quantique. S'il est mis en œuvre avec succès, des nombres de plusieurs ordres de grandeur plus grands que ceux disponibles pour son traitement quantique à l'aide de l'algorithme de Shor seront factorisés et, en tant que sous-produit, la conjecture de Hilbert-Polya sera testée expérimentalement."

© 2018 Phys.org