sábado, 11 de junio de 2011

Cara o cruz a distancia

¿Sabías que es posible jugar a cara o cruz a distancia sin que medie posible engaño? ¿Cómo es posible? Bien, para exponerlo es necesario conocer algunas ideas matemáticas básicas.
  1. Al dividir un número primo X cualquiera por 4, siempre se obtiene 1 ó 3 de resto.
  2. La probabilidad de obtener resto 1 al dividir un número primo X por 4 es la misma que la probabilidad de obtener resto 3. Esto es: 50%.
Para ilustrar cómo jugar a cara a cruz a distancia tomaremos las siguientes suposiciones:
  1. Llamaremos jugador A y jugador B a cada jugador participante. Evidentemente, ambos jugadores se encuentran en entornos diferentes pero están comunicados (a través de internet por ejemplo).
  2. Denotaremos cara al hecho de obtener resto 1 cuando se divide un número primo por 4. Por otra parte, llamaremos cruz al resto 3.
  3. ¿Quién tira la moneda? Es igual quién lo haga. Nosotros supondremos que es el jugador A quién lo hace. Pero en realidad el jugador A no tira ninguna moneda. En su defecto escogerá un número a partir de un criterio que veremos a continuación.
Ya conocemos todo lo necesario para jugar. Así que... ¡Juguemos! El desarrollo de la partida de cara o cruz viene especificada por los siguientes pasos:
  1. El jugador A escoge dos números primos X e Y de forma que ambos números devuelvan el mismo resto cuando son divididos por 4.
  2. El jugador A multiplica ambos números primos y obtiene el valor P.
  3. El jugador A envía el resultado P al jugador B y le pregunta: ¿Cara o cruz? Realmente el jugador A está preguntando al jugador B: ¿Qué resto eliges? ¿1 (cara) ó 3 (cruz)?
  4. El jugador B tiene un 50% de posibilidades de acertar, puesto que no conoce los dos números primos que el jugador A eligió (X e Y). El jugador B se decantará por una de las dos opciones y enviará su elección al jugador A.
  5. A continuación el jugador A enviará al jugador B los dos números primos X e Y para que se pueda comprobar quién ha ganado. Si el jugador B eligió el mismo valor de resto que aquél que tienen X e Y, entonces ha vencido B. En otro caso habrá ganado A. Para comprobar que no ha habido engaño bastará con que el jugador B compruebe que el producto de los números primos X e Y es igual al valor P que el jugador A le envió en el paso 3.
A continuación ejemplifiquemos el juego:
  1. El jugador A elige los números primos X = 727 e Y = 1031. Ambos números primos devuelven un 3 de resto (o lo que es lo mismo: Cruz) al ser divididos por 4.
  2. El jugador A realiza el producto de X e Y, y obtiene P = 749537.
  3. El jugador A envía P = 749537 al jugador B.
  4. El jugador B apuesta por resto 1 (cara) y se lo hace saber al jugador A.
  5. El jugador A, que ya sabe que ha ganado, envía los números primos X e Y al jugador B, el cual divide ambos números por 4 obteniendo 3 (cruz) en ambos casos. Además el jugador B comprueba que el juego ha sido limpio al realizar el producto de X e Y, y comprobar que coincide con el número P. El jugador B ha perdido. Apostó cara (resto 1) y salió cruz (resto 3).

Posibles problemas de este juego: Cuando decimos que el jugador B tiene un 50% de probabilidades estamos suponiendo implícitamente que no se puede descomponer (factorizar) el valor P en sus dos números primos. Si el valor P es pequeño, el problema se torna fácil para el jugador B, pero con un número relativamente grande la tarea de factorización se hace más que complicada (y más aún, si el jugador B tiene que responder cara o cruz en un espacio breve de tiempo). De hecho, si los números son muy grandes el problema es irresoluble. Basta leer un poco el artículo de Factorización de enteros que aparece en Wikipedia para encontrarse con una frase que dice textualmente: "Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema". Es más, gran parte de la seguridad mundial depende de que se encuentre solución a este problema, pero esa es otra historia. Concluyendo: Con un número P relativamente grande la factorización se complica y hace seguro nuestro juego de cara o cruz.

Enlace con los 10.000 primeros números primos para poder jugar a cara o cruz a distancia.

Gracias a Michelle ("These are words that go together well").