La frase mágica para este problema es de "Cero-Prueba de Conocimiento', y un poco de caza alrededor sugiere que en realidad hay un cero-régimen de conocimiento para el producto de dos números primos - no exactamente una prueba, sino una estadística (así que puede ser verificada de forma arbitraria, con alta probabilidad, incluso con una confrontación armario). Desde el extracto para el papel de Un eficiente no interactivo de estadística cero-prueba de conocimiento del sistema de cuasi-caja de seguridad de productos primarios por parte de Gennaro, Micciancio y Rabin:
[...] presentamos el primer sencillo y eficiente cero-prueba de conocimiento de que una presunta RSA módulo es de la forma correcta, es decir, el producto de dos números primos.
Parece que la prueba va en etapas; en primer lugar, un conocimiento cero la prueba de que un número $n$ es squarefree mediante la exhibición de la capacidad para extraer de $n$th raíces de números (números $$ n que no son cuadrados libre de tener $\mathrm{MCD}(n,\phi(n))>1$ y por lo tanto sólo una pequeña fracción de números de $n$th raíces mod $n$), a continuación, un conocimiento cero la prueba de que un número es un producto de dos primos poderes (ambos de los cuales sean desiguales entre sí y sean desiguales a 1 mod 8), donde el verificador suministra un número $x$ y el armario proporciona una raíz cuadrada de uno de $\pm x, \pm 2x$; por la reciprocidad cuadrática, esto siempre es posible que los números de satisfacer la condición, mientras que los productos $m$ de tres o más factores primos tienen en la mayoría de un octavo de los números de menos de $m$ como residuos cuadráticos, por lo que un aleatoriamente elegidos de $x$, no tiene ninguna de $\{\pm x, \pm 2x\}$ ser un cuadrado, al menos, la mitad del tiempo. La combinación de las dos cero-conocimiento de las pruebas da un cero-prueba de conocimiento (un subconjunto de) la propiedad del producto de dos números primos', y entonces la combinación de este con el estándar de pruebas de primalidad da una prueba (un subconjunto de) "producto de dos números primos'.
Tenga en cuenta que este es un estadístico de prueba, aunque no exacta, de uno, usted puede estar convencido de que el resultado de un arbitrario grado de certeza, pero no es una prueba en el sentido clásico. Para más detalles sobre cero-conocimiento de las pruebas en general, la página de la Wikipedia es un buen punto de partida.
