Pular para o conteúdo
Even3

O algoritmo de Shor e a vulnerabilidade da criptografia RSA

Trecho de 1 min 53 s de Um novo paradigma para o processamento de informação, gravado no evento XXXVII SEMANA DA FÍSICA UFG: O Impacto Social da Informação e da Tecnologia Quântica.

Assistir à gravação completaNo Even3 Conteúdos · 2 h 41 min

Sobre este trecho

Entenda como o algoritmo de Shor reduz drasticamente o tempo necessário para fatorar números primos grandes e por que isso ameaça a segurança digital.

Vai de a da gravação.

O que é dito neste trecho

Por exemplo, o número 15, os fatores primos dele são cinco e três. Cinco vezes três são números primos que quando multiplicados me dão 15. Parece muito fácil, mas não é, porque se eu der para vocês um número grandão desse aqui e pedir para vocês encontrarem, eh, qual é quais são os fatores primos deles que são esses dois aqui, vocês vão demorar um tempo bastante grande, vocês podem confiar. Por quê? Porque o melhor algoritmo clássico, ou seja, que roda aí nos nossos laptops encontrado até hoje e acredita-se que ele seja de fato o melhor possível, ele é exponencial no número de dígitos que a gente tem no nosso, eh, número, né? Então, por exemplo, se eu tiver 512 bits, eu demoro aí por volta de quatro dias. Agora se eu dobro o número de bits, eu já vou de quatro dias para 100, eh, 1000 anos. Então, vocês veem aqui, né, por esses, eh, números muito grandes que cada vez que eu dobro, né, o número de bits, eu tô aumentando o tempo que eu preciso para faturar esse número de maneira exponencial. Só que o algoritmo descoberto pelo Shor, ele é de fato, eh, muito eficiente, porque ele é polinomial no eh no número de dígitos, né? Então, só para vocês terem uma ideia, ao invés de 34, eh, de quatro dias, eu preciso de 34 segundos, ao invés de 100.000 anos, eu preciso de 4,5, eh, minutos, e ao invés de precisar de, eh, um quintilhão de anos para, eh, faturar um número de 4.000 e, eh, 96 bits, eu preciso apenas de 5 horas. E por que que isso é extremamente relevante? Porque, eh, um dos protocolos de segurança mais usados da internet, que é o chamado RSA, a segurança dele se baseia na, eh, no fato de que faturar números primos é um problema difícil. Mas difícil para quem? Difícil para um computador clássico.

Outros trechos deste conteúdo