Un pseudoprime fuerte es un número compuesto que pasa la prueba de primalidad de Miller-Rabin . Todos los números primos pasan esta prueba, pero una pequeña fracción de compuestos también pasa, lo que los convierte en " pseudoprimos ".
A diferencia de los pseudoprimos de Fermat , para los que existen números que son pseudoprimos de todas las bases coprimas (los números de Carmichael ), no hay compuestos que sean pseudoprimos fuertes de todas las bases.
Motivación y primeros ejemplos
Digamos que queremos investigar si n = 31697 es un número primo probable (PRP). Elegimos la base a = 3 e, inspirados en el pequeño teorema de Fermat , calculamos:
Esto muestra que 31697 es un PRP de Fermat (base 3), por lo que podemos sospechar que es primo. Ahora dividimos repetidamente a la mitad el exponente:
El primer par de veces no arrojó nada interesante (el resultado seguía siendo 1 módulo 31697), pero en el exponente 3962 vemos un resultado que no es ni 1 ni menos 1 (es decir, 31696) módulo 31697. Esto prueba que 31697 es de hecho compuesto. Modulo a primo, el residuo 1 no puede tener otras raíces cuadradas que 1 y menos 1. Esto muestra que 31697 no es un pseudoprime fuerte para la base 3.
Para otro ejemplo, elija n = 47197 y calcule de la misma manera:
En este caso, el resultado sigue siendo 1 (mod 47197) hasta que llegamos a un exponente impar. En esta situación, decimos que 47197 es un número primo probable fuerte en base 3. Debido a que resulta que este PRP es de hecho compuesto (se puede ver eligiendo otras bases distintas de 3), tenemos que 47197 es un pseudoprimo fuerte en base 3 .
Finalmente, considere n = 74593 de donde obtenemos:
Aquí llegamos a menos 1 módulo 74593, situación que es perfectamente posible con un primo. Cuando esto ocurre, paramos el cálculo (aunque el exponente aún no es impar) y decimos que 74593 es un número primo probable fuerte (y, como resulta, un pseudoprimo fuerte) en base 3.
Definicion formal
Un número compuesto impar n = d · 2 s + 1 donde d es impar se llama un pseudoprime fuerte (Fermat) a base a si:
o
(Si un número n satisface una de las condiciones anteriores y aún no sabemos si es primo, es más preciso referirse a él como un primo probable fuerte de base a . Pero si sabemos que n no es primo, entonces podemos usar el término pseudoprime fuerte).
La definición se cumple trivialmente si a ≡ ± 1 (mod n ) por lo que estas bases triviales a menudo se excluyen.
Guy da una definición erróneamente con solo la primera condición, que no se satisface con todos los números primos. [1]
Propiedades de los pseudoprimos fuertes
Una pseudoprima fuerte para la base a es siempre una pseudoprima Euler-Jacobi , una pseudoprima Euler [2] y una pseudoprima Fermat para esa base, pero no todas las pseudoprimas Euler y Fermat son pseudoprimas fuertes. Los números de Carmichael pueden ser pseudoprimos fuertes para algunas bases, por ejemplo, 561 es un pseudoprime fuerte para la base 50, pero no para todas las bases.
Un número compuesto n es un pseudoprime fuerte a como máximo una cuarta parte de todas las bases por debajo de n ; [3] [4] por lo tanto, no hay "números fuertes de Carmichael", números que son pseudoprimos fuertes para todas las bases. Por lo tanto, dada una base aleatoria, la probabilidad de que un número sea un pseudoprime fuerte para esa base es menor que 1/4, lo que constituye la base de la prueba de primalidad de Miller-Rabin ampliamente utilizada . La verdadera probabilidad de falla es generalmente mucho menor. Paul Erdos y Carl Pomerance demostraron en 1986 que si un número entero aleatorio n pasa la prueba de primaria de Miller-Rabin a una base aleatoria b, entonces n es casi con seguridad un primo. [5] Por ejemplo, de los primeros 25,000,000,000 enteros positivos, hay 1,091,987,405 enteros que son números primos probables de base 2, pero solo 21,853 de ellos son pseudoprimes, y aún menos de ellos son pseudoprimes fuertes, ya que el último es un subconjunto del anterior. [6] Sin embargo, Arnault [7] da un número de Carmichael de 397 dígitos que es un pseudoprime fuerte para cada base menor que 307. Una forma de reducir la posibilidad de que dicho número se declare incorrectamente como probablemente primo es combinar un primo probable fuerte. prueba con una prueba de primo probable de Lucas , como en la prueba de primalidad de Baillie-PSW .
Hay infinitos pseudoprimos fuertes para cualquier base. [2]
Ejemplos de
Los primeros pseudoprimos fuertes a la base 2 son
- 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... (secuencia A001262 en la OEIS ).
Los primeros en la base 3 son
- 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... ( secuencia A020229 en la OEIS ).
Los primeros en la base 5 son
- 781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (secuencia A020231 en la OEIS ).
Para la base 4, consulte OEIS : A020230 , y para la base 6 a 100, consulte OEIS : A020232 a OEIS : A020326 . Al probar las condiciones anteriores en varias bases, se obtienen pruebas de primordialidad algo más poderosas que si se usa una sola base. Por ejemplo, solo hay 13 números menores que 25 · 10 9 que son pseudoprimos fuertes de las bases 2, 3 y 5 simultáneamente. Se enumeran en la Tabla 7 de. [2] El número más pequeño es 25326001. Esto significa que, si n es menor que 25326001 y n es un primo probable fuerte de las bases 2, 3 y 5, entonces n es primo.
Llevando esto más lejos, 3825123056546413051 es el número más pequeño que es un pseudoprime fuerte a las 9 bases 2, 3, 5, 7, 11, 13, 17, 19 y 23. [8] [9] Entonces, si n es menor que 3825123056546413051 y n es un número primo probable fuerte de estas 9 bases, entonces n es primo.
Mediante una elección juiciosa de bases que no son necesariamente primarias, se pueden construir pruebas aún mejores. Por ejemplo, no hay compuestoque es un pseudoprime fuerte para las siete bases 2, 325, 9375, 28178, 450775, 9780504 y 1795265022. [10]
Pseudoprime fuerte más pequeño a base n
norte | Mínimo SPSP | norte | Mínimo SPSP | norte | Mínimo SPSP | norte | Mínimo SPSP |
1 | 9 | 33 | 545 | sesenta y cinco | 33 | 97 | 49 |
2 | 2047 | 34 | 33 | 66 | sesenta y cinco | 98 | 9 |
3 | 121 | 35 | 9 | 67 | 33 | 99 | 25 |
4 | 341 | 36 | 35 | 68 | 25 | 100 | 9 |
5 | 781 | 37 | 9 | 69 | 35 | 101 | 25 |
6 | 217 | 38 | 39 | 70 | 69 | 102 | 133 |
7 | 25 | 39 | 133 | 71 | 9 | 103 | 51 |
8 | 9 | 40 | 39 | 72 | 85 | 104 | 15 |
9 | 91 | 41 | 21 | 73 | 9 | 105 | 451 |
10 | 9 | 42 | 451 | 74 | 15 | 106 | 15 |
11 | 133 | 43 | 21 | 75 | 91 | 107 | 9 |
12 | 91 | 44 | 9 | 76 | 15 | 108 | 91 |
13 | 85 | 45 | 481 | 77 | 39 | 109 | 9 |
14 | 15 | 46 | 9 | 78 | 77 | 110 | 111 |
15 | 1687 | 47 | sesenta y cinco | 79 | 39 | 111 | 55 |
dieciséis | 15 | 48 | 49 | 80 | 9 | 112 | sesenta y cinco |
17 | 9 | 49 | 25 | 81 | 91 | 113 | 57 |
18 | 25 | 50 | 49 | 82 | 9 | 114 | 115 |
19 | 9 | 51 | 25 | 83 | 21 | 115 | 57 |
20 | 21 | 52 | 51 | 84 | 85 | 116 | 9 |
21 | 221 | 53 | 9 | 85 | 21 | 117 | 49 |
22 | 21 | 54 | 55 | 86 | 85 | 118 | 9 |
23 | 169 | 55 | 9 | 87 | 247 | 119 | 15 |
24 | 25 | 56 | 55 | 88 | 87 | 120 | 91 |
25 | 217 | 57 | 25 | 89 | 9 | 121 | 15 |
26 | 9 | 58 | 57 | 90 | 91 | 122 | sesenta y cinco |
27 | 121 | 59 | 15 | 91 | 9 | 123 | 85 |
28 | 9 | 60 | 481 | 92 | 91 | 124 | 25 |
29 | 15 | 61 | 15 | 93 | 25 | 125 | 9 |
30 | 49 | 62 | 9 | 94 | 93 | 126 | 25 |
31 | 15 | 63 | 529 | 95 | 1891 | 127 | 9 |
32 | 25 | 64 | 9 | 96 | 95 | 128 | 49 |
Referencias
- ^ Guy , Pseudoprimes. Euler Pseudoprimes. Pseudoprimes fuertes. §A12 en Problemas no resueltos en teoría de números , 2ª ed. Nueva York: Springer-Verlag, págs. 27-30, 1994.
- ^ a b c Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff Jr. (julio de 1980). "Los pseudoprimes a 25 · 10 9 " (PDF) . Matemáticas de la Computación . 35 (151): 1003–1026. doi : 10.1090 / S0025-5718-1980-0572872-7 .
- ^ Louis Monier (1980). "Evaluación y comparación de dos algoritmos de prueba de primalidad probabilística eficientes". Informática Teórica . 12 : 97-108. doi : 10.1016 / 0304-3975 (80) 90007-9 .
- ^ Rabin , algoritmo probabilístico para probar la primordialidad. Journal of Number Theory , 12 págs. 128-138, 1980.
- ^ "Primos probables: ¿Qué tan probable?" . Consultado el 23 de octubre de 2020 .
- ^ "El Glosario Prime: probable prime" .
- ^ F. Arnault (agosto de 1995). "Construcción de números de Carmichael que son pseudoprimes fuertes a varias bases". Revista de Computación Simbólica . 20 (2): 151-161. doi : 10.1006 / jsco.1995.1042 .
- ^ Zhenxiang Zhang; Min Tang (2003). "Encontrar pseudoprimes fuertes a varias bases. II" . Matemáticas de la Computación . 72 (244): 2085–2097. doi : 10.1090 / S0025-5718-03-01545-X .
- ^ Jiang, Yupeng; Deng, Yingpu (2012). "Pseudoprimes fuertes a las primeras 9 bases principales". arXiv : 1207.0063v1 [ math.NT ].
- ^ "Registros SPRP" . Consultado el 3 de junio de 2015 .