Contraseñas, números primos y computación cuantica

Contraseñas y números primos

Todos los días introducimos una contraseña para accesar a algún lugar, ya sea nuestro correo, al cajero, la cuenta de la universidad, o cualquier otra cosa.
Las contraseñas son algo fundamental de nuestro día a día.

Un sistema muy usado para el uso de contraseñas se basa en el uso de números grandes y su descomposición en factores de números primos.
Por ejemplo, el número 21 se descompone en los números primos 3 y 7, 3*7 = 21.
La seguridad de estos sistemas radica en el hecho que descomponer un número en factores de números primos no es una tarea sencilla, y para números adecuados y suficientemente grandes es computacionalmente imposible realizar esta descomposición (tardaría unos cuantos trillones de años).

Estos sistemas se basan en usar un número grande como llave pública (al que todos pueden tener acceso), se codifica el mensaje con esta llave publica, y solo se puede descifrar los mensajes si se conoce la factorización en números primos (llave privada) de esta llave publica, de esta manera, se garantiza que los mensajes que usted mande usando la llave publica solo puedan ser leídos por la persona a la que se los manda.

También, si codifica el mensaje usando la llave privada, cualquiera puede decodificarlo usando la llave publica. De esta manera se puede identificar quien es el que envía el mensaje, pues solo él tiene acceso a su llave privada.

Hoy en día su navegador de confianza realiza conexiones seguras realizando un método similar, cuando una página es puesta en su navegador como https:, significa que se ha realizado una conexión segura. Esto quiere decir que esta seguro que se comunica con el banco, y el banco está seguro que se comunica con usted.

llave1 = la llave de su ordenador
llave2 = la llave del banco

Primero su ordenar envía un mensaje al banco, usando su llave1 privada para codificar el mensaje y la llave2 publica del banco.
El banco usa su llave1 publica, para decodificar el mensaje, y su llave2 privada, de esta manera se
asegura que usted es el emisor y que solo el banco puede leer el mensaje.

Posteriormente el banco envía un mensaje usando su llave2 privada para codificar el mensaje y su llave1 publica.
Su ordenador procede a decodificar el mensaje usando la llave2 publica del banco y su llave1 privada, asegurando que el banco es el emisor de dicho mensaje y que solo usted puede leerlo.

Una vez iniciada la conversación segura puede usted mandar su contraseña al banco, sin riesgo a que alguien mas se robe sus datos.

---

---

Computación cuántica y sus repercusiones en seguridad

La computación digital es la computación que realiza su ordenador, basada en bits de información que pueden estar en 2 estados.
En la computación cuántica se utilizan qubits, los cuales pueden estar en estado uno, cero o en cualquier superposición cuántica de estos dos estados.
Esto es, algo puede ser verdadero y falso a la vez en un computador cuántico.

Para no alejarnos mucho del tema en mano, existen algoritmos (secuencias de pasos con un número finito de pasos).
Diseñados para ordenadores cuánticos que pueden resolver rápidamente problemas que las computadoras digitales, tardarían millones de años.
Un problema de este estilo es el reducir un número en factores de números primos.
El algoritmo de Shor corre en O(log n), esto quiere decir que un computador cuántico lo suficientemente poderoso podría romper su contraseña en poco tiempo.
Con lo que el mundo podría cambiar como lo conocemos.

Por suerte los computadores cuánticos aun están lejos de ser funcionales, debido a poca memoria solo pueden factorizar números como 15 = 3*5.


Para los DBA's existe el algoritmo de Grover, que es capaz de buscar una entrada en una base de datos no ordenada en tiempo O( n^1/2 ). Esto es un decremento cuadrático en los tiempos de corrida.

The ligth bulb stall-ion o la gallina de las bombillas de oro.

La obsolencia programada es una herramienta diseñada por los fabricantes de productos para que, después de cierto tiempo (un poco después de expirar la garantía) tu producto deje de funcionar.
De esta manera debes comprar uno nuevo, lo que les permite seguir ganando dinero.

Hoy en día se ha desarrollado un foco que gasta un 68% menos de electricidad que los "focos ahorradores" y cuyo costo de fabricación es mas bajo.
Esto quiere decir que existen focos que son mas baratos de comprar, duran mas tiempo y gastan menos. ¿Por qué no están enroscados estos focos a todas nuestras tomas?
La respuesta es sencilla, el inventor de estos focos no puede encontrar quien le de fondos para desarrollarlo, no existe ninguna firma que quiera sacar al mercado estos focos, lo único que este inventor ha recibido son amenazas de muerte.
La razón de este comportamiento por parte de los dueños del dinero es sencilla, al durar estos focos para toda la vida, no habría necesidad de comprarlos de forma regular, y no tendrían un flujo de dinero de forma constante a sus bolsillos.

