En teoría de números, un número pseudoprimo de Frobenius es un número pseudoprimo, cuya definición se inspiró en el test cuadrático de Frobenius descrito por Jon Grantham en un documento preimpreso en 1998 y publicado en 2000.
de la manera que se detalla a continuación.
Un número compuesto n es un pseudoprimo de Frobenius
Dado que las condiciones (2) y (3) se cumplen para todos los números primos que satisfacen simplemente la condición (1), se pueden usar como una prueba de probable primo (si la condición (1) falla, el máximo común divisor es menor que n, en cuyo caso es un factor no trivial y n es compuesto, o el MCD es igual a n, en cuyo caso se deben probar diferentes parámetros P y Q que son no múltiplos de n).
Además, se sigue que para los mismos parámetros
Por ejemplo, 6721 es el primer pseudoprimo de Frobenius para
, que no es un pseudoprimo de Lucas fuerte.
Enunciados análogos valen para otros polinomios cúbicos de la forma
, el primer pseudoprimo de Frobenius con respecto al mismo polinomio es 4181 (Grantham lo declaró como 5777[2], pero varios autores han notado que esto es incorrecto y, en cambio, es el primer pseudoprimo con
Otro caso, los pseudoprimos de Frobenius con respecto al polinomio cuadrático
se pueden determinar usando la secuencia de Lucas
y son: En este caso, el primer pseudoprimo de Frobenius con respecto al polinomio cuadrático
es 119, que es también el primer pseudoprimo de Lucas con respecto al mismo polinomio.
, tiene pseudoprimos más dispersos en comparación con muchos otros cuadráticos simples.
También se definen los pseudoprimos fuertes de Frobenius.
[2] Los detalles sobre la generación de polinomios cuadráticos se pueden encontrar en Crandall y Pomerance.
[3] Las condiciones que definen el pseudoprimo de Frobenius se pueden utilizar para probar un número dado n para determinar su probable primalidas.
A menudo, estas pruebas no se basan en parámetros fijos
, sino que se seleccionan de cierta manera según el número de entrada n para disminuir la proporción de falso positivo y falso negativo, es decir, números compuestos que pasan la prueba.
A veces, estos números compuestos se denominan comúnmente pseudoprimos de Frobenius, aunque pueden corresponder a diferentes parámetros.
Por ejemplo, para los parámetros (P,2), donde P es el primer entero impar que satisface
[8] Para un número no cuadrado dado n, primero se calcula un parámetro c como el primo impar más pequeño que tiene el símbolo de Jacobi
Similar al ejemplo anterior, Khashin señala que no se ha encontrado ningún pseudoprimo para su prueba.
Se debe tener en cuenta que la prueba de Frobenius cuadrática es más fuerte que la prueba de Lucas.
Por ejemplo, 1763 es un pseudoprimo de Lucas para (P, Q)= (3, -1) ya que U1764(3,-1) = 0 (mod 1763) (U(3,-1) se da en (sucesión A006190 en OEIS)), y también satisface el criterio de Jacobi desde
Téngase en cuenta que estos tienen más pasos, requisitos adicionales y cómputo adicional no despreciable más allá de lo que se describe en esta página.
Es importante tener en cuenta que los límites de error para estos métodos no se aplican a las pruebas de Frobenius estándar o fuerte con valores fijos de (P,Q) que se describen en esta página.
Müller en 2001 propuso la prueba MQFT con límites esencialmente de
[9] Damgård y Frandsen en 2003 propusieron el EQFT con un límite esencialmente de
[10] Seysen en 2005 propuso la prueba SQFT con un límite de