Wagstaff prime

Wagstaff prime

Lleva el nombre de	Samuel S. Wagstaff, Jr.
Año de publicación	1989 [1]
Autor de la publicación	Bateman, PT , Selfridge, JL , Wagstaff Jr., SS
No. de términos conocidos	43
Primeros términos	3 , 11 , 43 , 683
Término más grande conocido	(2 15135397 +1) / 3
Índice OEIS	A000979 Primos de Wagstaff: números primos de forma (2 ^ p + 1) / 3

En teoría de números , un número primo de Wagstaff es un número primo de la forma

${\displaystyle {{2^{p}+1} \over 3}}$

donde p es un primo impar . Los números primos de Wagstaff llevan el nombre del matemático Samuel S. Wagstaff Jr .; las páginas principales dan crédito a François Morain por nombrarlas en una conferencia en la conferencia Eurocrypt de 1990. Los números primos de Wagstaff aparecen en la conjetura de New Mersenne y tienen aplicaciones en criptografía .

Ejemplos de

Los primeros tres números primos de Wagstaff son 3, 11 y 43 porque

${\displaystyle {\begin{aligned}3&={2^{3}+1 \over 3},\\[5pt]11&={2^{5}+1 \over 3},\\[5pt]43&={2^{7}+1 \over 3}.\end{aligned}}}$

Primos Wagstaff conocidos

Los primeros números primos de Wagstaff son:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651,… (secuencia A000979 en la OEIS )

A junio de 2021 ^[actualizar], los exponentes conocidos que producen números primos de Wagstaff o números primos probables son:

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, ^[2] (todos los números primos conocidos de Wagstaff)

117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399,…, 13347311, 13372531, 15135397 (números primos probables de Wagstaff) (secuencia A000978 en la OEIS )

En febrero de 2010, Tony Reix descubrió el probable prime de Wagstaff:

${\displaystyle {\frac {2^{4031399}+1}{3}}}$

que tiene 1.213.572 dígitos y fue el tercer número primo probable más grande jamás encontrado en esta fecha. ^[3]

En septiembre de 2013, Ryan Propper anunció el descubrimiento de dos números primos probables adicionales de Wagstaff: ^[4]

${\displaystyle {\frac {2^{13347311}+1}{3}}}$

y

${\displaystyle {\frac {2^{13372531}+1}{3}}}$

Cada uno es un número primo probable con un poco más de 4 millones de dígitos decimales. Actualmente no se sabe si hay exponentes entre 4031399 y 13347311 que produzcan números primos probables de Wagstaff.

En junio de 2021, Ryan Propper anunció el descubrimiento del probable principal de Wagstaff: ^[5]

${\displaystyle {\frac {2^{15135397}+1}{3}}}$

que es un número primo probable con un poco más de 4.5 millones de dígitos decimales.

Prueba de primordialidad

Se ha probado o refutado la primacía para los valores de p hasta 95369. Aquellos con p > 95369 son números primos probables a partir de agosto de 2021 ^[árbitro]. La prueba de primalidad para p = 42737 fue realizada por François Morain en 2007 con una implementación ECPP distribuida que se ejecuta en varias redes de estaciones de trabajo durante 743 GHz-días en un procesador Opteron . ^[6] Fue la tercera prueba de primalidad más grande realizada por ECPP desde su descubrimiento hasta marzo de 2009. ^[7]

La prueba de Lucas-Lehmer-Riesel se puede utilizar para identificar PRP de Wagstaff. En particular, si p es un exponente de un número primo de Wagstaff, entonces

${\displaystyle 25^{2^{p-1}}\equiv 25{\pmod {2^{p}+1}}}$. ^[8]

Generalizaciones

Es natural considerar ^{[9] de manera} más general números de la forma

${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}$

donde la base . Ya que por extraño que tengamos${\displaystyle b\geq 2}$${\displaystyle n}$

${\displaystyle {\frac {b^{n}+1}{b+1}}={\frac {(-b)^{n}-1}{(-b)-1}}=R_{n}(-b)}$