Vivimos en una época de tirar y comprar, inducida por las grandes corporaciones como una forma de ganar mas dinero.
En los tiempos de nuestros abuelos la mentalidad era de reparar lo roto, el problema es que de esa forma, el dinero que se gasta en reparar el producto no entra a los bolsillos de los grandes empresarios, si no que va a los de las personas que tienen su taller de reparación.
En resumen, reparar tus productos crea empleos y ayuda a una repartición mas equitativa de la riqueza. Mientras que la mentalidad en la que nos están induciendo a crecer es una en la que el dinero solo llega a unas cuantas personas.

 

Todas las imágenes hechas por mi en MS paint

Siéntanse con la libertad de usarlas como gusten

Y pueden decir que ustedes la hicieron, la vdd 

a mi me daría pena, pero como quieran.

Fuente:
http://energiaslibres.wordpress.com/2012/04/12/ya-han-amenazado-de-muerte-al-espanol-que-invento-la-bombilla-que-apenas-gasta-y-dura-toda-la-vida/

Teorema de los monos infinitos.

El teorema de los monos infinitos dice:

    Un mono pulsando teclas al azar sobre un teclado durante un periodo de tiempo infinito casi seguramente podrá escribir finalmente cualquier libro que se halle en la Biblioteca Nacional Francesa.

Que básicamente dice que si intentas mucho algo que puede pasar (aunque sea muy difícil que pase) muy probable mente lograras tu cometido.



El otro día en la clase de diseño y análisis de algoritmos (impartida en linea gratis por la universidad de stanford Link al curso), el programa de tarea consistía en implementar el algoritmo de Karger, para el problema de corte mínimo.


En esencia para el problema de corte mínimo se tiene un grafo G = ( V, E ), en el cual se traza una linea que separe el grafo en 2 subconjuntos, cada subconjunto no debe ser vació. Y la solución a este problema es encontrar una linea que separe al grafo en 2 subconjuntos y exista el menor número de vértices que vallan de los nodos de un subconjunto a los nodos del otro.


En la imagen se muestra un grafo con nodos A, B, C y D, en la primera imagen se divide el grafo en en los 2 subconjuntos {B}  y {A, C, D}, a esto le llamamos un corte, y como existen 2 vértices que unen al subconjunto 1 con el subconjunto 2, decimos que es un corte de orden 2, los vértices en este caso serían los unen a A con B, y a  C con B.

La tercera imagen muestra otro corte para este mismo grafo. En este caso, los 2 subconjuntos generados son {D} y {A, B, C}, este corte es de orden 1, y debido a que es el menor número de cortes que se pueden realizar, se dice que es un corte mínimo.

Hay que notar que no se permite realizar cortes en que existan subconjuntos vacíos y que un grafo puede tener mas de un corte mínimo.

La cuestión con este algoritmo es que es un algoritmo probabilistico, esto es, no necesaria mente llega a la solución mínima, pero dado un número suficiente de corridas llega a la solución correcta.

Esto ya es una aplicación del teorema de los monos infinitos, hay que correr este algoritmo varias veces para poder (casi seguramente) llegar a una solución.

El problema con el que me encontré fue que tenía un bug muy escurridizo que ocasionaba que a veces el programa crasheara,
debido a que tenía poco tiempo para dedicarle al programa decidí aplicar nuevamente el teorema de los monos infinitos.

Como el programa no crasheaba siempre, y de las veces que no crasheaba a veces llegaba a una solución correcta (pues así funciona el algoritmo).
Solo puse un try catch, que en realidad solo evitaba que el programa crasheara.
Poner a correr esta programa un número de veces los suficiente mente grande me dio la solución correcta, y gracias a una buena implementación y que
el tamaño de la instancia era pequeño, en realidad no tardaba nada en terminar.

Anexo el código hecho en java, nunca tuve tiempo de corregir el bug, pero funciona casi perfectamente =p.
http://pastebin.com/FGh9H4LL
y la info del problema esta aquí:
http://pastebin.com/R1uJHHu3

---

Otra aplicación del teorema de los monos infinitos se da en las personas que hablan mucho, si dices un chingo de cosas, alguna de ellas tendrá sentido.
Claro eso no quiere decir que sea agradable escuchar todas la basura que sale por tu boca.

---

Karger's algorithm

El algoritmo de karger se basa en realizar contracciones de los nodos del grafo, cada paso del algoritmo se contraen 2 nodos reduciendo el número de nodos en 1. El algoritmo termina cuando el número de nodos es 2, y el valor del corte es el número de vértices que unen a los 2 nodos.

