Factorización de enteros

Descomponer dos números de igual longitud no tiene por qué tener la misma complicación.

Actualmente (2006) se considera que los casos más duros son aquellos para los que los factores son dos números primos, elegidos al azar, de aproximadamente el mismo tamaño.

El problema de factorizar enteros en tiempo polinómico no ha sido aún resuelto en computación clásica.

Este descubrimiento disparó el interés en la computación cuántica y ya se han construido algunos computadores cuánticos de unos pocos qubits, capaces de descomponer números pequeños.

En contraste, pueden existir ataques más eficientes al problema RSA, pero no se conoce ninguno.

Para una computadora cuántica, en cambio, Peter Shor descubrió en 1994 un algoritmo que lo resuelve en tiempo polinómico.

Esto tendría implicaciones importantes en la criptografía, si alguna vez se construyese una computadora cuántica.

Esto es porque tanto respuestas SI y NO pueden ser comprobadas si se proveen los factores primos junto a sus certificados de primalidad.

Se conoce que está en BQP gracias al algoritmo de Shor.

Además, existen varios algoritmos aleatorios que pueden comprobar la primalidad de un número muy rápidamente, si se está dispuesto a aceptar una pequeña posibilidad de error.