En teoría de números , un pseudoprime de Frobenius es un pseudoprime , 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 pseudoprimes de Frobenius se pueden definir con respecto a polinomios de grado al menos 2, pero se han estudiado más extensamente en el caso de polinomios cuadráticos . [3] [4]
Frobenius pseudoprimes wrt polinomios cuadráticos
Definición de pseudoprimes de Frobenius con respecto a un polinomio cuadrático monico , donde el discriminante no es un cuadrado, se puede expresar en términos de secuencias de Lucas y como sigue.
Un número compuesto n es un Frobenius pseudoprime si y solo si
- y
dónde es el símbolo de Jacobi .
Cuando se satisface la condición (2), la condición (3) se vuelve equivalente a
Por tanto, Frobenius la pseudoprima n se puede definir 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) son válidas para todos los primos que satisfacen la condición simple (1), se pueden utilizar como prueba de primos probables . (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 debe probar diferentes parámetros P y Q que no son múltiplos de n .)
Relaciones con otros pseudoprimes
Cada Frobenius pseudoprime también es
- un pseudoprime de Lucas con parámetros, ya que está definido por las condiciones (1) y (2); [2] [3] [5]
- un pseudoprime de Dickson con parámetros, ya que está definido por las condiciones (1) y (3 '); [5]
- una base pseudoprime de Fermat Cuándo .
La inversa de ninguna de estas afirmaciones es cierta, lo que hace que Frobenius pseudoprimes un subconjunto adecuado de cada uno de los conjuntos de pseudoprimes de Lucas y pseudoprimes de Dickson con parámetros , y pseudoprimes base de Fermat Cuándo . Además, se deduce que para los mismos parámetros, un número compuesto es un pseudoprime de Frobenius si y solo si es pseudoprime de Lucas y Dickson. En otras palabras, para cada par fijo de parámetros, el conjunto de pseudoprimes de Frobenius es igual a la intersección de los conjuntos de pseudoprimes de Lucas y Dickson.
Mientras cada Frobenius pseudoprime es un pseudoprime de Lucas, no es necesariamente un pseudoprime fuerte de Lucas . Por ejemplo, 6721 es el primer pseudoprime de Frobenius para, que no es un pseudoprime fuerte de Lucas.
Cada pseudoprime de Frobenius para es también un pseudoprime de Perrin restringido . Declaraciones análogas son válidas para otros polinomios cúbicos de la forma. [2]
Ejemplos de
Pseudoprimes de Frobenius con respecto al polinomio de Fibonacci se determinan en términos de los números de Fibonacci y números de Lucas . 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, ... (secuencia A212424 en la OEIS ).
Mientras que 323 es el primer pseudoprime de Lucas con respecto al polinomio de Fibonacci, el primer pseudoprime de Frobenius con respecto al mismo polinomio es 4181 (Grantham lo expresó como 5777 [2] pero varios autores han señalado que esto es incorrecto y, en cambio, es el primer pseudoprime conpara este polinomio [3] ).
Otro caso, Frobenius pseudoprimes con respecto al polinomio cuadrático se puede determinar usando el Lucas secuencia 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, 47311801, 479191 ... (secuencia A327655 en la OEIS )
En este caso, el primer pseudoprime de Frobenius con respecto al polinomio cuadrático es 119, que también es el primer pseudoprime de Lucas con respecto al mismo polinomio. Además,.
El polinomio cuadrático , es decir , tiene pseudoprimes más escasos en comparación con muchas otras cuadráticas simples. Usando el mismo proceso anterior, obtenemos la secuencia:
- 13333, 44801, 486157, 1615681, 3125281, 4219129, 9006401, 12589081, 13404751, 15576571, 16719781,….
Observe que solo hay 3 pseudoprimes por debajo de 500000, mientras que hay muchos pseudoprimes de Frobenius (1, −1) y (3, −1) por debajo de 500000.
Cada entrada en esta secuencia es un pseudoprime de Fermat a base 5, así como un pseudoprime de Lucas (3, −5), pero lo contrario no es cierto: 642001 es un pseudoprime tanto de psp-5 como de Lucas (3, -5), pero no es un pseudoprime de Frobenius (3, −5). (tenga en cuenta que la pseudoprima de Lucas para un par ( P , Q ) no necesita ser una pseudoprima de Fermat para la base | Q |, por ejemplo, 14209 es una pseudoprima de Lucas (1, −3), pero no una pseudoprima de Fermat para la base 3.
Pseudoprimes 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]
Pruebas de pseudoprimalidad
Las condiciones que definen el pseudoprime de Frobenius se pueden utilizar para probar un número n dado para determinar la primalidad probable . A menudo, estas pruebas no se basan en parámetros fijos., sino seleccionarlos 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 pseudoprimas de Frobenius, aunque pueden corresponder a diferentes parámetros.
Utilizando las ideas de selección de parámetros expuestas por primera vez en Baillie y Wagstaff (1980) [6] como parte de la prueba de primalidad de Baillie-PSW y utilizadas por Grantham en su prueba cuadrática de Frobenius , [7] se pueden crear pruebas cuadráticas aún mejores. En particular, se demostró que la elección de parámetros de módulo n cuadrático de no 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 pseudoprimes debajo .
Khashin propone otra prueba más. [8] Para un número n no cuadrado dado , 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:
- .
Mientras que todos los primos n pasan esta prueba, un compuesto n la pasa si y solo si n es un pseudoprime de Frobenius para. Al igual que en el ejemplo anterior, Khashin señala que no se ha encontrado pseudoprime para su prueba. Además, muestra que cualquiera que exista por debajo de 2 60 debe tener un factor menor que 19 o tener c > 128.
Propiedades
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 de pseudoprimalidad fuerte (p. Ej., 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 fuerte que la prueba de Lucas. Por ejemplo, 1763 es un pseudoprime de Lucas a ( P , Q ) = (3, -1) ya que U 1764 (3, -1) ≡ 0 (mod 1763) ( U (3, -1) se da en OEIS : A006190 ), y también pasa el paso de Jacobi ya que, pero falla la prueba de Frobenius ax 2 - 3 x - 1. Esta propiedad se puede ver claramente cuando el algoritmo se formula como se muestra en Crandall y Pomerance Algorithm 3.6.9 [3] o como lo muestra Loebenberger, [4] como el algoritmo realiza una prueba de Lucas seguida de una verificación adicional de 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 utilizar 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 para estos métodos no se aplican a las pruebas estándar o fuertes de Frobenius con valores fijos de (P, Q) descritos en esta página.
Con base en esta idea de pseudoprimes, se pueden construir algoritmos con límites de error fuertes en el peor de los casos. La prueba cuadrática de Frobenius , [7] que usa una prueba cuadrática de Frobenius más otras condiciones, tiene un límite de. Müller en 2001 propuso la prueba MQFT con límites de esencialmente. [9] Damgård y Frandsen en 2003 propusieron el EQFT con un límite de esencialmente. [10] Seysen en 2005 propuso la prueba SQFT con un límite de y una prueba SQFT3 con un límite de . [11]
Dado el mismo esfuerzo computacional, estos ofrecen mejores límites para el peor de los casos que la prueba de primalidad de Miller-Rabin de uso común .
Ver también
- Pseudoprime
- Lucas pseudoprime
- Ferdinand Georg Frobenius
- Prueba cuadrática de Frobenius
Referencias
- ^ Grantham, Jon (1998). Pseudoprimes de Frobenius (Informe). preimpresión.
- ^ a b c d e Grantham, Jon (2001). "Pseudoprimes de Frobenius" . Matemáticas de la Computación . 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). Números primos: una perspectiva computacional (2ª ed.). Springer-Verlag . ISBN 978-0-387-25282-7.
- ^ a b Loebenberger, Daniel (2008). "Una derivación simple para la prueba de Frobenius Pseudoprime" (PDF) . Archivo ePrint de criptología IACR . 2008 .
- ^ a b Rotkiewicz, Andrzej (2003). "Pseudoprimes de Lucas y Frobenius" (PDF) . Annales Mathematicae Silesianae . Wydawnictwo Uniwersytetu Śląskiego. 17 : 17–39.
- ^ Baillie, Robert; Wagstaff, Samuel S., Jr. (octubre de 1980). "Lucas Pseudoprimes" (PDF) . Matemáticas de la Computación . 35 (152): 1391-1417. doi : 10.1090 / S0025-5718-1980-0583518-6 . Señor 0583518 .
- ^ a b 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 / jnth.1998.2247 .
- ^ Khashin, Sergey (julio de 2013). "Contraejemplos para la prueba de primalidad de Frobenius". arXiv : 1307.7920 [ matemáticas.NT ].
- ^ Müller, Siguna (2001). "Una prueba de prima probable con muy alta confianza para N Equiv 1 Mod 4". Actas de la 7ma Conferencia Internacional sobre Teoría y Aplicación de la Criptología y Seguridad de la Información: Avances en Criptología . ASIACRYPT. págs. 87-106. doi : 10.1007 / 3-540-45682-1_6 . ISBN 3-540-42987-5.
- ^ 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 .
- ^ Seysen, Martin. Una prueba de primalidad de Frobenius cuadrática simplificada , 2005.
enlaces externos
- Weisstein, Eric W. "Frobenius Pseudoprime" . MathWorld .
- Weisstein, Eric W. "Strong Frobenius Pseudoprime" . MathWorld .
- Jacobsen, Dana Pseudoprime Estadísticas, tablas y datos (datos de Frobenius (1, -1) y (3, -5) pseudoprimes)