Número pseudoprimo de Euler-Jacobi

En teoría de números, un número 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 números coprimos, y

a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

donde $\left({\frac {a}{n}}\right)$ es el símbolo de Jacobi.

Si n es un entero compuesto impar que satisface la congruencia anterior, entonces n se denomina número pseudoprimo de Euler-Jacobi' (o, más comúnmente, pseudoprimo de Euler) respecto a la base a.

Propiedades

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 dedicado al criterio de Euler. La ecuación se puede probar con bastante rapidez, lo que se puede usar para realizar 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.

Cada pseudoprimo de Euler-Jacobi es también un pseudoprimo de Fermat y un pseudoprimo de Euler. No hay 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úmero compuesto n, para al menos n/2 bases menores que n, n no es un pseudoprimo de Euler-Jacobi.[1]

El pseudoprimo de base 2 de Euler-Jacobi más pequeño es 561. Hay 11347 pseudoprimos de base 2 de Euler-Jacobi que son menores que 25 · 10⁹ (véase (sucesión A047713 en OEIS)) y la página 1005 de The pseudoprimes to 25·10⁹[2]).

En la literatura (por ejemplo, en el texto mencionado),[2] un pseudoprimo de Euler-Jacobi como se definió anteriormente a menudo se denomina simplemente pseudoprimo de Euler.

Véase también

Probable primo

Referencias

Solovay, R.; Strassen, V. (1 de marzo de 1977). «A Fast Monte-Carlo Test for Primality». SIAM Journal on Computing 6 (1): 84-85. ISSN 0097-5397. doi:10.1137/0206006.
Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). «The pseudoprimes to 25·10⁹». Mathematics of Computation 35 (151): 1003-1026. doi:10.1090/S0025-5718-1980-0572872-7.

Datos: Q3343104

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.

[1] Solovay, R.; Strassen, V. (1 de marzo de 1977). «A Fast Monte-Carlo Test for Primality». SIAM Journal on Computing 6 (1): 84-85. ISSN 0097-5397. doi:10.1137/0206006.

[PSW-2] Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). «The pseudoprimes to 25·10⁹». Mathematics of Computation 35 (151): 1003-1026. doi:10.1090/S0025-5718-1980-0572872-7.