Se agregan dibujillos hechos por mi para mayor claridad. En este grafo, primero se contrajeron los nodos A y C, y posteriormente se contrajeron los nodos {A, C} y D, como el número de nodos en este punto es 2, el algoritmo termina, reportando un corte con valor de 2.

Contraer nodos A y C

Grafo resultante de la contracción de A y C

Contraer nodo {A, C} y D

Grafo final, con un corte de 2

Suponga que en la tercera imagen, en lugar de contraer los nodos {A, C} con el nodo D, se contrajeran los nodos {A, C} con el nodo B. En este caso también terminaria el algoritmo al tener solo 2 nodos, pero ahora tenemos un corte con valor de 1.

Lo único adicional que hay que mencionar es que el algoritmo de Karger realiza la elección de que nodos unir de forma aleatoria con base al número de vértices que tiene cada nodo. Entre mas vértices tenga un nodo, mas probable es que este sea elegido. Suponga que queremos encontrar un corte mínimo dado, donde sabemos que el nodo A se encuentra en un subconjunto que se crea por el corte, y el nodo B se encuentra en el otro subconjunto.
Si en algún momento el algoritmo de Karger realiza una contracción del nodo A y B, estos dos nodos terminaran en un mismo subconjunto al terminar el algoritmo. Esto quiere decir que al terminar, no encontramos el corte mínimo en el que A y B terminan en subconjuntos diferentes.

Una idea intuitiva del porque de este algoritmo es que, un corte mínimo es aquel que separa al grafo en 2 subconjuntos en los que el número de vértices que los unen es el menor posible. Este algoritmo elegirá contraer con mayor probabilidad aquellos nodos que tengan un alto número de vértices, esto lleva a que aquellos vértices que tengan un alto número de vértices acaben en el mismo subconjunto.
Lo que con suerte, quiere decir que tendremos un corte mínimo.

La forma de las cosas.

Ya en tiempos antiguos sabemos que la tierra es "redonda", pero, ¿por qué tiene la tierra esta forma de esfera?

Todo es debido a la gravedad, una piedra pequeña que podamos sostener en nuestras manos tiene una masa muy pequeña, esto causa que su fuerza de atracción (i.e. gravedad) sea muy pequeña, lo que le permite tener formas muy diversas.
Recordara la famosa ley de la gravitación universal (ya sabe el de la manzana (no, no el de mac))

Esta formula, nos dice que entre mayor masa tenga uno de los cuerpos, mayor fuerza existirá entre ellos.

Lo contrario de la pequeña piedrita en términos de masa, sería una estrella. Una estrella es el segundo objeto con mayor masa en el universo, tiene tanta masa que si no fuera por el calor que se produce en la estrella, esta se comprimiría tanto que formaría un hoyo negro.

La tierra se encuentra en un nivel intermedio, teniendo una masa que crea una fuerza de gravedad que jala a la masa de la tierra hacía el centro, como esta fuerza es lo suficiente mente grande (9.8m/s^2) como para jalar a la masa hacía el centro de la tierra.
Por ejemplo, la luna, que tiene una gravedad menor a la de la tierra, igual tiene una forma esférica, la diferencia principal radica en que la luna tiene montañas que son de mucho mayor tamaño que la de mayor tamaño en la tierra. Si en la tierra existieran montañas del tamaño de las montañas de la luna, están serían derribadas por la fuerza de gravedad de la tierra.

Construyeron tan alto que su ambición derrumbo sus aspiraciones.

Cursos Stanford

Para aquellos que no sepan la universidad de Stanford imparte cursos a travez de internet de forma gratutita. Los cursos tienen duración de entre 5 y 7 semanas dependiendo el curso.
El formato de los cursos es impartir clases a travez de videos, se genera un conjunto de videos cada semana con el material para esa semana, ademas se deja tarea en base a los videos de la semana.
Generalmente los cursos son autocontenidos, refiriendoce al hecho de que no ocuparas una fuente de información externa para llegar a buen camino en el curso.
También se crean grupos de estudio por si existen cosas que no quedaron claras.

Al finalizar, si lograste tener una calificación aprovatoria se otorga un reconocimiento por parte de la universidad (no valido para nada que no sea presumir).

Les dejo la liga al directorio de materias:

https://www.coursera.org/


Las que a mi me llaman la atención son:


https://www.coursera.org/course/ml

El cual es un curso de Machine Learning o Aprendizaje Maquina, con aplicaciones como enseñar a un auto a conducir de forma automatica, reconocimiento de imagenes, tecnología anti-spam y mucho mas.


