Portada
mis comunidades
otras secciones
#15:
#6 y #2 así rapidamente, y si no me he equivocado...
Un número de 300.000 dígitos expresados en binario requiere x cifras:
10^300000=2^x
log2(10^300000)=log2(2^x)
x=690775,52 => x = 690776 bits por cada número.
Al ser un procesador casero establecemos el tamaño de la palabra en 690776 bits y obviamos las dificultades de arquitectura que ello conlleva (tamaño de registros de la ALU y buses,etc) supliendo estas carencias con un buen software de programación.
El tamaño de un array por tanto sería el nº de bits de la palabra multiplicado por el número de componentes del mismo. Para la relización del algoritmo en su más puro estilo deberíamos crear una posición de array por cada número posible (Se podría optimizar por ejemplo si obviamos aquellos números pares o divisibles por los primeros N números primos...). Teniendo en cuenta por tanto una implementación pura del algoritmo tendríamos 690776bits por cada número multiplicado por 10^300000 posibles números.
Nuestro array tendría un tamaño de: 6,9*10^300005 bits.
Por otro lado, 1Tb (1024Gb = 1024^2Mb = 1024^3Kb = 1024^4b )se representa mediante 40 bits(2^40)
Por tanto:
6,9*10(300005)/2^40 = nº de Teras
log2(6,9*10(300005)/log2(2^40) = nº de Teras
log2(6,9*10(300005) = 690788,972
6900788,972/40 = 17269 Teras.
Por lo tanto... 17269 Teras = 16.86 Petabits aproximadamente ocuparía el array que necesita la criba de eratóstenes...
Un número de 300.000 dígitos expresados en binario requiere x cifras:
10^300000=2^x
log2(10^300000)=log2(2^x)
x=690775,52 => x = 690776 bits por cada número.
Al ser un procesador casero establecemos el tamaño de la palabra en 690776 bits y obviamos las dificultades de arquitectura que ello conlleva (tamaño de registros de la ALU y buses,etc) supliendo estas carencias con un buen software de programación.
El tamaño de un array por tanto sería el nº de bits de la palabra multiplicado por el número de componentes del mismo. Para la relización del algoritmo en su más puro estilo deberíamos crear una posición de array por cada número posible (Se podría optimizar por ejemplo si obviamos aquellos números pares o divisibles por los primeros N números primos...). Teniendo en cuenta por tanto una implementación pura del algoritmo tendríamos 690776bits por cada número multiplicado por 10^300000 posibles números.
Nuestro array tendría un tamaño de: 6,9*10^300005 bits.
Por otro lado, 1Tb (1024Gb = 1024^2Mb = 1024^3Kb = 1024^4b )se representa mediante 40 bits(2^40)
Por tanto:
6,9*10(300005)/2^40 = nº de Teras
log2(6,9*10(300005)/log2(2^40) = nº de Teras
log2(6,9*10(300005) = 690788,972
6900788,972/40 = 17269 Teras.
Por lo tanto... 17269 Teras = 16.86 Petabits aproximadamente ocuparía el array que necesita la criba de eratóstenes...
Comentarios
Atención ejercicio!! Comprueba mediante la criba de eratóstenes (http://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes) que el primo obtenido efectivamente lo es.
Pregunta: ¿Cuanta RAM se necesita para ejecutar la criba?
#2 Una ayuda, según el artículo fuente en inglés, se necesito testar 625 000 primos potenciales, para ayudar al cálculo
#6 y #2 así rapidamente, y si no me he equivocado...
Un número de 300.000 dígitos expresados en binario requiere x cifras:
10^300000=2^x
log2(10^300000)=log2(2^x)
x=690775,52 => x = 690776 bits por cada número.
Al ser un procesador casero establecemos el tamaño de la palabra en 690776 bits y obviamos las dificultades de arquitectura que ello conlleva (tamaño de registros de la ALU y buses,etc) supliendo estas carencias con un buen software de programación.
El tamaño de un array por tanto sería el nº de bits de la palabra multiplicado por el número de componentes del mismo. Para la relización del algoritmo en su más puro estilo deberíamos crear una posición de array por cada número posible (Se podría optimizar por ejemplo si obviamos aquellos números pares o divisibles por los primeros N números primos...). Teniendo en cuenta por tanto una implementación pura del algoritmo tendríamos 690776bits por cada número multiplicado por 10^300000 posibles números.
Nuestro array tendría un tamaño de: 6,9*10^300005 bits.
Por otro lado, 1Tb (1024Gb = 1024^2Mb = 1024^3Kb = 1024^4b )se representa mediante 40 bits(2^40)
Por tanto:
6,9*10(300005)/2^40 = nº de Teras
log2(6,9*10(300005)/log2(2^40) = nº de Teras
log2(6,9*10(300005) = 690788,972
6900788,972/40 = 17269 Teras.
Por lo tanto... 17269 Teras = 16.86 Petabits aproximadamente ocuparía el array que necesita la criba de eratóstenes...
#15 Con un poco de swap se arregla.
#15 y obviamos las dificultades de arquitectura que ello conlleva
Intentando obviar dificultades.... Error, por favor contacte con el administrador.
#15 deja las fantasmadas tambien, que sabes que nadie se va a leer ese chorizo que has escrito...
#19 te animo a cojer una calculadora y un trozo de papel y un lápiz y goma y tratar de desmontar mi chorizo...
#19 Además de matemáticas le haría falta un poco de educación para la ciudadanía.
#15 yo me llamo Ralph
¿Qué es un número parcialmente primo?
#3 Un número que es hijo de la hermana de tu madre pero no de tu padre.
Gracias a los enlaces de #1, corrijo y completo #3: No son parcialmente primos sino potencialmente primos (tenemos sospechas de que son primos, pero no lo aseguramos).
Abreviadamente 4737*2^985810+1
Exactamente tiene 296763 dígitos... concretamente estos :
Edito. Meneame no está preparado para tanto y trunca el contenido, lo teneis aquí: http://vilinet.communityserver.primegrid.com/primes/?section=decimal&primeid=24914
#13 Pues si tiene 296.763 dígitos en lugar de 300.000, el titular y la noticia cometen un error de exactamente 3237 órdenes de magnitud.
Para comparar, la diferencia entre la menor longitud físicamente razonable (la longitud de Planck) y el diámetro del Universo conocido es de "sólo" 61 órdenes de magnitud: http://www.wolframalpha.com/input/?i=diameter+of+the+observable+universe+%2F+planck+length
En términos puramente cuantitativos, ésta noticia es demostrablemente la más errónea jamás enviada a Menéame.
PD: La he meneado igualmente.
#13 Haberlo puesto en varias líneas separado por puntos aparte que incluyen espacios.
El enlace que das incluye instalar un software para poder leer el archivo. No me parece algo interesante.
#12 No he dicho que uno 100 veces menor sea inseguro, sólo que cuanto más largos son los primos, más seguro es el cifrado. Que pueda llegar a no ser práctico a nivel de seguridad criptográfica, no he dicho nada. De todas formas su utilidad no sólo se limita a la seguridad del cifrado, cuanto más largo es el primo, más largos son los mensajes que se pueden enviar con él, facilitando la comunicación. Evidentemente todo esto ha de ponderarse, muchas veces puede que no resulte práctico utilizar un primo tan grande, pero si te interesa minimizar el número de mensajes cifrados a cruzar, por ejemplo, quizá sí te interese que los primos sean lo más largos posible.
Original en inglés:
http://www.broward.edu/news/Pages/Perretta-Discovers-New-Prime-Number-with-Homemade-Supercomputer-.aspx
No la meneo por tener una errata, habla de 30 millones de dígitos en lugar de los cerca de 300 000.
Link directo al primo en cuestión: http://vilinet.communityserver.primegrid.com/primes/?section=decimal&primeid=24914
vaya, ya han descubierto el pin de mi movil
300.000 dígitos es un poco cacota. En octubre del 2009 se descubrió uno de 12978189 dígitos (sí, casi 13 millones). También cabría mencionar que si bien los primos muy son útiles en criptografía, normalmente lo son si nadie sabe qué primos has utilizado (es lo que tienen las claves privadas). Descubrir un único primo enorme y publicarlo es una buena forma de automáticamente descartar cualquier uso práctico del mismo en algoritmos criptográficos.
Podrían mencionar en el artículo que algoritmo ha usado para comprobar que dicho numeraco es efectivamente primo. Para hacer este tipo de declaraciones hay que usar algoritmos deterministas (que no probabilistas por muchas veces que los uses) que normalmente tienen costes demasiado elevados por mucho paralelismo que introduzcas. ¿Quizás alguna variante del AKS? (http://es.wikipedia.org/wiki/Test_de_primalidad_AKS)
Lo habitual en estos casos es tirar de primos de Mersenne (http://es.wikipedia.org/wiki/N%C3%BAmero_primo_de_Mersenne) ya que existe un test determinista de coste polinómico bastante asumible: el test de Lucas-Lehmer (http://es.wikipedia.org/wiki/Test_de_Lucas-Lehmer). Y cuando digo "bastante asumible" me refiero a cosa de un mes de cálculos por procesador por primo candidato haciendo triquiñuelas tipo transformadas rápidas de Fourier para acelerar calcular el cuadrado de números exageradamente grandes. A eso hay que añadirle que los cálculos deben verificarse independientemente al menos 2 ó 3 veces ya que dada la cantidad y tiempo de las operaciones existen riesgos reales de fallos en el hardware durante la operación (por ejemplo, un bit de la RAM que cambia por picos de tensión o por radiación cósmica). Esto es exactamente lo que hacen en el GIMPS de forma distribuída (Great Internet Mersenne Prime Search: http://www.mersenne.org/).
No me salen las cuentas... 625.000 numeros a 300 o 400 horas cada numero, da 25.000.000 horas (máximo) que en años son 28538, en esa época no existían los ordenadores, bha .. es falso
.
Que manera de perder el tiempo y los recursos... latigazos le daría.
#4 Al contrario que comentar en meneame
#4 Los números primos se usan para cifrar mensajes, cuanto mayor es el primo, más largo es el mensaje que se puede cifrar, y más seguro el cifrado.
#8 Si, mucha seguridad, pero seguro que luego se lo dejan escrito en un postit pegado al monitor
#10 Que estos números sena conocidos no es un problema, es más, para poderlos usar, se han de conocer, el problema está con la seguridad de las claves escogidas (que han de ser respecto a ese primo), pero eso es otra cosa.
#8 usas uno 100 veces mas pequeño y no lo descrubre nadie igualmente... así que déjate de fantasmadas.
#10 tengo una camapaña en este blog para subir el nivel de los chistes, así que... por favor...