Frobenius pseudoprime

En teoría de números , un pseudoprimo de Frobenius es un pseudoprimo , cuya definición se inspiró en la prueba cuadrática de Frobenius descrita por Jon Grantham en una preimpresión de 1998 y publicada en 2000. ^{[1] [2]} Los pseudoprimos de Frobenius se pueden definir con respecto a polinomios de grado al menos 2, pero se han estudiado más ampliamente en el caso de polinomios cuadráticos . ^{[3] [4]}

Pseudoprimos de Frobenius con polinomios cuadráticos

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

Un número compuesto n es un pseudoprimo de Frobenius si y sólo si ${\displaystyle (P,Q)}$

${\displaystyle (1)\qquad \gcd(n,2QD)=1,}$

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

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

¿Dónde está el símbolo de Jacobi ? ${\displaystyle \delta =\left({\tfrac {D}{n}}\right)}$

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

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

Por lo tanto, un Frobenius pseudoprime n puede definirse de manera equivalente mediante las condiciones (1-2) y (3), o mediante las condiciones (1-2) y (3′). ${\displaystyle (P,Q)}$

Dado que las condiciones (2) y (3) se cumplen para todos los primos que satisfacen la condición simple (1), pueden usarse como una prueba de primalidad probable . (Si la condición (1) falla, entonces 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 no son múltiplos de n .)

Relaciones con otros pseudoprimos

Cada Frobenius pseudoprime también es ${\displaystyle (P,Q)}$

• un pseudoprimo de Lucas con parámetros , ya que está definido por las condiciones (1) y (2); ^{[2] [3] [5]} ${\displaystyle (P,Q)}$
• un pseudoprimo de Dickson con parámetros , ya que está definido por las condiciones (1) y (3'); ^[5] ${\displaystyle (P,Q)}$
• una base pseudoprime de Fermat cuando . ${\displaystyle |Q|}$ ${\displaystyle |Q|>1}$

Lo contrario de ninguna de estas afirmaciones es cierto, lo que convierte a los pseudoprimos de Frobenius en un subconjunto adecuado de cada uno de los conjuntos de pseudoprimos de Lucas y pseudoprimos de Dickson con parámetros , y pseudoprimos de Fermat con base cuando . Además, se deduce que para los mismos parámetros , un número compuesto es un pseudoprimo de Frobenius si y sólo si es un pseudoprimo de Lucas y Dickson. En otras palabras, para cada par fijo de parámetros , el conjunto de pseudoprimos de Frobenius es igual a la intersección de los conjuntos de pseudoprimos de Lucas y Dickson. ${\displaystyle (P,Q)}$ ${\displaystyle (P,Q)}$ ${\displaystyle |Q|}$ ${\displaystyle |Q|>1}$ ${\displaystyle (P,Q)}$ ${\displaystyle (P,Q)}$

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

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

Ejemplos

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

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

Mientras que 323 es el primer pseudoprimo de Lucas con respecto al polinomio de Fibonacci , el primer pseudoprimo de Frobenius con respecto al mismo polinomio es 4181 (Grantham lo indicó como 5777 ^[2] , pero varios autores han notado que esto es incorrecto y, en cambio, es el primer pseudoprimo con para este polinomio ^[3] ). ${\displaystyle x^{2}-x-1}$ ${\displaystyle \left({\tfrac {5}{n}}\right)=-1}$

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

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

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

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

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

Observe que solo hay 3 de estos pseudoprimos 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 pseudoprimo de Fermat en base 5, así como un pseudoprimo de Lucas (3, −5), pero lo contrario no es cierto: 642,001 es a la vez un psp-5 y un pseudoprimo de Lucas (3,-5). pero no es un pseudoprimo de Frobenius (3, −5). (Tenga en cuenta que el pseudoprimo de Lucas para un par ( P , Q ) no necesita ser un 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

También se definen pseudoprimos fuertes de Frobenius. ^[2] Los detalles sobre la implementación de polinomios cuadráticos se pueden encontrar en Crandall y Pomerance. ^[3]

Al imponer las restricciones que y , los autores de ^[6] muestran cómo elegir y de modo que solo haya cinco números compuestos impares menores que para los cuales (3) es válido, es decir, para los cuales . ${\displaystyle \delta =-1}$ ${\displaystyle Q\neq \pm 1}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle 10^{15}}$ ${\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}}$

