Analiza si un número entero dado es primo, dando una respuesta segura en caso de que la respuesta sea negativa, mientras que si la respuesta es afirmativa lo hace con cierta probabilidad de error (tan baja como se desee, según cómo se aplique el test).
La idea detrás de la prueba fue descubierta por M. M. Artjuhov en 1967 (véase el Teorema E en el documento del enlace que figura en la referencia siguiente).[2].
Históricamente tiene importancia, ya que fue el algoritmo probabilístico para verificar la primalidad de un entero.
[3] Además, lo hace con un tiempo de ejecución de orden polinomial, lo que permitió asegurar que el sistema criptográfico RSA puede utilizarse en la práctica.
El test ya no se utiliza en general, ya que ha sido superado por el test de primalidad de Miller-Rabin.
[4] Dado un número impar n se puede contemplar si se da o no la congruencia que vale para varios valores de la "base" a, dado que a es un número coprimo con respecto a n. Si n es primo, entonces esta congruencia es verdadera para todo a.
Entonces, si se elegen valores de a al azar y probamos la congruencia, entonces, tan pronto como se encuentra una a que no se ajusta a la congruencia, entonces se sabe que n no es primo (pero esto no determina una factorización no trivial de n).
Esta base a se llama un testigo de Euler para n, dado que es un testigo de que n es un número compuesto.
y n es impar, según el teorema fundamental de la aritmética se puede descomponer como un producto de primos
Se define en este caso: Según la definición, para conocer
Como se acaba de mencionar, si p es primo impar entonces O sea que (utilizando el contrarrecíproco) si para un n dado se encuentra un a que no verifica esta congruencia, entonces n no es primo.
Esta es la idea del algoritmo de Solovay-Strassen.
Debido a que calcular el símbolo de Jacobi puede hacerse en tiempo polinomial (gracias a las propiedades (I)-(IV)) y a que calcular potencias módulo n también se puede hacer en tiempo polinomial (gracias al algoritmo de exponenciación binaria), este test es rápido de efectuar.
, no se puede afirmar que p sea primo.
Lo que sí ocurre es lo siguiente: si n no es primo, entonces al menos la mitad de los a naturales con 0 Es decir que si el test consiste en probar k enteros a distintos, entonces (el test dé mal | n no es primo)=1/2k. (1) Se elige a un natural al azar entre 2 y n-2. Si repetimos el procedimiento varias veces y siempre respondió "n es un probable primo", entonces con probabilidad muy grande n es primo. Supóngase que se desea determinar si n = 221 es primo. Usando un método eficiente para elevar un número a una potencia (mod n) como la exponenciación binaria, se calcula: Esto da que, o 221 es primo, o 47 es un mentiroso de Euler para 221. Téngase en cuenta que esto no dice nada acerca de los factores primos de 221, que en realidad son 13 y 17. [7] Es posible que el algoritmo devuelva una respuesta incorrecta. Sin embargo, si la entrada n es compuesta, entonces es posible que la salida sea incorrectamente probablemente prima. Cuando n es impar y compuesta, al menos la mitad de todas las a con mcd(a,n) = 1 son testigos de Euler. Por lo tanto, cuando n es compuesto, al menos la mitad de todos los a con mcd(a,n) = 1 es un testigo de Euler. A efectos criptográficos, cuantas más bases a se prueben, es decir, si se elege un valor suficientemente grande de k, mejor será la precisión de la prueba. Por lo tanto, la posibilidad de que el algoritmo falle de esta manera es tan pequeña que el (pseudo) primo se usa en la práctica en aplicaciones criptográficas. En promedio, la probabilidad de error del algoritmo es significativamente menor, y de hecho, es menor que para k rondas de la prueba, aplicadas a n ≤ x uniformemente aleatorias. [9][10] El mismo límite también se aplica al problema relacionado de cuál es la probabilidad condicional de que n sea compuesto para un número aleatorio n ≤ x que ha sido declarado primo en k rondas de la prueba.