En teoría de números , un entero impar n se denomina primo probable de Euler-Jacobi (o, más comúnmente, primo probable de Euler ) en base a , si a y n son coprimos , y
¿Dónde está el símbolo de Jacobi ?
Si n es un entero compuesto impar que satisface la congruencia anterior, entonces n se denomina pseudoprimo de Euler–Jacobi (o, más comúnmente, pseudoprimo de Euler ) para basar a .
La motivación de esta definición es el hecho de que todos los números primos n satisfacen la ecuación anterior, como se explica en el artículo sobre el criterio de Euler . La ecuación se puede probar con bastante rapidez, lo que se puede utilizar para pruebas de primalidad probabilísticas . Estas pruebas son más del doble de sólidas que las pruebas basadas en el pequeño teorema de Fermat .
Todo pseudoprimo de Euler-Jacobi es también un pseudoprimo de Fermat y un pseudoprimo de Euler . No existen números que sean pseudoprimos de Euler-Jacobi en todas las bases como lo son los números de Carmichael . Solovay y Strassen demostraron que para cada n compuesto , para al menos n /2 bases menores que n , n no es un pseudoprimo de Euler-Jacobi. [1]
El pseudoprimo de Euler–Jacobi base 2 más pequeño es 561. Hay 11347 pseudoprimos de Euler–Jacobi base 2 que son menores que 25·10 9 (ver OEIS : A047713 ) (página 1005 de [2] ).
En la literatura (por ejemplo, [2] ), un pseudoprimo de Euler–Jacobi como el definido anteriormente a menudo se denomina simplemente pseudoprimo de Euler.
Función EulerJacobiTest(k) a = 2 si k == 1 entonces devuelve falso de lo contrario si k == 2 entonces devuelve verdadero de lo contrario si ( modPow(a,(k-1)/2,k) == Jacobi(a,k) ) entonces devuelve verdadero de lo contrario devuelve falso fin fin fin
