Número primo probable
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 232
- 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:
Trackback | 7 Dic, 2006
A dorfunteca » Anotacións da Bitácora » Quick News Flagged Articles
Trackback | 8 Dic, 2006
Aqui - Log
aqui_c | 8 de Diciembre de 2006 | 15:11
Interesante…
Habría que ver cuánto se tarda en probar que un número es primo.
JJ | 9 de Diciembre de 2006 | 2:26
“N no puede ser escrito como un producto”
¿Eso no es ya una condición suficiente de primalidad?
^DiAmOnD^ | 9 de Diciembre de 2006 | 17:06
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?
Naka Cristo | 9 de Diciembre de 2006 | 20:33
Pero eso es lo mismo que decir que no tiene factores menores que 2^32
^DiAmOnD^ | 9 de Diciembre de 2006 | 20:35
Pues también es verdad…Voy a borrar esa condición, no parece independiente de las otras.
Jaume | 11 de Diciembre de 2006 | 18:35
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 contaban un test de primalidad 100% fiable y en un tiempo polinomial. Sinceramente no seguí mucho el tema pero por si hay algún interesado os dejo el articulo.
http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf
Jaume
Trackback | 15 Dic, 2006
labitacora.net » Blog Archives » Tipos de números