En aritmética , un entero compuesto impar n se denomina pseudoprimo de Euler para base a , si a y n son coprimos , y
(donde mod se refiere a la operación módulo ).
La motivación para esta definición es el hecho de que todos los números primos p satisfacen la ecuación anterior que se puede deducir del pequeño teorema de Fermat . El teorema de Fermat afirma que si p es primo y coprimo con a , entonces a p −1 ≡ 1 (mod p ). Supongamos que p >2 es primo, entonces p puede expresarse como 2 q + 1 donde q es un entero. Por lo tanto, a (2 q +1) − 1 ≡ 1 (mod p ), lo que significa que a 2 q − 1 ≡ 0 (mod p ). Esto se puede factorizar como ( a q − 1)( a q + 1) ≡ 0 (mod p ), que es equivalente a a ( p −1)/2 ≡ ±1 (mod p ).
La ecuación se puede comprobar con bastante rapidez, lo que puede utilizarse para realizar pruebas de primalidad probabilísticas . Estas pruebas son el doble de sólidas que las pruebas basadas en el pequeño teorema de Fermat.
Todo pseudoprimo de Euler es también un pseudoprimo de Fermat . No es posible producir una prueba definitiva de primalidad basada en si un número es un pseudoprimo de Euler porque existen pseudoprimos de Euler absolutos , números que son pseudoprimos de Euler para cada base relativamente prima a ellos mismos. Los pseudoprimos de Euler absolutos son un subconjunto de los pseudoprimos de Fermat absolutos, o números de Carmichael , y el pseudoprimo de Euler absoluto más pequeño es 1729 = 7×13×19 (secuencia A033181 en la OEIS ).
La condición ligeramente más fuerte que
donde n es un compuesto impar, el máximo común divisor de a y n es igual a 1, y ( a / n ) es el símbolo de Jacobi , es la definición más común de un pseudoprimo de Euler. Véase, por ejemplo, la página 115 del libro de Koblitz que se indica a continuación, la página 90 del libro de Riesel o la página 1003 de. [1] Se puede encontrar una discusión de los números de esta forma en Pseudoprimo de Euler–Jacobi . No hay pseudoprimos absolutos de Euler–Jacobi. [1] : p. 1004
Una prueba de primos probables fuerte es incluso más fuerte que la prueba de Euler-Jacobi, pero requiere el mismo esfuerzo computacional. Debido a esta ventaja sobre la prueba de Euler-Jacobi, el software de prueba de primos a menudo se basa en la prueba fuerte.
Función EulerTest(k) a = 2 si k == 1 entonces devuelve falso de lo contrario si k == 2 entonces devuelve verdadero de lo contrario m = modPow(a,(k-1)/2,k) si (m == 1) o (m == k-1) entonces devuelve verdadero de lo contrario devuelve falso fin fin fin
