289 meneos
3978 clics

Desarrollan un método que mejora la forma de encontrar números primos (eng)

El matemático peruano Harald Helfgott, quien ya resolviera en 2013 la conjetura débil de Goldbach, lo ha conseguido desarrollando una versión modificada de la Criba de Erastótenes.
etiquetas: criba de erastótenes, matemáticas, primos
124 165 0 K 638 actualidad
#39   #1 La criba de Eratóstenes es mucho más potente si se hace uso junto con la espiral de Ulam.

De esta manera puedes descartar 4 de cada 6 números sin necesidad de cálculo alguno y sobre esto, aplicar la criba de Eratóstanes haciendo saltos del orden 2n y 4n...

Pero qué os voy a contar que no sepáis...

P.D.: #0 En la entradilla pone Erastotenes.
votos: 7    karma: 59
 *   LoLaista LoLaista
#60   #10 Supongo que lo que ocurre es que cuando vas a leer lo comentarios a muchos usuarios les (nos) gusta encontrar comentarios como el de #39 o #42 que aporten algo de conocimiento.
votos: 2    karma: 19
#42   #1 La búsqueda de números primos hace mucho que no se hace por cribas de Eratóstenes. Se buscan candidatos y se aplican test de primalidad
es.wikipedia.org/wiki/Test_de_primalidad
Lo complicado es conseguir candidatos que no sean primos de Merssenne o de Fermat. Pero como hay un teorema sobre la distribución logarítmica de los primos se va encontrando.
votos: 4    karma: 22
#68   #42 Depende. No es lo mismo buscar un número primo concreto que hallar todos los primos menores que un número dado. Para el segundo caso, la criba de Eratóstenes sigue siendo un método muy utilizado.
votos: 0    karma: 15
#71   #68 Bueno, tanto como muy utilizado... Hay listas de primos hasta números muy altos, y a partir de cierta cantidad de cifras el proceso consume mucho tiempo. La búsqueda de primos para criptografía no suele ser modo exahustivo. Y es la aplicación principal.
votos: 0    karma: 10
#73   #71 Eso es porque en la criptografía basta con encontrar números primos altos, no se necesita una lista exhaustiva (si te saltas unos cuantos, no pasa nada).
votos: 1    karma: 22
 *   maria1988
#75   #73 Ya, pero es la razón principal para buscar primos.
votos: 0    karma: 10
#83   #71 pero... ¿podría acelarar algoritmos de cracking por fuerza bruta?

quizás la pregunta en si misma es un poco bruta... no tengo muchos conocimientos en criptografia! :-)
votos: 0    karma: 6
#84   #83 No creo que este algoritmo ponga en peligro el RSA
votos: 0    karma: 10
#96   #68 Si vas a hacer una criba, quizás sea más fácil aplicar el test de primalidad, y sobre lo que quede, comprobar si efectivamente son primos o no. A mi me parece que esto es una no-noticia, quizás culpa de la mala prensa, pero por lo poco que dice es que se filtran los números a comprobar, pero eso ya podemos hacerlo y de forma muy eficiente.
votos: 0    karma: 7
#2   Ahora vamos a por los números cuñados :shit:
votos: 31    karma: 121
#10   #3 ¿que tiene de malo hacer bromas en cualquier tipo de noticia? cuando se hacen en noticias de desgracias MAL porque el humor negro no está bien visto, cuando se hace en envios con motivos religiosos MAL porque ofenden el sentimiento de su fe, y ahora tampoco en noticias cientificas...

A todos los idiotas les molesta u ofende algo.
votos: 15    karma: 26
#11   #10 Tontos solemnes.
votos: 5    karma: 45
#14   #10 te estás ofendiendo? :troll:
votos: 3    karma: 36
#35   #14 no, pero parece que mi comentario si que ha ofendido a 3 meneantes, o quizas como se reconocian como idiotas se han visto en la obligación de ofenderse
votos: 5    karma: 19
#46   #35 Ofenderse en meneame es como enamorarse en un puticlub
votos: 5    karma: 38
#64   #46 Es decir, a todos no pasa alguna vez(?). :troll: xD
votos: 0    karma: 7
#70   #46 Yo diría "ofenderse en internet"...
votos: 1    karma: 14
#50   #10 Además en Menéame solo hay cuatro tipo de usuarios:
1º) Los que vienen a dejar bromitas.
2º) Los que vienen a leer bromitas.
3º) Los que no saben contar.
votos: 5    karma: 35
#69   #50 Yo soy de los cuatro
votos: 3    karma: 27
#59   #10 Las bromas no tienen nada de malo. Lo malo es entrar a una noticia y que ningún comentario aporte nada, ni siquiera gracia. Es el chiste fácil de idiotas.
votos: 0    karma: 8
#61   #10 No se queja de que un usuario haga una broma, se queja de que el 90% de comentarios al final son bromas y eso indica un poco el nivel de contenido (en Meneame los comentarios una parte muy importante del contenido de la página).

