Número pseudoprimo de Frobenius

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. Los pseudoprimos de Frobenius^[1]^[2] se pueden definir con respecto a polinomios de grado al menos 2, pero se han estudiado más extensamente en el caso de los polinomios cuadráticos.^[3]^[4]

Pseudoprimos de Frobenius con respecto a los polinomios cuadráticos[editar]

La definición de pseudoprimos de Frobenius con respecto a un polinomio cuadrático mónico $x^{2}-Px+Q$ , donde el discriminante $D=P^{2}-4Q$ no es un cuadrado, se puede expresar en términos de una sucesión de Lucas $U_{n}(P,Q)$ y $V_{n}(P,Q)$ de la manera que se detalla a continuación.

Un número compuesto n es un pseudoprimo de Frobenius $(P,Q)$ si y solo si

(1)\qquad {\text{mcd}}(n,2QD)=1,

(2)\qquad U_{n-\delta }(P,Q)\equiv 0{\pmod {n}},

y

(3)\qquad V_{n-\delta }(P,Q)\equiv 2Q^{(1-\delta )/2}{\pmod {n}},

donde $\delta =\left({\tfrac {D}{n}}\right)$ es el símbolo de Jacobi.

Cuando se cumple la condición (2), la condición (3) se vuelve equivalente a

(3')\qquad V_{n}(P,Q)\equiv P{\pmod {n}}.

Por lo tanto, el pseudoprimo $(P,Q)$ de Frobenius $n$ puede definirse de manera equivalente por las condiciones (1-2) y (3), o por las condiciones (1-2) y (3′).

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$ ).

Relaciones con otros pseudoprimos[editar]

Cada pseudoprimo de Frobenius $(P,Q)$ también es

Un número pseudoprimo de Lucas con parámetros $(P,Q)$ , ya que está definido por las condiciones (1) y (2);^[2]^[3]^[5]
Un número pseudoprimo de Dickson con parámetros $(P,Q)$ , ya que está definido por las condiciones (1) y (3');^[5]
Un número pseudoprimo de Fermat base $|Q|$ cuando $|Q|>1$ .

El recíproco de ninguna de estas declaraciones es cierto, lo que hace de los pseudoprimos de Frobenius $(P,Q)$ un subconjunto propio de cada uno de los conjuntos de pseudoprimos de Lucas y pseudoprimos de Dickson con parámetros $(P,Q)$ , y base de pseudoprimos de Fermat $|Q|$ cuando $|Q|>1$ .

Además, se sigue que para los mismos parámetros $(P,Q)$ , un número compuesto es un pseudoprimo de Frobenius si y solo si es un pseudoprimo tanto de Lucas como de Dickson. En otras palabras, para cada par fijo de parámetros $(P,Q)$ , el conjunto de pseudoprimos de Frobenius es igual a la intersección de los conjuntos de pseudoprimos de Lucas y Dickson.

Si bien cada pseudoprimo de Frobenius $(P,Q)$ es un pseudoprimo de Lucas, no es necesariamente un pseduprimo de Lucas fuerte. Por ejemplo, 6721 es el primer pseudoprimo de Frobenius para $(P,Q)=(1,-1)$ , que no es un pseudoprimo de Lucas fuerte.

Cada pseudoprimo de Frobenius a $x^{3}-x-1$ es también un pseudoprimo de Perrin restringido. Enunciados análogos valen para otros polinomios cúbicos de la forma $x^{3}-rx^{2}+sx-1$ .^[2]

Ejemplos[editar]

Los pseudoprimos de Frobenius con respecto al polinomio de Fibonacci $x^{2}-x-1$ se determinan en términos de la sucesión de Fibonacci $F_{n}=U_{n}(1,-1)$ y número de Lucas $L_{n}=V_{n}(1,-1)$ . Tales pseudoprimos de Frobenius forman la secuencia:

4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 75077, 90061, 96049, 97921, 100127, 113573, 118441, 146611, 161027, 162133, 163081, 186961, 197209, 219781, 231703, 252601, 254321, 257761, 268801, 272611, 283361, 302101, 303101, 330929, 399001, 430127, 433621, 438751, 489601, ... (sucesión A212424 en OEIS).

Si bien 323 es el primer número pseudoprimo de Lucas con respecto al polinomio de Fibonacci $x^{2}-x-1$ , 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 $\left({\tfrac {5}{n}}\right)=-1$ para este polinomio^[3]).

Otro caso, los pseudoprimos de Frobenius con respecto al polinomio cuadrático $x^{2}-3x-1$ se pueden determinar usando la secuencia de Lucas $(3,-1)$ y son:

119, 649, 1189, 4187, 12871, 14041, 16109, 23479, 24769, 28421, 31631, 34997, 38503, 41441, 48577, 50545, 56279, 58081, 59081, 61447, 75077, 91187, 95761, 96139, 116821, 127937, 146329, 148943, 150281, 157693, 170039, 180517, 188501, 207761, 208349, 244649, 281017, 311579, 316409, 349441, 350173, 363091, 371399, 397927, 423721, 440833, 459191, 473801, 479119, 493697, ... (sucesión A327655 en OEIS)

