Fatorar números muito grandes em seus "blocos de construção" primos é extremamente difícil para computadores clássicos, e essa dificuldade é a base da segurança de muitos algoritmos criptográficos. Embora seja fácil fatorar o número 20 como o produto dos primos 2 x 2 x 5, por exemplo, a fatoração de números maiores torna-se exponencialmente mais difícil ao usar algoritmos de fatoração clássicos.

Em um novo artigo publicado em Revisão Física A , os físicos Jose Luis Rosales e Vicente Martin desenvolveram um método que pode tornar muito mais fácil fatorar números muito grandes que são conhecidos por terem exatamente dois fatores primos. O novo método determina a probabilidade de que qualquer número primo seja um dos dois fatores primos de um determinado número. Depois de determinar essas probabilidades, os candidatos mais prováveis ​​ao fator principal podem ser testados primeiro, permitindo que os fatores principais sejam identificados muito mais rapidamente do que antes.

"A teoria mostra não apenas onde os primos estão localizados, mas também a probabilidade de um primo ser um fator de um determinado número, "Rosales disse Phys.org . "Claro, isso tem implicações na criptografia porque [o criptossistema] RSA ignora essa regularidade. "

Uma das coisas interessantes sobre o novo método é que ele não usa nenhum tipo de computador, clássico ou quântico. Em vez disso, envolve um sistema quântico físico - um "simulador quântico" - que, quando codificado com o número a fatorar, exibe uma distribuição de probabilidade de valores de energia que é equivalente à distribuição de probabilidade dos candidatos ao fator principal do número codificado.

"Nosso objetivo é desenvolver uma nova teoria quântica do problema de fatoração usando um simulador quântico, "Rosales disse." Nossa abordagem descobriu uma propriedade sem analogia clássica na teoria dos números. Cada par de primos que resolve o problema se reorganiza para formar um padrão regular:o espectro de banda do simulador quântico. "

A ideia geral por trás do simulador quântico é algo chamado de "conjunto de fatoração, "que os pesquisadores introduziram anteriormente. É baseado na ideia de que os primos são ordenados do menor para o maior (por exemplo, 2 é o primeiro primo, 3 é o segundo primo, e 101 é o 26 ^º melhor). Também é possível obter a raiz quadrada de qualquer número, e então compare o resultado com o primo mais próximo. Por exemplo, a raiz quadrada de 27 é um pouco mais de 5, que é o terceiro primo. Pela definição de um conjunto de fatoração, isso significa que 27 pertence ao conjunto de fatoração de 3.

Os físicos, então, mostraram que podiam transformar a função do conjunto de fatoração em uma função da física quântica (a função do oscilador harmônico invertido). Depois de muitas outras etapas, eles finalmente mostraram que o espectro de energia previsto de um sistema quântico corresponde à distribuição dos primos no conjunto de fatoração de um número. A partir desta informação, os pesquisadores podem determinar a probabilidade de que um primo seja um fator desse número. Para testar a validade de seu método, os físicos testaram certos números e compararam seus resultados com as distribuições reais obtidas usando tabelas de números primos, e encontrou distribuições muito semelhantes.

Os físicos demonstraram teoricamente que o simulador quântico proposto pode fatorar números que são muitas ordens de magnitude maiores do que aqueles que foram fatorados com computadores quânticos. Em seu jornal, eles relatam os resultados do uso de seu método para determinar a distribuição de probabilidade dos fatores primos de um número com 24 dígitos. Avançar, o método faz isso com muito menos recursos do que os exigidos pelos algoritmos de fatoração clássicos.

"Na teoria quântica, a complexidade algorítmica é apenas polinomial com o número de bits do número a fatorar, "Rosales disse." Na verdade, nossos primeiros resultados parecem confirmar que o simulador requer apenas (log√N) ³ estados quânticos para reproduzir seu espectro de energias, um resultado muito encorajador. "

Um último ponto de interesse é que o novo método tem fortes conexões com a hipótese de Riemann, que, se for verdade, sugeriria que os números primos são distribuídos de maneira previsível - da mesma forma que a distribuição dos zeros da função Riemann-zeta. Provar (ou refutar) a hipótese de Riemann é um dos maiores problemas não resolvidos da matemática, e um dos Problemas do Prêmio do Milênio do Clay Mathematics Institute.

"Os primos devem se comportar como números quânticos se a conjectura de Hilbert-Polya se aplicar, "Rosales disse, referindo-se à abordagem de longa data para provar a hipótese de Riemann.

Daqui para frente, os pesquisadores estão atualmente trabalhando na implementação experimental do simulador quântico usando duas partículas emaranhadas em uma armadilha Penning.

"O tratamento totalmente quântico do simulador exigiria análise óptica quântica das interações dos fótons com dois (ou mais) íons emaranhados em uma armadilha de Penning, "Rosales disse." Esta parte do programa ainda está em desenvolvimento. O objetivo é construir um simulador de fatoração quântica experimentalmente. Se implementado com sucesso, números muitas ordens de magnitude maiores do que aqueles disponíveis para seu processamento quântico usando o algoritmo de Shor serão fatorados e, como um subproduto, a conjectura de Hilbert-Polya será testada experimentalmente. "

© 2018 Phys.org