Es como si me dices que vas a ver Gran Hermano, yo no voy a criticar que tu lo veas, pero si me puede parecer criticable que sea de los programas que más audiencia tienen en TV.
votos: 0    karma: 7
#53   #3 xD xD xD xD xD xD xD xD xD
votos: 1    karma: 28
#57   #3 Entrar a llamar a otro karmawhore para luego no hacer ni un solo comentario sobre la noticia también es muy karmawhore :roll:
votos: 2    karma: 32
#79   #78 Y tú podrías ser más original y no repetir lo ya dicho.. goto #57 :-P
votos: 0    karma: 13
#78   #3 Te podrías aplicar ese enlace perfectamente.
votos: 0    karma: 9
#25   #2 Como curiosidad, la palabra "primo" proviene de una traducción errónea de "prime number" cuya traducción correcta sería "número principal", "primordial", "original". Yo los hubiera traducido como números primarios.
votos: 6    karma: 59
 *   Ganimedes Ganimedes
#32   #25 Falso, por poner un ejemplo toma "opera prima"
De la propia RAE:

primo, ma
Del lat. primus.
1. adj. primero.
20. f. desus. Superioridad, excelencia o ventaja sobre otros de su clase.
votos: 9    karma: 73
#33   #25 siendo esto de buscar primos más viejo que el mear, dudo mucho que la palabra primo venga del inglés y no del griego (proto) pasando por el latín (primus), que es como tradicionalmente llegaban al castellano las palabras cultas. Simplemente la palabra "primo", en castellano, ha perdido el significado primigenio ;)
votos: 2    karma: 20
#38   #25 Muchos cultismos del inglés también vienen del latín al igual que sucede con el español.
votos: 0    karma: 6
#45   #25 Lo dudo muchísimo. La principal acepción de "primo" es primero (de hecho la relación de parentesco viene de consobrinus primus). A los números primos se les denominaba de esa forma porque eran los primeros en los que se dividían los números impares. Isidoro de Sevilla en el s. VII los definía así:

El número impar, por su parte, se subdivide en primo o simple, segundo o compuesto, y tercero o intermedio. El intermedio en un sentido es primo y simple; en cambio, en otro sentido, es segundo y compuesto.
votos: 3    karma: 37
#4   Es sencillo. Te pones a hacer el timo de la estampida y los primos vienen sin tener que llamarlos.
votos: 5    karma: 34
#12   #4 o un partido político... :roll:
votos: 0    karma: 16
 *   robustiano robustiano
#5   ¿Y por qué no viene un enlace al paper?
votos: 4    karma: 48
#7   #5 helfgott@math.univ-paris-diderot.fr
votos: 5    karma: 63
#51   #7 Igual no es la mejor idea copiar y pegar textualmente una cuenta de correo en un foro público... Es muy fácil para un bot meterlo en una lista de spam
votos: 1    karma: 19
#54   #51 Buenas tardes desde 2016.
votos: 0    karma: 7
#55   #54 Holaaaaaa :hug: :hug: :hug: :hug: :hug:
votos: 1    karma: 13
#6   Aquí en España hay muchos números primos, todos los de la seguridad social de aquellos primos que nos levantamos cada mañana y estamos currando un huevo de horas para mantener a tanto parásito y gandul
votos: 9    karma: -20
 *   Capricarpio Capricarpio
#16   #6 Alguien no tomó su All Bran esta mañana.
votos: 3    karma: 13
vet vet
#56   #16 ¿ No te has tomado la medicación verdad ?, pues anda, ya estás tardando...
votos: 4    karma: -25
#74   #56

Querido Capricarpio:

Hoy sí me he tomado mi medicación, como me la tomo todos los días a riesgo de perder mi vida si no lo hago. Soy trasplantado renal y tomo unos nueve comprimidos diarios. Si no lo hago, mi propio sistema inmunitario destruirá el órgano trasplantado y entraré en un fallo renal. Eso implicaría que. tras una agonía de unos pocos meses, fallecería sin remedio. Podría alargarse a unos pocos años con un tratamiento de diálisis pero el resultado sería a la larga el mismo.…   » ver todo el comentario
votos: 2    karma: 27
 *   vet vet
#76   #74 Meada fuera de tiesto... así se llama a tu comentario.

¿O crees realmente que se refería a esa medicación?
votos: 1    karma: -4
#77   #76 Sé perfectamente a qué se refería, pero me apetecía darle un ZAS a esa persona que va por ahí faltando al respeto a los demás.

