Pseudoprima de Frobenius

En teoría de números, un pseudoprimo de Frobenius es un pseudoprimo que ha pasado la prueba de tres pasos de pertenencia a primos probables de Jon Grantham de 1996 . [1] [2]

Los números pseudoprimos de Frobenius se definen con respecto a un polinomio dado . Para ciertos tipos de polinomios, los pseudoprimos de Frobenius están relacionados con otros tipos de pseudoprimos.

Ejemplo

Los números pseudoprimos de Frobenius con respecto al polinomio forman la secuencia:

4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079,... (secuencia A212424 en OEIS ).

Propiedades

Aunque la prueba de Frobenius de un solo paso es más lenta que la prueba de un solo paso de la mayoría de las otras pruebas de pseudo-primalidad, tiene una menor probabilidad de error en el peor de los casos , [1] , que solo se puede obtener con siete pases de la prueba de primalidad de Miller-Rabin .

Fuerte pseudosimple Frobenius

Un pseudoprimo se denomina pseudoprimo fuerte de Frobenius si cumple restricciones adicionales. [3]

Véase también

Enlaces

  1. ↑ 1 2 Weisstein, Eric W. Frobenius pseudoprime  (inglés) en el sitio web de Wolfram MathWorld .
  2. ↑ John Grantham. Frobenius pseudoprimes  (inglés)  // Matemáticas de la computación : diario. - 2001. - vol. 70 , núm. 234 . - Pág. 873-891 . -doi : 10.1090/ S0025-5718-00-01197-2 .
  3. ↑ Weisstein, Eric W. Strong Frobenius pseudoprime  en el sitio web Wolfram MathWorld .

Enlaces externos