En este caso, el primer pseudoprimo de Frobenius con respecto al polinomio cuadrático $x^{2}-3x-1$ es 119, que es también el primer pseudoprimo de Lucas con respecto al mismo polinomio. Además, $\left({\tfrac {13}{119}}\right)=-1$ .

El polinomio cuadrático $x^{2}-3x-5$ , es decir, $(P,Q)=(3,-5)$ , tiene pseudoprimos más dispersos en comparación con muchos otros cuadráticos simples. Usando el mismo proceso que el anterior, obtenemos la secuencia:

13333, 44801, 486157, 1615681, 3125281, 4219129, 9006401, 12589081, 13404751, 15576571, 16719781, ...

Obsérvese que solo hay tres pseudoprimos de este tipo por debajo de 500.000, mientras que hay muchos pseudoprimos de Frobenius (1, -1) y (3, -1) por debajo de 500.000.

Cada entrada en esta secuencia es un número pseudoprimo de Fermat en base 5 así como un pseudoprimo de Lucas (3, -5), pero lo contrario no es cierto: 642001 es tanto un pseudoprimo de psp-5 como de Lucas (3,-5), pero no es un pseudoprimo de Frobenius (3, -5) (debe tenerse en cuenta que un número pseudoprimo de Lucas para un par $(P, Q)$ no necesita ser un número pseudoprimo de Fermat para la base| $Q$ |, por ejemplo, 14209 es un pseudoprimo de Lucas (1, -3), pero no un pseudoprimo de Fermat para la base 3.

Pseudoprimos fuertes de Frobenius[editar]

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]

Pruebas de pseudoprimalidad[editar]

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 $(P,Q)$ , 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.

El uso de ideas de selección de parámetros fue expuesto por primera vez en Baillie y Wagstaff (1980)^[6] como parte del test de primalidad de Baillie-PSW y utilizado por Grantham en su test cuadrático de Frobenius,^[7] que permite crear incluso mejores pruebas cuadráticas. En particular, se demostró que elegir parámetros sin residuo cuadrático de módulo n (basados en el símbolo de Jacobi) permite que las pruebas sean mucho más sólidas, y es una de las razones del éxito del test de primalidad de Baillie-PSW.

Por ejemplo, para los parámetros (P,2), donde P es el primer entero impar que satisface $\left({\tfrac {D}{n}}\right)=-1$ , no hay pseudoprimos debajo de $2^{64}$ .