Lo tuyo sí que es meada fuera del tiesto.
votos: 3    karma: 37
vet vet
#80   #74 Ante todo siento lo que te ocurre, pero me parece que te has pasado 34 pueblos, y creo que poco o nada tiene que ver tu comentario con lo de los primos, yo me siento un 'primo' por estar todo el día trabajando, quema y bastante y me siento un primo con tanto desgraciado viviendo a costa nuestra (por ejemplo hay 350 que están tocándose las narices ahora mismo sin hacer nada y viviendo del cuento) y me siento un primo luchando día a día para sacar mi trabajo adelante y comentarios como el…   » ver todo el comentario
votos: 1    karma: -4
#85   #80
Eres un quejica y un despreciable. ¿Qué trabajas mucho? Yo también.



Buenos días.
votos: 1    karma: 9
 *   vet vet
#86   #85 ¿ Quién coño te ha dicho que no pago impuestos ? y muchos, por cierto, lo de mierdecilla será tu puta madre
votos: 3    karma: -19
#87   #86 Tú eres el que empezaste insultando y encima no sabes leer.
votos: 0    karma: 11
vet vet
#88   #87 No he insultado mas que cuando a mi me han insultado, además he estado aguantando sarcasmos y gilipolleces por un estúpido comentario, me paso el día trabajando como un cabrón para encima cuando me tomo un pequeño descanso y leo algo y pongo un comentario tener que aguantar esta mierda.
votos: 1    karma: -4
#89   #88 Mira, y trabajo unas once horas al días y no le vengo a decir a nadie que se vaya a tomar sus pastillas. A mi también me da rabia la gente que no da golpe y cobra.
votos: 0    karma: 11
 *   vet vet
#90   #89 Hombre yo trabajo trabajo más o menos eso y ese comentario lo puse porque antes me molestó un comentario que pusieron
votos: 0    karma: 7
#91   #90 Oye, ¿nos pedimos disculpas mutuas y nos dejamos de estupideces?
votos: 1    karma: 17
vet vet
#92   #91 Oye, que yo no tengo nada contra tí, simplemente me sentí molesto por un comentario, es más, cuando leí la noticia me senti como un primo, trabajando para mantener a tanta gente que no se lo gana
votos: 0    karma: 7
#93   #92 Bueno, pues mis disculpas las tienes y yo te perdono a ti. A veces nos calentamos y pasan estas cosas.
votos: 1    karma: 17
vet vet
#94   #93 Me disculpo también si en algo te ofendí
votos: 2    karma: 24
#8   @Heimish No vayas de serio ahora, que tu también sueltas tus buenas gilipolleces en posts de ciencia www.meneame.net/c/18954847 :-D
votos: 3    karma: 47
 *   MKitus MKitus
votos: 6    karma: 61
 *   xa.bi xa.bi
#15   #9 Ya se vio que ese sistema no es eficiente en absoluto para números grandes. Parte de un número candidato en notación "unaria", esto es un 6 se representaría como seis unos: "111111". La expresión regular lo que hace es buscar patrones de cadenas que se repiten dentro de ella, por ejemplo "2 veces 111". Si los encuentra, es que el número no es primo. Para números muy grandes, esta estrategia es inabordable.
votos: 6    karma: 66
#17   #15 se me olvidó el [IRONIC]
Soy perfectamente consciente de las limitaciones de esa expresión regular.
votos: 1    karma: 15
 *   xa.bi xa.bi
#18   #17 Eso dicen todos. ;)
votos: 5    karma: 49
#19   #18 Bueno ... llevo programando ordenadores desde principios de los 80 y profesionalmente desde mediados de los 90, ya me veo capacitado para bromear con estas cosas :-)
votos: 1    karma: 17
 *   xa.bi xa.bi
#20   #19 Yo perforaba tarjetas de arcilla en Babilonia. Con las uñas, porque todavía no se había inventado el palo con punta.
votos: 11    karma: 80
#21   #20 :q!
votos: 4    karma: 36
#13   Un crack este Helfgott, los surprimos ésos se deben estar haciendo caquita... :-P
votos: 3    karma: 52
#22   joder, un puto genio
votos: 1    karma: 23
#23   Una vez intenté un programita con el excel y cascó. El método de probar todos los candidatos desde 2 hasta n-1 desde luego no era el más eficiente...
votos: 2    karma: 18
#26   #23 Hasta la raiz cuadrada de n hubiese sido suficiente.
votos: 0    karma: 12
#27   #26 ah. Pues no tenía ni idea. ¿hasta el redondeo por debajo de la raíz?
votos: 0    karma: 8
#29   #27 Sí. Si un número a es igual al producto de b * c, podemos asegurar que uno de ellos es menor o igual que la raíz cuadrada de a, y el otro es mayor o igual que la raíz cuadrada de a. Si lo que quieres ver es si a es primo, basta con que compruebes si es divisible por un número menor que su raíz cuadrada.
votos: 4    karma: 41
#37   #29 Hazme un hijo.
votos: 1    karma: 18
#43   #37 xD Y yo pensando en la carrera que el cáculo no me iba a servir para nada
votos: 1    karma: 15
#49   #29 Buena explicación.
Me recuerda a un problema que me salio el otro día en Brilliant: "Two prime numbers sum to 86479. What is their positive difference?"
votos: 1    karma: 15
#72   #49 86477