https://www.coursera.org/course/compilers

Este curso enseñara como un programa escrito en un lenguaje de alto nivel, es traducido a un programa escrito en bajo nivel, esto mas que nada por curiosidad.


https://www.coursera.org/course/intrologic

Introducción a logica es justo lo que su nombre dice, como hacer que tu cerebro realice pasos sistematicamente como un robot, pero con la creatividad de la mente humana.

Al espacio y mas alla.

Me gustaría tener un pequeño espejo que me permitiera ver hacía el futuro de la humanidad, tengo curiosidad si algun dia "el hombre llegara a las estrellas", o si nos quedaremos encerrados en la tierra hasta la inanición.

El problema con el viaje interestelar radica en el hecho de que las estrellas estan demasiado lejos proxima centauri, la estrella mas cercana esta a 4.2420 años luz de distancia, esto es, si viajaramos a la velocidad de la luz, tardariamos 4.2420 años en llegar a ella.

Con las velocidades de las naves modernas se tardaría mas de la vida de un hombre en llegar a estas.
Se tendría que tener una tripulación que tenga hijos dentro de la nave, que tenga otros hijos y así hasta llegar al destino. La otra alternativa es mantener a la tripulación en estado de criopreservación y que la nave sea conducida de forma automatica por un computador.

Suponga que hoy en dia enviamos una nave a colonizar un nuevo planeta, tardaría algo como unos 50,000 años.

Si, 100 años despues se envia una nave, que gracias a los avances de la tecnología nos permite llegar en 30,000 años, y lanzamos esa nave, tendremos que la nave moderna abra llegado antes que la nave que lanzamos hoy en dia.

Podríamos tener guerras interestelares donde las naves de guerra lleguen muchos años despues de que el conflicto se haya arreglado debido a que se invento una nave mas veloz con la que se llegaron a terminos de paz con el otro planeta.

En fin, estaba diviertiendome con un pequeño juego Kerval Space Program.
En este juego tomas el rol de la NASA para construir un cohete sin limite de presupuesto, y 3 pequeños astronautas caen en tus manos para tripular la nave fuera de la orbita de la tierra, y con suerte, a la luna!

Fotografiando las estrellas.

Durante el día no podemos ver las estrellas, pues la luz del sol opaca la luz de las estrellas.

Fotografía de un cielo de ciudad con un
tiempo de exposición de 5 segundos.

Durante la noche, en la ciudad podemos ver unas cuantas estrellas, debido a que la luz de los coches, edificios y lamparas publicas opacan a las estrellas, además de la capa de smog que las cubre.
Si nos alejamos un poco de la ciudad, podemos ver aun mas estrellas, y si tenemos la fortuna de salir al espacio, podremos ver aun mas estrellas.

Las estrellas no aparecen de la nada, siempre han estado ahí (o mejor dicho, estuvieron, pues la luz de las estrellas que vemos tiene millones de años), lo único es que hay mucho "ruido" que no nos permite ver la luz que nos mandan.


Como sabrán entre mas tiempo esta una fotografía expuesta a una luz mas brillante se hace esta, pues durante mas tiempo pasa luz a través del lente hacía la fotografía.
Si tomamos una foto de un lugar durante 1 segundo y otra durante 5 segundos, podrá notar que la fotografía tomada durante 5 segundos es mucho mas brillante que la fotografía con menor tiempo de exposición.

Luego una técnica que se usaba en la antigüedad, para poder fotografías aquellas estrellas que no eran visibles a simple vista era exponer la fotografía a la luz de la estrella durante un periodo prolongado de tiempo.
Se montaba un telescopio con una serie de engranajes que permitían que el lente girara lentamente en el sentido contrario de la rotación de la tierra, lo que permitía que el telescopio siempre estuviera enfocado en el mismo lugar del cielo.
De esta manera se exponía una fotografía durante todo un día, o incluso mas, a la luz de una estrella que ha simple vista resultaba invisible, logrando una fotografía de esta.

Fotografía del mismo cielo de ciudad con un
tiempo de exposición de 60 segundos

Como hacer fotos de fantasmas.

Seguro todos han visto fotos de fantasmas, en donde se ve una persona y detrás, en un reflejo o escondido en una esquina se ve la forma de un fantasma.
Realizar este tipo de fotografias es bastante sencillo y la mayoria de las camaras modernas deberían ser capaces de hacer esto.

Foto de mi traslucido, 15 segundos de tiempo de exposición,
7 segundos en la foto y 8 sin aparecer.

