En teoría de números un número primo probable (PRP) es un número del que no se sabe si es primo o no pero que satisface una cierta condición específica que también satisfacen todos los números primos.
Algunas de las condiciones que debería cumplir un cierto número N para ser primo probable son:
- N no tiene factores menores que
.
- Debe cumplir el pequeño teorema de Fermat.
- …
La primalidad probable, como casi todo lo que involucra primalidad y números grandes, está relacionada con la criptografía.
Pues desde ayer tenemos un nuevo primo probable que se ha convertido en el primo probable más grande conocido hasta ahora (en PRP Top Records podéis ver una lista con todos los números primos probables conocidos). El número en cuestión es el siguiente:
Su descubridor ha sido Borys Jaworski, conocido por haber descubierto números primos de muchos dígitos.
Este nuevo número primo probable tiene 339.333 dígitos y, como hemos dicho antes, es el número primo probable más grande conocido hasta la fecha. No puede aspirar a ser el número primo más grande conocido hasta la fecha pero no está nada mal.
Vía Microsiervos.
Más información:
Primo Probable en la Wikipedia (inglés)
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
[…] Número primo probable https://gaussianos.com/numero-primo-probable/ […]
Nuevo número primo probable…
En teoría de números, un número primo probable (PRP, en inglés) es un número que no se sabe con certeza que sea probable, pero cumple con una serie de requisitos que los números primos deben satisfacer:
No tiene factores menores que 232
No se lo…
Interesante…
Habría que ver cuánto se tarda en probar que un número es primo.
«N no puede ser escrito como un producto»
¿Eso no es ya una condición suficiente de primalidad?
Uhmmm…cierto. La web de donde lo saqué se decía que no se pudiera escribir trivialmente como un producto. Ahora que lo pienso eso debe referirse a que no sea múltiplo de 2 (es decir, que no sea par), ni de 3 (es decir, que sus cifras no sumen un múltiplo de 3), ni de 5 (es decir, que no acabe ni en 0 ni en 5)…Vamos, que no se pueda escribir como múltiplo de algún número primo pequeño.
¿Qué pensáis?
Pero eso es lo mismo que decir que no tiene factores menores que 2^32
Pues también es verdad…Voy a borrar esa condición, no parece independiente de las otras.
La idea de los primos probables es que comprobar la primalidad es un problema exponencial hablando en terminos de computación. Lo que se hace entonces es disenyar test con ciertas condiciones que deben cumplir los primos pero que ciertos no primos también cumplen. Así consigues obtener candidatos más o menos fuertes en un tiempo prudencial. El pequeño teorema de fermat es un ejemplo sencillo de ello. Si os poneis a buscar encontrareis varios test, cada cual más fiable pero generalmente más costoso. http://es.wikipedia.org/wiki/Test_de_primalidad Por otro lado hace pocos años unos Indios publicaron un articulo (Primes in P) donde creo que… Lee más »
[…] Número primo probable: todo número del cual no se sabe si es primo o no pero que verifica alguna condición que verifican todos los números primos […]