Número pseudoprimo de Euler

En aritmética, un número entero compuesto impar n se llama pseudoprimo de Euler en base a, si a y n son números coprimos, y

${\displaystyle a^{(n-1)/2}\equiv \pm 1{\pmod {n}}}$

(donde mod se refiere a la operación módulo).

La motivación de esta definición es el hecho de que todos los números primos p satisfacen la ecuación anterior que puede deducirse del pequeño teorema de Fermat, que afirma que si p es primo y coprimo de a, entonces a^p−1 ≡ 1 (mod p).

Supóngase que p>2 es primo. Entonces, p se puede expresar como 2q   1 donde q es un número entero. Así, a^{(2q 1) − 1} ≡ 1 (mod p), lo que significa que a^2q − 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 probar con bastante rapidez, lo que se puede usar para pruebas de primalidad probabilísticas. Estas pruebas son dos veces más fuertes que las pruebas basadas en el pequeño teorema de Fermat.

Todo número 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 todas las bases primas entre sí. Los pseudoprimos absolutos de Euler son un subconjunto de los pseudoprimos absolutos de Fermat, o números de Carmichael, y el pseudoprimo absoluto de Euler más pequeño es 1729 = 7 × 13 × 19.

Relación con los pseudoprimos de Euler-Jacobi

La condición ligeramente más fuerte de que:

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

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 enumerado a continuación, la página 90 del libro de Riesel, o su página 1003).^[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}

La prueba de un probable primo 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 principal a menudo se basa en la prueba fuerte.

Código en Lua

function EulerTest(k)
  a = 2
  if k == 1 then return false
  elseif k == 2 then return true
  else
    if (modPow(a,(k-1)/2,k) == 1) or (modPow(a,(k-1)/2,k) == k-1) then
      return true
    else
      return false
    end
  end
end

Ejemplos

Menores pseudoprimos de Euler en base n

Véase también

• Probable primo

Referencias

Bibliografía

• M. Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag, 1987.
• H. Riesel, "Prime numbers and computer methods of factorisation", Birkhäuser, Boston, Mass., 1985.