Calculando RSA con una regla

4 * 5
Esta historia se me puede hacer un poco larga...
Hace un tiempo, tenuki, me conto que se podia multiplicar usando rectas.
El asunto es asi (hice dibujitos):
Supongamos que quiero multiplicar 4 * 5 (señorita señorita, esa la se!). Lo primero que tenemos que hacer es trazar un segmento de tamaño 5, que empieza en el punto 1@0, y llega hasta el punto 1@5 (segmento azul). Despues trazamos una recta, que pasa por el punto 0@0, y por el punto 1@5 (recta roja). Finalmente, a baño maria, hacemos un segmento de tamaño 4, sobre el eje de las x, y que salga del punto 0@0 (segmento verde). Cuando unimos el segmento verde con la recta roja (a travez del segmento amarillo), encontramos dos puntos. El que esta sobre la recta roja (4@20) nos da en su coordenada y el valor que estabamos buscando (y si.. 20).
El metodo parece piola, y la explicacion es simple. Cuando trazamos la recta roja, en realidad, estamos trazando una recta que tiene como ecuacion y = 5 * x. Luego hacemos el segmento verde, y nos encontramos con que x = 4. Entonces y = 5 * 4 = 20. Lo mismo que queriamos, pero expresado obtenido de una manera distinta.
La pregunta seria que tiene esto que ver con RSA. Para eso necesitamos poder elevar un numero a una potencia (elevar es multiplicar un numero por si mismo n veces).
Eso tambien lo podemos hacer con regla, y para eso usamos mapas iterativos.

3 ^ 5
Receta para calcular 3 ^ 5 (4 porciones):
Primero le cambiamos el nombre a los ejes, el eje X ahora se llama x(t) y el eje Y ahora se llama x(t+1). Despues trazamos dos rectas que salen desde el origen 0@0. La primer recta es una recta de 45 grados (recta verde). La segunda recta (recta roja) es una recta de pendiente 3 (si estubiesemos elevando 17 ^ n, la recta seria de pendiente 17).
Partiendo del punto 1@1 (que esta en la recta verde), trazamos una recta paralela al eje x(t+1), hasta encontrar a la recta roja (esto va a ocurrir en el punto 1@3). Maravillosamente encontramos el valor de 3 ^ 1. Luego trazamos una recta horizontal hasta volver a encontrar la recta verde, y subimos hasta la recta roja, ahora el punto va a ser el 3@9 (jua, 3 ^ 2 !!). Si hacemos esto 3 veces mas, nos vamos a encontrar con el punto 81@243 (y 243 es 3^5 !!). Esto significa que aprendimos a potenciar con regla!
Yo me pregunte por que esto funcionaba... Bueno, parte de la respuesta es que cuando trazabamos la recta de pendiente 3, podiamos escribir esta ecuacion en diferencias:
x(t+1) = 3 * x(t) que es la ecuacion de la recta roja.
La solucion a esta ecuacion en diferencias es: x(t) = C(3^t) donde C es alguna constante que depende del punto inicial (en nuestro caso, y para el bien de todos nosotros, es 1).
Asi que esto funcionaba :)
Ahora nada mas nos falta solucionar un problema: el modulo
El ejemplo anterior lo vamos a cambiar un poco, vamos a calcular 3 ^ 6 % 251 (esto se lee: 3 a la sexta modulo 251). Al grafico anterior, trazamos una recta horizontal para x(t+1) = 251.
Ahora, cuando elevamos un numero, seguimos los mismos paso que antes, pero si, cuando estamos trazando la recta vertical, encontramos la recta azul en vez de la roja, cambiamos un poco el asunto. En ese caso, trazamos una recta paralela a la recta roja, y que pase por este punto (por el punto donde nos encontramos con la recta azul). Seguimos esta nueva recta hasta que x(t+1) = 0 (es decir, hasta el eje x(t)), y volvemos a seguir los pasos anteriores (con la precaucion de que podemos volver a encontrarnos la recta azul).
Asi vemos como en el ejemplo (3 ^ 6 % 251), nos encontramos dos veces con la recta azul antes de encontrar a la recta roja en el punto que estavamos buscando (227/3@227) donde 227 es el resultado que buscabamos.
3^6 % 251
Finalmente me queda pendiente algo interesante para pensar, que es la existencia de atractores. Un atractor en este caso seria algun conjunto de dibujos que sean iguales. Lo interesante es que una vez que se toca un punto de la recta roja mas de una vez, sabemos que estamos en presencia de un atractor, es decir, vamos a estar un dibujo que ya habiamos hecho. Hay un pequeño teorema que garantiza la presencia de atractores, si se cumplen algunas situaciones, pero el numero al que tenemos que elevar es un numero muy alto. Seria piola achicar ese numero.

Mas on Random (no-tan) Walk