Khashin propone otra prueba más.^[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 $\left({\tfrac {c}{n}}\right)=-1$ , y luego se verifica la congruencia:

(1+{\sqrt {c}})^{n}\equiv (1-{\sqrt {c}}){\pmod {n}}

.

Mientras que todos los primos n pasan esta prueba, un compuesto n la pasa si y solo si n es un pseudoprimo de Frobenius para $(P,Q)=(2,1-c)$ .

Similar al ejemplo anterior, Khashin señala que no se ha encontrado ningún pseudoprimo para su prueba. Además, demostró que cualquiera que exista por debajo de 2⁶⁰ debe tener un factor menor que 19 o tener c > 128.

Propiedades[editar]

El costo computacional de la prueba de pseudoprimalidad de Frobenius con respecto a los polinomios cuadráticos es aproximadamente tres veces el costo de una prueba pseudoprimalidad fuerte (por ejemplo, una sola ronda del test de primalidad de Miller-Rabin), 1,5 veces el de una prueba pseudoprimalidad de Lucas y un poco más que un test de primalidad de Baillie-PSW.

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 U₁₇₆₄(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 $\left({\tfrac {13}{1763}}\right)=-1$ , pero falla la prueba de Frobenius para (x² - 3x - 1). Esta propiedad se puede ver claramente cuando el algoritmo se formula como se muestra en el Algoritmo de Crandall y Pomerance 3.6.9^[3] o como lo muestra Loebenberger,^[4] cuando el algoritmo realiza una prueba de Lucas seguida de una verificación adicional para la condición de Frobenius.

Si bien la prueba cuadrática de Frobenius no tiene límites de error formales más allá de la prueba de Lucas, se puede usar como base para métodos con límites de error mucho más pequeños. 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.

Sobre la base de esta idea de los pseudoprimos, se pueden construir algoritmos con fuertes límites de error en el peor de los casos. El test cuadrático de Frobenius,^[7] utilizando una prueba de Frobenius cuadrática más otras condiciones, tiene un límite de ${\tfrac {1}{7710}}$ . Müller en 2001 propuso la prueba MQFT con límites esencialmente de ${\tfrac {1}{131040^{t}}}$ .^[9] Damgård y Frandsen en 2003 propusieron el EQFT con un límite esencialmente de ${\tfrac {256}{{331776}^{t}}}$ .^[10]

Seysen en 2005 propuso la prueba SQFT con un límite de ${\tfrac {1}{{4096}^{t}}}$ y una prueba SQFT3 con un límite de ${\tfrac {16}{336442^{t}}}$ . ^[11]

Dado el mismo esfuerzo computacional, estos procedimientos ofrecen mejores límites en el peor de los casos que el test de primalidad de Miller-Rabin de uso común.

Véase también[editar]

Referencias[editar]

↑ Grantham, Jon (1998), Frobenius pseudoprimes, preprint .
↑ ^a ^b ^c ^d ^e Grantham, Jon (2001). «Frobenius pseudoprimes». Mathematics of Computation 70 (234): 873-891. arXiv:1903.06820. doi:10.1090/S0025-5718-00-01197-2.
↑ ^a ^b ^c ^d ^e Crandall, Richard; Pomerance, Carl (2005). Prime numbers: A computational perspective (2nd edición). Springer Science+Business Media. ISBN 978-0-387-25282-7.
↑ ^a ^b Loebenberger, Daniel (2008). «A Simple Derivation for the Frobenius Pseudoprime Test». IACR Cryptology ePrint Archive 2008.
↑ ^a ^b Rotkiewicz, Andrzej (2003). «Lucas and Frobenius pseudoprimes». Annales Mathematicae Silesianae (Wydawnictwo Uniwersytetu Śląskiego) 17: 17-39.
↑ Baillie, Robert; Wagstaff, Samuel S. Jr. (October 1980). «Lucas Pseudoprimes». Mathematics of Computation 35 (152): 1391-1417. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6.
↑ ^a ^b Grantham, Jon (1998). «A Probable Prime Test With High Confidence». Journal of Number Theory 72 (1): 32-47. doi:10.1006/jnth.1998.2247. «citeseerx: 10.1.1.56.8827 eprint: 1903.06823».
↑ Khashin, Sergey (July 2013). Counterexamples for Frobenius primality test (math.NT). «eprint: 1307.7920».
↑ Müller, Siguna (2001). «A Probable Prime Test with Very High Confidence for N Equiv 1 Mod 4». Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. ASIACRYPT. pp. 87-106. ISBN 3-540-42987-5. doi:10.1007/3-540-45682-1_6.
↑ Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (October 2006). «An Extended Quadratic Frobenius Primality Test with Average- and Worst-Case Error Estimate». Journal of Cryptology 19 (4): 489-520. doi:10.1007/s00145-006-0332-x.
↑ Seysen, Martin. A Simplified Quadratic Frobenius Primality Test, 2005.

Enlaces externos[editar]

Weisstein, Eric W. «Frobenius Pseudoprime». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Weisstein, Eric W. «Strong Frobenius Pseudoprime». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Jacobsen, Dana Pseudoprime Statistics, Tables, and Data (datos para Frobenius (1,-1) y (3,-5) pseudoprimes)

Datos: Q5505102

[Grantham98-1] Grantham, Jon (1998), Frobenius pseudoprimes, preprint .

[Grantham01-2] Grantham, Jon (2001). «Frobenius pseudoprimes». Mathematics of Computation 70 (234): 873-891. arXiv:1903.06820. doi:10.1090/S0025-5718-00-01197-2.

[CP05-3] Crandall, Richard; Pomerance, Carl (2005). Prime numbers: A computational perspective (2nd edición). Springer Science+Business Media. ISBN 978-0-387-25282-7.

[Loebenberger08-4] Loebenberger, Daniel (2008). «A Simple Derivation for the Frobenius Pseudoprime Test». IACR Cryptology ePrint Archive 2008.

[Rotkiewicz03-5] Rotkiewicz, Andrzej (2003). «Lucas and Frobenius pseudoprimes». Annales Mathematicae Silesianae (Wydawnictwo Uniwersytetu Śląskiego) 17: 17-39.

[lpsp-6] Baillie, Robert; Wagstaff, Samuel S. Jr. (October 1980). «Lucas Pseudoprimes». Mathematics of Computation 35 (152): 1391-1417. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6.

[QFT-7] Grantham, Jon (1998). «A Probable Prime Test With High Confidence». Journal of Number Theory 72 (1): 32-47. doi:10.1006/jnth.1998.2247. «citeseerx: 10.1.1.56.8827 eprint: 1903.06823».

[Khashin13-8] Khashin, Sergey (July 2013). Counterexamples for Frobenius primality test (math.NT). «eprint: 1307.7920».

[9] Müller, Siguna (2001). «A Probable Prime Test with Very High Confidence for N Equiv 1 Mod 4». Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. ASIACRYPT. pp. 87-106. ISBN 3-540-42987-5. doi:10.1007/3-540-45682-1_6.

[10] Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (October 2006). «An Extended Quadratic Frobenius Primality Test with Average- and Worst-Case Error Estimate». Journal of Cryptology 19 (4): 489-520. doi:10.1007/s00145-006-0332-x.

[11] Seysen, Martin. A Simplified Quadratic Frobenius Primality Test, 2005.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]