Pruebas de pseudoprimalidad

Las condiciones que definen a Frobenius pseudoprime se pueden utilizar para probar la primalidad probable de un número dado n . A menudo, estas pruebas no se basan en parámetros fijos , sino que los seleccionan de cierta manera dependiendo del número de entrada n para disminuir la proporción de falsos positivos , 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. ${\displaystyle (P,Q)}$

Utilizando ideas de selección de parámetros expuestas por primera vez en Baillie y Wagstaff (1980) ^[7] como parte de la prueba de primalidad de Baillie-PSW y utilizadas por Grantham en su prueba cuadrática de Frobenius , ^[8] se pueden crear pruebas cuadráticas aún mejores. En particular, se demostró que elegir parámetros del módulo n cuadrático sin residuos (basado en el símbolo de Jacobi ) hace pruebas mucho más sólidas y es una de las razones del éxito de la prueba de primalidad de Baillie-PSW . Por ejemplo, para los parámetros ( P ,2), donde P es el primer entero impar que satisface , no hay pseudoprimos por debajo de 2 ⁶⁴ . ${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$

Khashin propone otra prueba más. ^[9] Para un número no cuadrado dado n , primero calcula un parámetro c como el primo impar más pequeño que tiene el símbolo de Jacobi y luego verifica la congruencia: ${\displaystyle \left({\tfrac {c}{n}}\right)=-1}$

${\displaystyle (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 sólo si n es un pseudoprimo de Frobenius para . Al igual que en el ejemplo anterior, Khashin señala que no se ha encontrado ningún pseudoprime para su prueba. Además, muestra que cualquiera que exista por debajo de 2 ⁶⁰ debe tener un factor menor que 19 o tener c > 128. ${\displaystyle (P,Q)=(2,1-c)}$

Propiedades

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

Tenga en cuenta que la prueba cuadrática de Frobenius es más sólida 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 proporciona en OEIS : A006190 ), y también pasa el paso de Jacobi desde , pero falla la prueba de Frobenius para x ² – 3 x – 1. Esta propiedad se puede ver claramente cuando el algoritmo se formula como se muestra en 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 de la condición de Frobenius. ${\displaystyle \left({\tfrac {13}{1763}}\right)=-1}$

Si bien la prueba cuadrática de Frobenius no tiene límites de error formales más allá de la prueba de Lucas, puede usarse como base para métodos con límites de error mucho más pequeños. Tenga en cuenta que estos tienen más pasos, requisitos adicionales y cálculos adicionales no despreciables más allá de lo que se describe en esta página. Es importante tener en cuenta que los límites de error de estos métodos no se aplican a las pruebas estándar o fuertes de Frobenius con valores fijos de (P,Q) descritas en esta página.

Sobre la base de esta idea de pseudoprimos, se pueden construir algoritmos con fuertes límites de error en el peor de los casos. La prueba cuadrática de Frobenius , ^[8] que utiliza una prueba cuadrática de Frobenius más otras condiciones, tiene un límite de . Müller propuso en 2001 la prueba MQFT con límites de esencialmente . ^[10] Damgård y Frandsen propusieron en 2003 el EQFT con un límite de esencialmente . ^[11] Seysen en 2005 propuso la prueba SQFT con un límite de y una prueba SQFT3 con un límite de . ^[12] ${\displaystyle {\tfrac {1}{7710}}}$ ${\displaystyle {\tfrac {1}{131040^{t}}}}$ ${\displaystyle {\tfrac {256}{{331776}^{t}}}}$ ${\displaystyle {\tfrac {1}{{4096}^{t}}}}$ ${\displaystyle {\tfrac {16}{336442^{t}}}}$

Dado el mismo esfuerzo computacional, estos ofrecen mejores límites en el peor de los casos que la prueba de primalidad de Miller-Rabin comúnmente utilizada .

Ver también

• pseudoprime
• Lucas pseudoprime
• Fernando Georg Frobenius
• Prueba cuadrática de Frobenius

Referencias

1. Grantham, Jon (1998). Frobenius pseudoprimes (Reporte). preimpresión.
2. Grantham, Jon (2001). "Frobenius pseudoprimos". Matemáticas de la Computación . 70 (234): 873–891. arXiv : 1903.06820 . Código Bib : 2001MaCom..70..873G. doi : 10.1090/S0025-5718-00-01197-2 .
3. Crandall, Richard ; Pomerancia, Carl (2005). Números primos: una perspectiva computacional (2ª ed.). Springer-Verlag . ISBN 978-0-387-25282-7.
4. Loebenberger, Daniel (2008). "Una derivación simple de la prueba Pseudoprime de Frobenius" (PDF) . Archivo ePrint de criptología IACR . 2008 .
5. Rotkiewicz, Andrzej (2003). «Lucas y Frobenius pseudoprimes» (PDF) . Annales Mathematicae Silesianae . 17 . Wydawnictwo Uniwersytetu Śląskiego: 17–39.
6. Robert Baillie; Andrés Fiori; Samuel S. Wagstaff, Jr. (julio de 2021). "Fortalecimiento de la prueba de primalidad de Baillie-PSW". Matemáticas de la Computación . 90 (330): 1931-1955. arXiv : 2006.14425 . doi : 10.1090/mcom/3616. ISSN  0025-5718. S2CID  220055722.
7. Baillie, Robert; Wagstaff, Samuel S. Jr. (octubre de 1980). «Lucas Pseudoprimos» (PDF) . Matemáticas de la Computación . 35 (152): 1391-1417. doi : 10.1090/S0025-5718-1980-0583518-6 . SEÑOR  0583518.
8. Grantham, Jon (1998). "Una prueba principal probable con alta confianza". Revista de teoría de números . 72 (1): 32–47. arXiv : 1903.06823 . CiteSeerX 10.1.1.56.8827 . doi :10.1006/junio.1998.2247. S2CID  119640473. 
9. Khashin, Sergey (julio de 2013). "Contraejemplos de la prueba de primalidad de Frobenius". arXiv : 1307.7920 [matemáticas.NT].
10. Müller, Siguna (2001). "Una prueba principal probable con muy alta confianza para N Equiv 1 Mod 4". Actas de la Séptima Conferencia Internacional sobre Teoría y Aplicación de la Criptología y Seguridad de la Información: Avances en Criptología . ASIACRIPTO. págs. 87-106. doi : 10.1007/3-540-45682-1_6 . ISBN 3-540-42987-5.
11. Damgård, Ivan Bjerre ; Frandsen, Gudmund Skovbjerg (octubre de 2006). "Una prueba de primalidad de Frobenius cuadrática extendida con estimación de error promedio y en el peor de los casos" (PDF) . Revista de criptología . 19 (4): 489–520. doi :10.1007/s00145-006-0332-x. S2CID  34417193.
12. Seysen, Martín. Una prueba de primalidad cuadrática simplificada de Frobenius, 2005.

enlaces externos

• Weisstein, Eric W. "Frobenius Pseudoprime". MundoMatemático .
• Weisstein, Eric W. "Fuerte Frobenius Pseudoprime". MundoMatemático .
• Jacobsen, Dana Pseudoprime Estadísticas, tablas y datos (datos para Frobenius (1,-1) y (3,-5) pseudoprimes)