Pseudoprima fuerte

La versión estable se desprotegió el 5 de agosto de 2022 . Hay cambios no verificados en plantillas o .

Un número primo probable es aquel que pasa la prueba de primalidad . Un primo probable fuerte es un número que pasa la versión fuerte de la prueba de primalidad. Un pseudoprimo fuerte es un número compuesto que pasa la versión fuerte de la prueba de primalidad.

Todos los números primos pasan esta prueba, pero una pequeña proporción de números compuestos también pasan esta prueba, lo que los convierte en " falsos primos ".

A diferencia de los pseudoprimos de Fermat , para los cuales hay números que son pseudoprimos en todas las bases coprimas ( números de Carmichael ), no hay números compuestos que sean pseudoprimos fuertes en todas las bases.

Formal definición

Formalmente, un número compuesto impar n = d • 2 s + 1 con d impar se denomina pseudoprimo fuerte (Fermat) en base a si se cumple una de las siguientes condiciones:

o

para algunos

(Si n satisface las condiciones anteriores y no sabemos si es primo o no, es más exacto llamarlo primo fuerte probable en base a . Si sabemos que n no es primo, podemos usar el término pseudoprimo fuerte. )

La definición es trivial si a ≡ ±1 mod n , por lo que estos casos triviales a menudo se descartan.

Richard Guy dio la definición erróneamente con solo la primera condición, pero no todos los números primos la satisfacen [1] .

Propiedades de los pseudoprimos fuertes

Un pseudoprimo fuerte para la base a es siempre un pseudoprimo de Euler-Jacobi , un pseudoprimo de Euler [2] y un pseudoprimo de Fermat para esa base, pero no todos los pseudoprimos de Euler y Fermat son pseudoprimos fuertes. Los números de Carmichael pueden ser pseudoprimos fuertes en algunas bases, por ejemplo, 561 es pseudoprimo fuerte en base 50, pero no en todas las bases.

El número compuesto n es un pseudoprimo fuerte como máximo para una cuarta parte de todas las bases menores que n [3] [4] . Por lo tanto, no hay "números de Carmichael fuertes", 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 pseudoprimo fuerte en esa base no excede 1/4, que se utiliza en la prueba de Miller-Rabin ampliamente utilizada . Sin embargo, Arnaud [5] ha dado un número compuesto de 397 dígitos que es pseudoprimo fuerte a cualquier base menor que 307. Una forma de evitar declarar tales números como primos probables es combinar la prueba de posible primo fuerte con la prueba de pseudoprimo de Lucas . en la prueba de Bailey-Pomeranz-Selfridge-Wagstaff .

Hay infinitos pseudoprimos fuertes para cualquier base en particular [2] .

Ejemplos

Primeros pseudoprimos fuertes en base 2

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... ( secuencia OEIS A001262 ).

Base 3

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513 , 87913, 88573 . OEIA ).

Base 5

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... ( secuencia OEIS A020231 ).

Para base 4, ver A020230 , y para bases 6 a 100, ver secuencias A020232 a A020326 .

Probar las condiciones anteriores contra bases múltiples da como resultado una prueba de primalidad más poderosa que usar una prueba de base única. Por ejemplo, solo hay 13 números menores que 25•10 9 que son pseudoprimos fuertes en las bases 2, 3 y 5 al mismo tiempo. Se enumeran en la Tabla 7 en Pomerance y Selfridge [2] . El número más pequeño es 25326001. Esto significa que para n menor que 25326001, si n es un número primo fuerte posiblemente en las bases 2, 3 y 5, entonces n es primo.

El número 3825123056546413051 es el número más pequeño que también es pseudoprimo fuerte en 9 bases 2, 3, 5, 7, 11, 13, 17, 19 y 23 [6] [7] . Entonces, para n menor que 3825123056546413051, si n es primo probable fuerte por estas 9 razones, entonces n es primo.

Mediante la elección cuidadosa de una base que no sea prima, se pueden construir pruebas aún mejores. Por ejemplo, no hay números compuestos que sean pseudoprimos fuertes en las siete bases 2, 325, 9375, 28178, 450775, 9780504 y 1795265022 [8] .

El pseudoprimo fuerte más pequeño en base n

norte El menos norte El menos norte El menos norte El menos
una 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
cuatro 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
ocho 9 40 39 72 85 104 quince
9 91 41 21 73 9 105 451
diez 9 42 451 74 quince 106 quince
once 133 43 21 75 91 107 9
12 91 44 9 76 quince 108 91
13 85 45 481 77 39 109 9
catorce quince 46 9 78 77 110 111
quince 1687 47 sesenta y cinco 79 39 111 55
dieciséis quince 48 49 80 9 112 sesenta y cinco
17 9 49 25 81 91 113 57
Dieciocho 25 cincuenta 49 82 9 114 115
19 9 51 25 83 21 115 57
veinte 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 quince
24 25 56 55 88 87 120 91
25 217 57 25 89 9 121 quince
26 9 58 57 90 91 122 sesenta y cinco
27 121 59 quince 91 9 123 85
28 9 60 481 92 91 124 25
29 quince 61 quince 93 25 125 9
treinta 49 62 9 94 93 126 25
31 quince 63 529 95 1891 127 9
32 25 64 9 96 95 128 49

Notas

  1. ↑ Guy, 1994 , pág. 27-30.
  2. ↑ 1 2 3 Pomerance, Selfridge, Wagstaff, 1980 , p. 1003–1026.
  3. ↑ Monier, 1980 , pág. 97-108.
  4. ↑ Rabin, 1980 , pág. 128-138.
  5. ↑ Arnault, 1995 , pág. 151–161.
  6. ↑ Zhang, Tang, 2003 , pág. 2085-2097
  7. ↑ Yupeng Jiang, Yingpu Deng (2012), Strong pseudoprimes to the first 9 primebases, arΧiv : 1207.0063v1 [math.NT]. 
  8. ↑ Registros SPRP . Consultado el 3 de junio de 2015. Archivado desde el original el 11 de octubre de 2015.

Literatura