Pseudoprime fuerte
En teoría de números, un probable primer es un número que pasa un Test de primalidad. A primer probable fuerte es un número que pasa un fuerte versión de un test de primalidad. A pseudoprime fuerte es un número compuesto Eso pasa una versión fuerte de un test de primalidad. Todos los números primos pasan estas pruebas, pero una pequeña fracción de los materiales compuestos también pase, haciéndolos"falsos números primos".
A diferencia de la Pseudoprimes Fermat, para lo cual existen números que son pseudoprimes a todos los coprimos (las bases Números de Carmichael), hay no hay compuestos que son fuertes pseudoprimes a todas las bases.
Contenido
- 1 Definición formal
- 2 Propiedades de pseudoprimes fuertes
- 3 Ejemplos
- 4 Referencias
Definición formal
Formalmente, un número compuesto n = d · 2s + 1 con d siendo raro se llama un fuerte pseudoprime (Fermat) a un relativamente prime base a Cuando posee una de las siguientes condiciones:
or
(If un número n satisface una de las anteriores condiciones y aún no sabe si es cebar, es más preciso referirse a él como un fuerte probable primer a la base a. Pero si sabemos que n No es primordial, entonces uno puede utilizar el pseudoprime fuerte del término).
La definición de un pseudoprime fuerte depende de la base utilizada; las bases diferentes tienen diferentes pseudoprimes fuertes. La definición es conocida trivial si a ≡ ±1 mod n tan a menudo excluyen a estas bases triviales.
Tipo erróneamente da una definición con sólo la primera condición, que no es satisfecha por todos los números primos.[1]
Propiedades de pseudoprimes fuertes
Un fuerte pseudoprime a la base a Siempre es un Pseudoprime de Euler-Jacobi, un Pseudoprime de Euler [2] y un Pseudoprime Fermat pseudoprimes Euler y Fermat esa base, pero no todos son pseudoprimes fuertes. Números de Carmichael puede ser fuertes pseudoprimes a algunas bases — por ejemplo, 561 es un pseudoprime fuerte a base de 50 — pero no a todas las bases.
Un número compuesto n es un pseudoprime fuerte a más de un cuarto de todas las bases más abajo n;[3][4] Así, no hay ningún "fuerte Carmichael números", que son pseudoprimes fuertes a todas las bases. Así dada una base al azar, la probabilidad de que un número es un pseudoprime fuerte a esa base es menos de 1/4, formando la base de los utilizados Test de primalidad Miller-Rabin. Sin embargo, Arnault [5] da un número compuesto 397-dígito que es un pseudoprime fuerte a cada la base de menos de 307. Una manera de evitar que un número tan injustamente se declara probablemente primer consiste en combinar una fuerte prueba privilegiada probable con un Primer probable Lucas la prueba, como en el Test de primalidad Baillie-PSW.
Hay infinitamente muchos pseudoprimes fuertes a cualquier base.[2]
Ejemplos
Son los primeras fuertes pseudoprimes a la base 2
- 2047 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751,... (secuencia A001262 en OEIS).
Son los primeros en base 3
- 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 OEIS).
Son los primeros en base 5
- 781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381,... (secuencia A020231 en OEIS).
Para la base 4, ver 
A020230y para ver base de 6 a 100, A020232 Para A020326.
Analizando las condiciones anteriores a varias bases, uno obtiene pruebas de primalidad algo más potentes que utilizando una sola base. Por ejemplo, sólo hay 13 números menos que 25·109 al mismo tiempo que son pseudoprimes fuertes a las bases de 2, 3 y 5. Se enumeran en la tabla 7 de.[2] El más pequeño tal número es 25326001. Esto significa que, si n es menos de 25326001 y n es que un número primo probable fuerte a bases de 2, 3 y 5, entonces n es principal.
Llevando esto aún más, 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. Ver [6] y.[7] Así que, si n es menos de 3825123056546413051 y n es un número primo probable fuerte a estas 9 bases, entonces n es principal.
Referencias
- ^ Tipo, Pseudoprimes. Pseudoprimes de Euler. Pseudoprimes fuertes. §A12 en Problemas no resueltos de teoría de números2ª ed. Nueva York: Springer-Verlag, pp. 27-30, 1994.
- ^ a b c Carl Pomerance; John L. Selfridge, Samuel S. Wagstaff, Jr. (Julio de 1980). "Los pseudoprimes a 25·109". Matemáticas de cómputo 35 (151): 1003-1026. Doi:10.1090/S0025-5718-1980-0572872-7.
- ^ Monier, Evaluación y comparación de dos algoritmos de prueba de primalidad probabilísticos eficiente. Informática teórica12 págs. 97-108, 1980.
- ^ Rabin, Algoritmo probabilista para prueba de primalidad. Revista de teoría de números12 págs. 128-138, 1980.
- ^ F. Arnault (agosto de 1995). "Números de Carmichael que son Pseudoprimes fuertes a varias Bases de la construcción". Diario de cálculo simbólico 20 (2): 151-161. Doi:10.1006/JSCo.1995.1042.
- ^ Zhenxiang Zhang; Min Tang (2003). "Encontrar fuertes Pseudoprimes a varias Bases. II". Matemáticas de cómputo 72 (244): 2085 – 2097. Doi:10.1090/S0025-5718-03-01545-X.
- ^ Jiang, Yupeng; Deng, Yingpu (2012). "Pseudoprimes fuertes a las primeros 9 bases privilegiadas". arXiv:1207.0063v1[matemáticas.NT].
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||