¿Dónde está mi premio?
votos: 0    karma: 7
#97   #72 Yo no descubrí la solución, pero luego entendí la respuesta. ¿Podrías explicar cómo has llegado a ese resultado?
Por cierto, el bueno es 86475 (la diferencia) ;)
votos: 0    karma: 8
 *   uzefli uzefli
#98   #97 Pues sí, me lié, hice la diferencia entre 86479 y 2... no entre 86477 y 2.

Obviamente los primos son 86477 y 2 ya que al decir que 86479 es la suma de dos primos y ser impar sólo puede deberse a que uno de ellos es par, y sólo hay un número par y primo, el 2.
votos: 2    karma: 18
#66   #29 Solo por trolear. 30 = 30*1; 30 > raiz(30) Te falta añadir premisas. :troll:
votos: 0    karma: 7
#95   #66 No, está bien.
votos: 0    karma: 8
#65   #27 No tan elaborado ni eficiente, pero quizás más intuitivo, es que puedes comprobar solo hasta la mitad. Seguramente igual hubiera cascado. xD
votos: 0    karma: 7
#24   Dado que muchos algoritmos criptográficos se basan en el producto de números primos muy grandes, ¿qué implicaciones tiene este avance matemático en el campo de la criptografía? ¿Puede dar lugar a cifrados más seguros o por el contrario puede ayudar a romper los cifrados actuales? Pregunto desde la casi completa ignorancia. :-)
votos: 5    karma: 44
#30   #24 esto estaba pensando yo, a mi no me da buena espina
votos: 2    karma: 27
#31   #24 Bueno de entrada el algoritmo no hace mas rapida la factorización, que es lo que podría hacer mas vulnerables muchos algoritmos de cifrado, así que aparentemente no creo que cambie el panorama en ese aspecto
votos: 4    karma: 42
#28   Yoestoy leyendo un libro sobre los numeros primos que esta muy interesante, lo recomiendo para los curiosos de las matemáticas como yo. www.casadellibro.com/libro-el-misterio-de-los-numeros-primos/978848298
votos: 0    karma: 6
#34   ¿Qué claves criptograficas va a poner en mas riesgo?

Si antes para tal clave de caracteristicas r y longitud de clave k , se necesitaban A dias para romperla en un cluster determinado. En ese mismo cluster con la misma clave y el nuevo metodo ¿Cuantos dias se necesitan?
Nuevo tiempo B = Ax
¿Cuanto es x?
votos: 0    karma: 13
#41   #36, no hay mucho que entender, habla de ese algoritmo y de que lo ha mejorado, pero no explican el método.
votos: 0    karma: 18
#67   #36 Interesantísimo aporte. Gracias.
votos: 0    karma: 12
#40   #0, ¿por qué no has enviado la versión en castellano de la noticia que da la misma página?

www.scientificamerican.com/espanol/noticias/matematico-peruano-mejora-

Y no, no es que en la página hagan una traducción automática, porque en la versión en castellano he visto alguna falta de ortografía que un traductor no habría cometido :-P
votos: 0    karma: 18
#44   Harald Helffgott -> peruano

Haroldo Huancapaza Chuquimamani -> ¿escandinavo?
votos: 1    karma: 19
#63   #44 Apropiación cultural. :troll:
votos: 0    karma: 7
#47   Si los números tienden a enchufarse unos a otros en cuanto tienen oportunidad es que son primos o cuñados.
votos: 0    karma: 7
#48   Yo la verdad es que últimamente no dormía bien pensando en esto, esta noche seguro que descanso mejor. :shit:
votos: 1    karma: 20
#52   Las conjeturas siempre me han llamado la atención.
votos: 0    karma: 6
#58   Por lo visto el método desarrollado es de tipo genealógico :troll:
votos: 0    karma: 11
#62   No sé si sea un efecto de mala prensa, pero no me parece muy relevante como noticia. Por una parte, no dice nada sobre como funciona, y por otra habla de sus aplicaciones pero tampoco menciona ninguna.

Así que es una noticia sobre que alguien ha descubierto algo nuevo, que no sabemos qué es ni qué aplicación tiene, en un campo que tiene un alto interés en la actualidad.
votos: 0    karma: 7
 *   Arth
#81   Aaaay primoooo! Qué bien lo vamos a celebrar con la fregoneta a toodo gasss. Primoooo qué rebien!
votos: 0    karma: 9
comentarios cerrados

menéame