Siguiendo con el processo del articulo pasado, un amigo, felipe, me sugirio que trate de probar el mismo proceso, variando los parametros, pero usando siempre los mismos numeros aleatorios. La idea de la prueba esta es: Si con un parametro igual a 2, en un determinado momento t habia un movimiento hacia arriba, con parametro igual a 3, en el mismo momento, tendria que existir el mismo movimiento (en la misma direccion), pero con el cambio propio que le da el processo.
El cambio fue simple (que grande squeak), y en el momento del cambio, me di cuenta de algo interesante. Yo estaba usando variables aleatorias con distribuccion Normal, y lo unico que hacia era cambiar el desvio de las variables x(t) dependiendo de la variable y(t-1). Aca hay que recordar que si queremos cambiar el desvio podemos hacer lo siguiente: x(t) = sigma * N(0;1) (lo contrario seria normalizar la variable N(0;1) = x(t) / sigma). Bueno, entonces para hacer el cambio, lo unico que tenia que hacer era generar n variables N(0;1), y despues, para cada uno de los parametros, aplicaba el sigma. Mmmm, creo que esto no quedo claro, bueno, esto queda asi:

x(t) = b * e ^ (a * sin(y(t-1))) * N(0;1)

y(t) = x(t) + y(t-1)

Y esto me parecio bastante piola. Basicamente una cosa que se puede leer de estas ecuaciones, es que el siguiente movimiento va a ser una variable aleatoria, multiplicada por una constante asociada a cada valor y. Esto seria como si nos imaginaramos que hay un numero para cada recta paralela al eje donde graficamos el tiempo (el horizontal), entonces, por ejemplo, a la paralela correspondiente a: a = 2; y = 3 el numero asociado a esa recta es k =2.0830282438600087, esto quiere decir que si en el momento t-1, y era igual a 3, la variable aleatoria que salga sorteada, va a ser multiplicada k.

Esto me triggereo otro pensamiento. En los modelos donde se tiene algo asi como Y = aX donde X es una variable Normal con una media y una varianza, al buscar el parametro a, en realidad lo unico que se esta haciendo es buscar cuales son los parametros (media y varianza) de la variable Y, ya que Y se podria simular como una normal y = N(a*E(X);a*sqrt(Var(X))) donde sqrt(x) es la raiz cuadrada de x. Bueno, es otra forma de pensar lo mismo...
saludos
/jb

ps: dejo un par de imagenes usando el comentario de felipe, donde todas las imagenes se hicieron con las mismas 10000 N(0;1), pero con distinto parametro a

ps2: quedan pendientes los colorsitos
a=1
a=2
a=3
a=4

Random Walk (o no tan walk)

Hace un tiempo estaba pensando en alguna forma de tener un proceso que genere Hysteresis o algun tipo de proceso stochastico (aleatorio y con una relacion temporal), y se me ocurrio este proceso
primero definimos un proceso x(t) = N(0, b * e ^ (a * sin(y(t-1)))) donde a y b son parametros, y N es la distribucion Normal o gaussiana.
y(t) = y(t-1) + x(t) (y(t) = 0 para t <= 0, no jodan)

Bueno, el asunto es que me encontre en que este proceso (el y(t) tiene un comportamiento bastante diferente dependiendo del parametro a (es decir, me encontre con una familia de procesos)
veamos un par de dibujitos.

El primer dibujo no parece nada raro, un poco distinto a una caminata medio borracha.
Ahora, este segundo dibujo, cambiando solamente el parametro a para que valga 2, ya muestra una estructura interesante


Ahora, si en vez de 2, usamos como parametro 3, obtenemos el siguiente grafico:
La structura es completamente distinta. La pregunta seria: "que es lo que esta pasando?"
Bueno, podemos empezar pensando como es un random walk, aca, el "caminante" decide si va a ir para arriba o para abajo usando una funcion de distribucion normal, con media 0, y varianza constante. Aca aparece la primer diferencia.

En este proceso, la varianza no es constante, podriamos decir que la varianza es el parametro b (que por cierto, me olvide comentar, yo uso b = pi/2 por que parece cheto). Esta varianza b, esta expandida o contraida dependiendo del resultado de a * sin (y), es decir, hay partes del camino (es claro que depende del lugar donde se esta, pero no de como se llego ahi), en que sin(y) es un numero negativo, y multiplicado por a, es mas negativo (cuando a es mas grande). Luego, cuando usamos ese valor como exponente, se produce una contraccion de la varianza (los valores van a estar cada vez mas proximos). El caso contrario es cuando el sin(y) > 0, ya que produce un exponente positivo, y eso expande la varianza (y los valores empiezan a saltar).
Una forma de pensar esto, es como navegar (sin timon) por un rio, en las zonas tranquilas, nuestro barquito se va a mover aleatoriamente, pero los cambios van a estar proximos... sin embargo, cuando entramos a una zona de rapidos, el barquito empezara a cambiar de posicion de manera brusca, y saltara entre zonas, hasta volver a encontrar otra zona tranquila en doned se quedara... Por eso este proceso no es tan Walk aunque si bastante Random.
Existe una forma piola de poder graphicar la idea de las corrientes y este proceso, pero para eso tengo que terminar de averiguar como funciona el PlotMorph

saludos
/jb

Primero, infaltable

El por que de este blog, la idea principal es tener un lugar donde pueda poner las cosas que se me van ocurriendo, y que los puedan leer cuando quieran, sin tener que estar molestando a mis amigos continuamente por cosas del estilo "che, me dicuenta que no hay helado de chocolate con granos de cafe", o peores...
Ahora voy a escribir esas cosas, y el que las lee... bueno, ya somos grandes :)