Necesitaremos una camara que nos permita abrir el lente durante un tiempo largo 5-10segundos, tener 2 personas, y un lugar con iluminación baja ,opcional un paisaje con aspecto tetrico para mas ambiente.
Digamos que nuestra camara nos permite abrir el lente durante 10segundos, durante los primeros 5 segundos, las dos personas posaran ante la camara sin moverse. Pasado este tiempo, la persona que pasara como fantasma debe retirarse de la foto, y listo, tendremos una foto con un fantasma.

Como funciona:
Entre mas tiempo permanece el lente de una camara abierta mas luz pasa atravez de este, como una de las personas permanece todo el tiempo en la misma posición, la imagen que se captura de esta persona permanece igual, mientras que la otra persona solo esta la mitad del tiempo en la foto, lo que hace que la camara capture 5segundos de su imagen, mientras los otros 5segundos captura lo que estaba detras de él.


Imagina que la camara toma una foto cada segundo, y la imagen final la consigue al mezclar las 10 imagenes que ha tomado, como una persona aparecen en las 10 fotos, su imagen permanece constante. Mientras que la imagen de la otra persona es una mezcla de las 5 fotos en las que sale él y las 5 en las que sale lo que había detras de él, consiguiendo un efecto fantasmagórico.

Para modificar el tiempo de apertura del lente o velocidad del obturador, busca en el manual de tu cámara para ver como poder modificar estos valores, un valor muy alto (varios segundos) permiten este efecto.
En la siguiente liga se habla de como modificar estos valores para cámaras modelo Nikon y Canon.
link

Jugando con un foco para efectos agregados.

La diagonal de Cantor

La demostración que mas me ha gustado es la de la diagonal de Cantor.
Esta se usa para probar que dado un conjunto de 2 o mas caracteres, el conjunto que se forma al crear todas las series infinitas con estos caracteres es infinita no numerable.
Un ejemplo, suponga que nuestro conjunto de caracteres tiene los elementos A y B.
Algunos elementos del conjunto de series infinitas sería:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
BBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
y así, este conjunto es claramente infinito, la pregunta es como demostrar que es infinito no-numerable.

Y como muchas demostraciones recurrimos a demostrarlo por contradicción. Esto es, suponer lo contrario de lo que queremos demostrar, i.e., que esta serie es infinito numerable.
El que la serie sea infinito numerable quiere decir que "podemos ordenarla" de alguna forma poder decir cual es el primer elemento, cual el segundo, y así para todos los elementos.

Como suponemos que el conjunto es infinito numerable, esto quiere decir que existe dicho ordenamiento magico en el que estan todos los elementos del conjunto.
Como ilustración suponga que el siguiente es dicho ordenamiento
AAAAAAAAAAAAAAAAAAAAA...
ABAAAAAAAAAAAAAAAAAAA...
AABAAAAAAAAAAAAAAAAAA...
.
.
.

La demostración de la diagonal de cantor se basa en crear una nueva serie que no se encuentre en el ordenamiento. Para crear esta serie hacemos lo siguiente. Tomar el primer elemento de la primera serie
osea, de la serie AAAAAAAAAAAAAA..., tomamos la primera letra A y la cambiamos por una B.
Hasta el momento nuestra nueva seríe es B
De la segunda serie hay que tomar la segunda letra (ABAAAAAA....) tomamos la B, y la cambiamos por A.
Ahora nuestra nueva seríe sera BA.
De la tercera serie (AABAAAA...) tomamos el tercer elemento B y lo cambiamos por una A.
Ahora nuestra seríe sera BAA.
Proseguimos de esa manera hasta tener una seríe en el que cada elemento tendra un elemento diferente de todas las series en nuestro ordenamiento (el primer elemento de la seríe que creamos difiere con el primer elemento de la primera seríe, pues tomamos el elemento de esa serie y lo cambiamos. Y esto ocurre para todas las demas series).
Esto quiere decir que la serie que hemos creado es diferente a todas las series del ordenamiento, lo que quiere decir que nuestra serie no esta en el ordenamiento, pero claramente nuestra seríe es un elemento del conjunto de series infinitas con los caracteres A y B pues así la construimos.
Esto implica que hemos creado un elemento perteneciente al conjunto que no se encuentra en nuestro ordenamiento magico. Pero se supone que el ordenamiento debe tener a todos los elementos del conjunto de series infinitas. Esto es una contradicción del hecho que existe dicho ordenamiento.
Por lo cual nuestra suposición inicial (que el conjunto es infinito numerable) es incorrecta, y como solo existen 2 posibilidades (infinito numerable o no-numerable) eso implica que el conjunto es infinito no-numerable.