estos números se denominan "base numérica de Wagstaff " y, a veces, se considera ^[10] un caso de números de repetición con base negativa .${\displaystyle b}$${\displaystyle -b}$

Para algunos valores específicos de , todos (con una posible excepción para los muy pequeños ) son compuestos debido a una factorización "algebraica". Específicamente, si tiene la forma de una potencia perfecta con exponente impar (como 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000, etc. (secuencia A070265 en la OEIS )), entonces el hecho de que , con impar, sea divisible por muestra que es divisible por en estos casos especiales. Otro caso es , con k entero positivo (como 4, 64, 324, 1024, 2500, 5184, etc. (secuencia A141046 en la OEIS )), donde tenemos la factorización aurifeuilleana${\displaystyle b}$${\displaystyle Q(b,n)}$${\displaystyle n}$${\displaystyle b}$${\displaystyle x^{m}+1}$${\displaystyle m}$${\displaystyle x+1}$${\displaystyle Q(a^{m},n)}$${\displaystyle a^{n}+1}$${\displaystyle b=4k^{4}}$.

Sin embargo, cuando no admite una factorización algebraica, se conjetura que un número infinito de valores hacen primos, observe que todos son primos impares.${\displaystyle b}$${\displaystyle n}$${\displaystyle Q(b,n)}$${\displaystyle n}$

Porque , los números primos en sí tienen la siguiente apariencia: 9091, 909091, 909090909090909091, 909090909090909090909090909091,… (secuencia A097209 en la OEIS ), y estos n son: 5, 7, 19, 31, 53, 67, 293, 641, 2137 , 3011, 268207, ... (secuencia A001562 en la OEIS ).${\displaystyle b=10}$

Consulte repunit para obtener la lista de la base de primes generalizados de Wagstaff . (La base de primos de Wagstaff generalizada es una base de primos de repunit generalizada con impar )${\displaystyle b}$${\displaystyle b}$${\displaystyle -b}$${\displaystyle n}$

Mínimos primos p tales que son primos son (comienza con n = 2, 0 si no existe tal p )${\displaystyle Q(n,p)}$

3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ... (secuencia A084742 en el OEIS )

La base b mínima tal que es primo es (comienza con n = 2)${\displaystyle Q(b,prime(n))}$

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (secuencia A103795 en la OEIS )

Referencias

1. Bateman, PT ; Selfridge, JL ; Wagstaff, Jr., SS (1989). "La nueva conjetura de Mersenne". American Mathematical Monthly . 96 : 125-128. doi : 10.2307 / 2323195 . JSTOR  2323195 .
2. "Los veinte primeros: Wagstaff" .
3. "Top records de PRP de Henri y Renaud Lifchitz" . www.primenumbers.net . Consultado el 13 de noviembre de 2021 .
4. Nuevos exponentes de PRP de Wagstaff , mersenneforum.org
5. Anuncio de un nuevo PRP de Wagstaff , mersenneforum.org
6. Comentario de François Morain, The Prime Database: (2 42737  + 1) / 3 en The Prime Pages .
7. Caldwell, Chris, "Los veinte primeros: prueba de primalidad de curva elíptica" , Las páginas principales
8. "Una prueba de primos probables eficiente para números de la forma (2 p  + 1) / 3"
9. Dubner, H. y Granlund, T .: Primes of the Form (b n + 1) / (b + 1) , Journal of Integer Sequences , vol. 3 (2000)
10. Repunit , Wolfram MathWorld (Eric W. Weisstein)

enlaces externos

• John Renze y Eric W. Weisstein . "Wagstaff prime" . MathWorld .
• Chris Caldwell, The Top Twenty: Wagstaff en The Prime Pages .
• Renaud Lifchitz, "Una prueba de primos probables eficiente para números de la forma (2 p  + 1) / 3" .
• Tony Reix, "Tres conjeturas sobre las pruebas de primalidad para los números de Mersenne, Wagstaff y Fermat basadas en ciclos del Digraph bajo x 2  - 2 módulo a primo" .
• Lista de repunciones en base -50 a 50
• Lista de primos Wagstaff base 2 a 160