por
pobrecito hablador
el Viernes, 12 Diciembre de 2003, 00:47h
(#243637)
Solo lo vamos a entender gente que estudiemos esos temas, todos esos de ESI y FP que dicen que saben más que nosotros y que damos lo mismo dudo que ni siquiera sepan por qué es una potencia de dos con un menos uno. Qué cosas tiene Fermat.
Hay bastantes más de uno... (se CREE que infinitos... pero es una conjetura)
En general, un Primo de Mersenne es un Número de Mersenne primo. Y un Número de Mersenne es un entero de la forma 2^{n}-1.
A partir de todo esto hay rios de tinta... empezando por que para que 2^{n}-1 sea primo, "n" ha de ser él mismo primo. Esto da una serie de "ventajas" para la obtención de primos ENORMES (empezando claramente por descartar todos los exponentes no primos).
Para quien quiera mas informacion, aquí [wolfram.com]
Para demostrar esta afirmación razonemos por reducción al absurdo.
Supongamos que existe solamente un número finito de primos. Sea C = { p1, p2, ... pn } el conjunto formado por todos ellos. Consideremos ahora el número M=p1xp2x ... pn+1. Como cada primo pi es mayor que 1, M es un número mayor que cualquiera de los pi; es decir, M no está en el conjunto C y por tanto es compuesto. Admitirá entonces una descomposición como producto de factores primos (por el teorema fundamental de la aritmética). Por hipótesis, estos factores sólo pueden estar entre los primos que aparecen en el conjunto C. Por tanto, existirá un primo q del conjunto C, tal que q|M y obviamente, q|p1xp2x ... pn. Por consiguiente, q divide a la diferencia M - p1xp2x ... pn (que es 1). Pero ningún número primo divide a 1, y q es un número primo que divide a 1 (Contradicción). Concluimos entonces que el conjunto de los números primos no puede ser finito.
Estamos razonado "por el absurdo": suponemos lo contrario de algo y tratamos de llegar a una contradicción (si el razonamiento ha sido correcto, solo puede ser porque lo que hemos supuesto al principio esta mal).
Asi pues, vamos a imaginar que NO hay infinitos números primos. Tenemos solo N (por ej, pongamos que tenemos cinco -> 2,3,5,7,11)
Ahora nos sacamos de la manga otro número que llamaremos M (y eso se hace porque sí, porque nos APETECE: en realidad es porque no olemos que pasara si metemos el dedo por ahi... usando un poco de "picardia" y un mucho de practica) que es el producto de todos estos primos mas 1 (en nuestro ejemplo concreto, (2*3*5*7*11)+1= 2310+1 = 2311). Como hemos multiplicado números todos ellos mayores que 1, tenemos que el resultado es seguro mayor que el mayor de los factores. O sea, que nos hemos "salido por arriba" de nuestro conjunto de primos. (esto se ve claramente con el 2311). La razon de porque le sumamos 1 viene luego (y en cualquier caso no hace mas que reafirmar el que tenemos un número aun mayor). Si el número no esta en esa coleccion de primos que hemos SUPUESTO que son LOS UNICOS PRIMOS QUE HAY, es porque es compuesto. Si es compuesto se desmuestra (teorema fundamental de la aritmetica) que puede descomponerse en producto de primos. Pues supongamos que uno de esos primos que "forman parte" de M es 'q' (es un primo, asi que tiene que estar en ese conjunto inicial FINITO que hemos considerado).
Entonces esta claro que la división M/q es un número entero. Tambien esta claro que 'q' divide al producto de todos los primos (es mas, él es uno de ellos!!).
(ignorar esto si no se entiende)
Asi pues, ambos forman parte de la misma "clase de equivalencia" son congruentes modulo 'q'
(/ignorar)
Si lo anterior no se entiende, hagase acto de fé y creaseme si digo que dos numero son congruentes módulo 'q' siempre que si los restamos y dividimos por 'q' sale un numero entero.
Asi que M - "producto de todos los primos" = 1 (Y ESTA ES LA RAZON DE SUMAR +1 A M AL PRINCIPIO!!).
Y aqui tenemos la CONTRADICCION, ya que NINGUN número primo (y por tanto mayor que 1) divide a 1. (recuerdo que 'q' deberia dividir a 1 porque acabamos de decir que forman parte de la misma "clase de equivalencia" y por tanto su resta ha de ser divisible por 'q')
De esto se deduce que el conjunto de los numeros primos no puede ser finito. (ya que si lo fuera, lo anterior no chocaria contra ese contrasentido...).
Espero haber aclarado algo a quien no este de manejar estas cosas. Y que no se me tiren al cuello demasiados puristas ;)
A veces merece la pena sacrificar un poco de "notacion" por claridad.
El solo pensar en cuanto espacio ocupará un archivo de texto con ese número, cuanto tiempo se llevaría mi máquina en calcularlo, cuantas canciones cabrían en ese espacio y en ese mismo tiempo cuantos archivos puedo bajar en mldonkey, me causa pereza.
Re:Primos
de kiwnix
(Puntos:1)
Viernes, 12 Diciembre de 2003, 01:44h
por
pobrecito hablador
el Viernes, 12 Diciembre de 2003, 02:26h
(#243655)
veréis que la EFF da 100.000$ al primero que le salga en la pantallita un primo de 10 millones de dígitos.
¡Justo lo que esperaba! ¿Dónde hay que apuntarse? Que te den 100.000$ sólo por eso no está nada mal... Claro que lo peor es que, de lograrse, tienes una probabilidad entre n de que te "toque" justo a ti (n=número de participantes en el proyecto)... Y, bueno, seguramente esos 100.000$ equivaldrán por aquel entonces a 10$ de hoy... Pero bueno, tampoco es para preocuparse demasiado, ya estaremos todos muertos. En fin, casi que no me apunto. Será mejor emplear los ciclos sobrantes de mi ordenador en algo que SEGURO (mayúsculas=ironía) que da sus frutos, como el proyecto SETI@home.
Re:jeje
de pobrecito hablador
(Puntos:0)
Viernes, 12 Diciembre de 2003, 19:36h
por
pobrecito hablador
el Viernes, 12 Diciembre de 2003, 04:31h
(#243664)
bueno pues eso si leeis bien las bases si tienes
la tremenda suerte de ser tu quien lo encuentre
no te llevaras los $100.000 si no que se descuentan
una buena parte para el proyecto otra para no se que y otra para no se cuanto y te quedas con menos de
la mitad a eso luego tienes que restarle los impuestos que seria cuanto ¿los impuestos para premios son del 40%? jaja
vamos al final aun vas a tener que tener que poner tu pasta ... XDD
Bueno al final con suerte de todos modos te quedarias unos 10k-15k que no esta mal tampoco no?
Seguro que en alguno de esos primos está escondida la letra de alguna de las canciones de David Buscaminas. ¿No habrá que pagar a la SGAE por descubrir nuevos primos? :?
.
--
NoP/Compiler
Re:SGAE
de zarshisha
(Puntos:2)
Viernes, 12 Diciembre de 2003, 12:51h
Re:SGAE
de pezezin
(Puntos:1)
Sábado, 13 Diciembre de 2003, 00:24h
La primera aplicación que me viene a la cabeza al hablar de numeros primos (grandes) es la criptografía
Cuanto más grande sea el número, más "intratable" será el problema, por lo que una información cifrada, tardará más tiempo en ser descifrada (por fuerza bruta). Pero, ¿que pasaría si para realizar el ataque, utilizo una capacidad de procesado _MUY_ superior a la que se supone disponible? 211.000 Usuarios actualmete, y funcionando desde el 96, es una capacidad muy alta, sin duda, pero nos olvidamos de un detalle, ¿quien asegura que quien va a realizar el ataque, utilice los mismos medios?
Revisando la hemeroteca [barrapunto.com], vemos que una empresa ha desarrollado un procesador 1000 veces más rápido que los actuales (según la Ley de Moore, es una avance de aprox. 15 años). Dentro de los comentarios, se habla de una utilidad práctica [barrapunto.com] :'(
A continuación copio un parrafo (pag. 25) del libro "Criptografía y seguridad en computadores" (libro _MUY_ recomendable, por cierto)de Manuel Lucena [ujaen.es]
Los algoritmos criptográficos emplean claves con un elevado número de bits, y usualmente
se mide su calidad por la cantidad de esfuerzo que se necesita para romperlos. El tipo de
ataque más simple es la fuerza bruta, que simplemente trata de ir probando una a una todas
las claves. Por ejemplo, el algoritmo DES tiene 256 posibles claves. ¿Cuánto tiempo nos llevaría
probarlas todas si, pongamos por caso, dispusiéramos de un computador capaz de hacer un
millón de operaciones por segundo? Tardaríamos. . . ¡más de 2200 años! Pero ¿y si la clave del ejemplo anterior tuviera 128 bits? El tiempo requerido sería de 1024 años.
Ahora dejo una pregunta para alguien que sepa del tema más que yo, ¿de que tamaño deberían ser las claves de un algoritmo de llave publica/privada, para tener la misma seguridad?
--
Los marrones se crean pero no se destruyen, solo se acumulan
¿Si?
de Lock
(Puntos:1)
Viernes, 12 Diciembre de 2003, 12:16h
por
pobrecito hablador
el Viernes, 12 Diciembre de 2003, 10:56h
(#243730)
Vean, vean:
Rato dice que el 19% del sueldo da para una casa
El ministro de Economía, Rodrigo Rato, afirmó ayer que el esfuerzo que supone para un joven solo comprar una vivienda asciende al 26% de su sueldo, y que se reduce al 19% si lo adquiere en pareja.
Rato citó datos del Observatorio Joven de la Vivienda del Consejo de la Juventud. Sin embargo, los datos aportados no son ciertos. En realidad, según el Observatorio, un joven necesita el 56,8% de su renta para comprar un piso y una pareja el 34,7%. El ministro señaló que el nivel de esfuerzo es bajo 'gracias a las políticas de Gobierno'.
Y volverán a ganar las erecciones, vereís, si es que somos unos primos. Ya lo dice el proverbio: no hay primo mas grande que un obrero de derechas.
De verdad, no es coña. Lo hice en HP Test Drive [hp.com] (concretamente la máquina SPE174) utilizando mi código Glucas [sourceforge.net] con dos hilos, no llegué a utilizar los cuatro procesadores Itanium-II.
Podeis ver los detalles de la verificación
aquí [oxixares.com]
Y os puedo decir que disfruté viendo el resultado de la prueba. Después de 20996009 iteraciones y 11 días de cálculo que todo salga bien.
Saludos.
¡Andaaaa!
(Puntos:0, FueraDeTema)Por favor, aprovecha bien los ciclos muertos de tu procesador. [stanford.edu].
Solo para Ingenieros y Matemáticos
(Puntos:-1, Provocacion)No es EL primo de Mersenne
(Puntos:2, Informativo)En general, un Primo de Mersenne es un Número de Mersenne primo. Y un Número de Mersenne es un entero de la forma 2^{n}-1.
A partir de todo esto hay rios de tinta... empezando por que para que 2^{n}-1 sea primo, "n" ha de ser él mismo primo. Esto da una serie de "ventajas" para la obtención de primos ENORMES (empezando claramente por descartar todos los exponentes no primos).
Para quien quiera mas informacion, aquí [wolfram.com]
Re:No es EL primo de Mersenne
(Puntos:4, Informativo)( Última bitácora: Sábado, 25 Febrero de 2006, 21:57h )
Para demostrar esta afirmación razonemos por reducción al absurdo.
Supongamos que existe solamente un número finito de primos. Sea C = { p1, p2, ... pn } el conjunto formado por todos ellos. Consideremos ahora el número M=p1xp2x ... pn+1. Como cada primo pi es mayor que 1, M es un número mayor que cualquiera de los pi; es decir, M no está en el conjunto C y por tanto es compuesto. Admitirá entonces una descomposición como producto de factores primos (por el teorema fundamental de la aritmética). Por hipótesis, estos factores sólo pueden estar entre los primos que aparecen en el conjunto C. Por tanto, existirá un primo q del conjunto C, tal que q|M y obviamente, q|p1xp2x ... pn. Por consiguiente, q divide a la diferencia M - p1xp2x ... pn (que es 1). Pero ningún número primo divide a 1, y q es un número primo que divide a 1 (Contradicción). Concluimos entonces que el conjunto de los números primos no puede ser finito.
No olvides lo importante que eres para mí.
Re:No es tan informativo...
(Puntos:4, Informativo)Estamos razonado "por el absurdo": suponemos lo contrario de algo y tratamos de llegar a una contradicción (si el razonamiento ha sido correcto, solo puede ser porque lo que hemos supuesto al principio esta mal).
Asi pues, vamos a imaginar que NO hay infinitos números primos. Tenemos solo N (por ej, pongamos que tenemos cinco -> 2,3,5,7,11)
Ahora nos sacamos de la manga otro número que llamaremos M (y eso se hace porque sí, porque nos APETECE: en realidad es porque no olemos que pasara si metemos el dedo por ahi... usando un poco de "picardia" y un mucho de practica) que es el producto de todos estos primos mas 1 (en nuestro ejemplo concreto, (2*3*5*7*11)+1= 2310+1 = 2311). Como hemos multiplicado números todos ellos mayores que 1, tenemos que el resultado es seguro mayor que el mayor de los factores. O sea, que nos hemos "salido por arriba" de nuestro conjunto de primos. (esto se ve claramente con el 2311). La razon de porque le sumamos 1 viene luego (y en cualquier caso no hace mas que reafirmar el que tenemos un número aun mayor). Si el número no esta en esa coleccion de primos que hemos SUPUESTO que son LOS UNICOS PRIMOS QUE HAY, es porque es compuesto. Si es compuesto se desmuestra (teorema fundamental de la aritmetica) que puede descomponerse en producto de primos. Pues supongamos que uno de esos primos que "forman parte" de M es 'q' (es un primo, asi que tiene que estar en ese conjunto inicial FINITO que hemos considerado).
Entonces esta claro que la división M/q es un número entero. Tambien esta claro que 'q' divide al producto de todos los primos (es mas, él es uno de ellos!!).
(ignorar esto si no se entiende)
Asi pues, ambos forman parte de la misma "clase de equivalencia" son congruentes modulo 'q'
(/ignorar)
Si lo anterior no se entiende, hagase acto de fé y creaseme si digo que dos numero son congruentes módulo 'q' siempre que si los restamos y dividimos por 'q' sale un numero entero.
Asi que M - "producto de todos los primos" = 1 (Y ESTA ES LA RAZON DE SUMAR +1 A M AL PRINCIPIO!!).
Y aqui tenemos la CONTRADICCION, ya que NINGUN número primo (y por tanto mayor que 1) divide a 1. (recuerdo que 'q' deberia dividir a 1 porque acabamos de decir que forman parte de la misma "clase de equivalencia" y por tanto su resta ha de ser divisible por 'q')
De esto se deduce que el conjunto de los numeros primos no puede ser finito. (ya que si lo fuera, lo anterior no chocaria contra ese contrasentido...).
Espero haber aclarado algo a quien no este de manejar estas cosas. Y que no se me tiren al cuello demasiados puristas ;)
A veces merece la pena sacrificar un poco de "notacion" por claridad.
Bye
Primos
(Puntos:1)jeje
(Puntos:0)¡Justo lo que esperaba! ¿Dónde hay que apuntarse? Que te den 100.000$ sólo por eso no está nada mal... Claro que lo peor es que, de lograrse, tienes una probabilidad entre n de que te "toque" justo a ti (n=número de participantes en el proyecto)... Y, bueno, seguramente esos 100.000$ equivaldrán por aquel entonces a 10$ de hoy... Pero bueno, tampoco es para preocuparse demasiado, ya estaremos todos muertos. En fin, casi que no me apunto. Será mejor emplear los ciclos sobrantes de mi ordenador en algo que SEGURO (mayúsculas=ironía) que da sus frutos, como el proyecto SETI@home.
el premio tiene truco
(Puntos:1, Informativo)Más info
(Puntos:1)( http://barrapunto.com/~fernand0/bitacora | Última bitácora: Miércoles, 11 Febrero de 2009, 15:45h )
--
Fernand0
Si elegimos a los políticos es para no tener que pensar todo el tiempo.
Homer Simpson
yo prefiero buscar a la prima
(Puntos:2, Divertido)( http://nachoproy.wordpress.com/ | Última bitácora: Jueves, 02 Marzo de 2006, 15:44h )
Empty your mind. Be formless, shapeless. Like freedom. You put GNU/Linux into a bottle and it becomes the bottle. You pu
SGAE
(Puntos:3, Divertido)( http://www.sromero.org/ )
Seguro que en alguno de esos primos está escondida la letra de alguna de las canciones de David Buscaminas. ¿No habrá que pagar a la SGAE por descubrir nuevos primos? :?
.
NoP/Compiler
Seguro que nos será de utilidad?
(Puntos:3, Interesante)( http://barrapunto.com/ | Última bitácora: Viernes, 13 Febrero de 2004, 14:50h )
La primera aplicación que me viene a la cabeza al hablar de numeros primos (grandes) es la criptografía
Cuanto más grande sea el número, más "intratable" será el problema, por lo que una información cifrada, tardará más tiempo en ser descifrada (por fuerza bruta). Pero, ¿que pasaría si para realizar el ataque, utilizo una capacidad de procesado _MUY_ superior a la que se supone disponible? 211.000 Usuarios actualmete, y funcionando desde el 96, es una capacidad muy alta, sin duda, pero nos olvidamos de un detalle, ¿quien asegura que quien va a realizar el ataque, utilice los mismos medios?
Revisando la hemeroteca [barrapunto.com], vemos que una empresa ha desarrollado un procesador 1000 veces más rápido que los actuales (según la Ley de Moore, es una avance de aprox. 15 años). Dentro de los comentarios, se habla de una utilidad práctica [barrapunto.com] :'(
A continuación copio un parrafo (pag. 25) del libro "Criptografía y seguridad en computadores" (libro _MUY_ recomendable, por cierto)de Manuel Lucena [ujaen.es]
Los algoritmos criptográficos emplean claves con un elevado número de bits, y usualmente se mide su calidad por la cantidad de esfuerzo que se necesita para romperlos. El tipo de ataque más simple es la fuerza bruta, que simplemente trata de ir probando una a una todas las claves. Por ejemplo, el algoritmo DES tiene 256 posibles claves. ¿Cuánto tiempo nos llevaría probarlas todas si, pongamos por caso, dispusiéramos de un computador capaz de hacer un millón de operaciones por segundo? Tardaríamos. . . ¡más de 2200 años! Pero ¿y si la clave del ejemplo anterior tuviera 128 bits? El tiempo requerido sería de 1024 años.
Ahora dejo una pregunta para alguien que sepa del tema más que yo, ¿de que tamaño deberían ser las claves de un algoritmo de llave publica/privada, para tener la misma seguridad?
Los marrones se crean pero no se destruyen, solo se acumulan
El premio flaco
(Puntos:2)( http://barrapunto.com/ | Última bitácora: Lunes, 31 Enero de 2005, 17:01h )
"veréis que la EFF da 100.000$ al primero que le salga en la pantallita un primo de 10 millones de dígitos."
De todas formas en mi pequeña pantalla no cabe.
El mayor primo conocido es el españolito de a pié
(Puntos:2, Divertido)Rato dice que el 19% del sueldo da para una casa
El ministro de Economía, Rodrigo Rato, afirmó ayer que el esfuerzo que supone para un joven solo comprar una vivienda asciende al 26% de su sueldo, y que se reduce al 19% si lo adquiere en pareja.
Rato citó datos del Observatorio Joven de la Vivienda del Consejo de la Juventud. Sin embargo, los datos aportados no son ciertos. En realidad, según el Observatorio, un joven necesita el 56,8% de su renta para comprar un piso y una pareja el 34,7%. El ministro señaló que el nivel de esfuerzo es bajo 'gracias a las políticas de Gobierno'.
Y volverán a ganar las erecciones, vereís, si es que somos unos primos. Ya lo dice el proverbio: no hay primo mas grande que un obrero de derechas.
Entonces has ganado los 100.000$
(Puntos:4, Inspirado)Pues yo he sido el encargado de verificarlo...
(Puntos:2, Informativo)Podeis ver los detalles de la verificación aquí [oxixares.com]
Y os puedo decir que disfruté viendo el resultado de la prueba. Después de 20996009 iteraciones y 11 días de cálculo que todo salga bien.
Saludos.
El primo más grande...
(Puntos:1)( http://barrapunto.com/ | Última bitácora: Miércoles, 29 Noviembre de 2006, 23:34h )
Sin duda el de Zumosol.
Hay que ser primo para andar buscando a un primo más grande que el de Zumosol.
¿Qué tiene esta bola que a todo el mundo le mola?
yo creo
(Puntos:0)Primates buscando primos...
(Puntos:0)