El álgebra básica detrás de los códigos secretos y la comunicación espacial

La exploración espacial requiere una precisión tremenda. Cuando aterriza un rover en Marte a 70 millones de millas de la estación de servicio más cercana, necesita maximizar la eficiencia y prepararse para lo inesperado. Esto se aplica a todo, desde el diseño de naves espaciales hasta la transmisión de datos: los mensajes que regresan a la Tierra como un flujo constante de 0 y 1 seguramente contendrán algunos errores, por lo que debe poder identificarlos y corregirlos sin perder tiempo y energía preciosos.

Ahí es donde entran las matemáticas. Los matemáticos han inventado formas ingeniosas de transmitir y almacenar información. Un método sorprendentemente eficaz utiliza Códigos Reed-Solomon, que se basan en la misma álgebra básica que los estudiantes aprenden en la escuela. Vayamos a una clase de matemáticas para ver cómo los códigos Reed-Solomon ayudan a transmitir y proteger la información mientras corrigen cualquier error costoso que aparezca.

Dos estudiantes, Art y Zeke, están intercambiando mensajes secretos en la clase de matemáticas de la Sra. Al-Jabr. Art despliega la última nota de Zeke para revelar los números 57 y 99. Sabe que tiene que proporcionar el x-coordenadas 3 y 6 para crear los puntos (3, 57) y (6, 99). Art conecta cada punto en la ecuación lineal. y = Ax + B y produce el siguiente sistema de ecuaciones:

57 = 3A + B

99 = 6A + B

Para decodificar el mensaje, Art tiene que resolver A y B. Comienza restando la primera ecuación de la segunda:

Esto elimina B. Dividir ambos lados de esta nueva ecuación por 3 le dice a Art que A = 14, y luego volviendo a sustituir esto en la primera ecuación, 57 = 3 × 14 + B, da B = 15.

Art ahora sabe que la línea que pasa por (3, 57) y (6, 99) está descrita por la ecuación y = 14x + 15. Pero también sabe que en un código Reed-Solomon, el mensaje secreto se esconde en los coeficientes. Él decodifica el mensaje de Zeke usando su cifrado alfabético simple acordado: 14 es "N" y 15 es "O", lo que le dice a Art que, no, Zeke no puede jugar videojuegos después de la escuela hoy.

El secreto de este simple código Reed-Solomon comienza con dos hechos básicos de geometría. Primero, a través de dos puntos cualesquiera hay una línea única. En segundo lugar, para coeficientes A y B, cada línea (no vertical) se puede escribir en la forma y = Ax + B. Juntos, estos dos hechos garantizan que si conoces dos puntos en una línea puedes encontrar A y B, y si sabes A y B, conoces todos los puntos de la recta. En resumen, poseer cualquier conjunto de información es equivalente a conocer la línea.

Los códigos Reed-Solomon aprovechan estos conjuntos de información equivalentes. El mensaje secreto está codificado como los coeficientes A y B, y los puntos de la línea se dividen en partes, algunas de las cuales se transmiten públicamente y otras se mantienen en privado. Para decodificar el mensaje, simplemente junta las piezas y vuelve a juntarlas. Y todo lo que esto requiere es algo de álgebra simple.

Las piezas de Zeke fueron los números 57 y 99, que envió al art. Estos números son la parte pública del mensaje. Art los juntó con sus propias piezas, 3 y 6, para reconstruir los puntos (3, 57) y (6, 99). Aquí, el 3 y el 6 constituyen la parte privada del mensaje, que Art y Zeke acordaron de antemano.

Los dos puntos se encuentran en una línea, y para decodificar el mensaje, solo necesita encontrar la ecuación de esa línea. Conectando cada punto en y = Ax + B te da un sistema de dos ecuaciones sobre la línea que deben ser verdaderas. Ahora la estrategia es sencilla: Resuelva el sistema, determine la línea y decodifique el mensaje.

En la clase de álgebra probablemente aprendiste muchos métodos para resolver sistemas de ecuaciones, como graficar, adivinar, verificar y sustituir. Art usó la eliminación, un método en el que manipulas las ecuaciones algebraicamente para eliminar las variables una a la vez. Cada vez que eliminas una variable, el sistema se vuelve un poco más fácil de resolver.

Al igual que con otros esquemas de encriptación, es la inteligente combinación de información pública y privada lo que mantiene seguros los mensajes. Zeke podría gritar sus números 57 y 99 en el aula y no pondría en peligro la seguridad de su mensaje a Art (aunque podría causarle problemas con la Sra. Al-Jabr). Eso es porque sin la información privada correspondiente, el x-coordenadas 3 y 6 — es imposible identificar la ecuación de la recta. Mientras mantengan esos valores para sí mismos, pueden transmitir sus mensajes secretos en público de manera segura.

La línea y = 14x + 15 está bien para transmitir la palabra de dos letras “no”, pero ¿qué pasa si los estudiantes quieren compartir un secreto más largo? Aquí es donde entra en juego todo el poder del álgebra, la geometría y los sistemas de ecuaciones lineales.

Supongamos que Zeke quiere saber cómo piensa Art que le irá en el examen de inglés de mañana. Art convierte su respuesta de tres letras en los números 14, 59 y 82 y se los pasa a Zeke. Los estudiantes acordaron de antemano que al usar códigos Reed-Solomon de longitud 3, sus números privados son 2, 5 y 6, entonces Zeke junta las piezas para reconstruir los puntos (2, 14), (5, 59) y (6, 82).

Ahora bien, no existe una función lineal que pase por estos tres puntos. Pero hay una función cuadrática única que lo hace. Y como toda función cuadrática se puede escribir en la forma y = Ax² + Bx + C, se puede aplicar el mismo método general. La única diferencia es el tamaño del sistema.

Conectando cada punto en y = Ax² + Bx + C produce una ecuación, por lo que los tres puntos producen el siguiente sistema de tres ecuaciones:

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

Un sistema de tres ecuaciones con tres incógnitas requiere un poco más de trabajo para resolver que un sistema de dos ecuaciones con dos incógnitas, pero el objetivo es el mismo: combinar inteligentemente pares de ecuaciones para eliminar variables.

Por ejemplo, si restas la primera ecuación de la segunda, obtienes la nueva ecuación 45 = 21A + 3B. Del mismo modo, si restas la segunda ecuación de la tercera, obtienes 23 = 11A + B. Estas manipulaciones algebraicas producen un nuevo sistema:

45 = 21A + 3B

23 = 11A + B

Ahora tienes un sistema de "dos por dos": dos ecuaciones con dos incógnitas. Para resolverlo, puedes multiplicar la segunda ecuación por −3 y sumarla a la primera ecuación:

Observe cómo la eliminación repetida ha convertido el sistema original de tres ecuaciones en una sola ecuación que se puede resolver fácilmente: A = 2. Trabajando hacia atrás, puedes conectar A = 2 en una de las ecuaciones en el sistema de dos por dos para encontrar B = 1, y luego reemplaza ambos valores en una de las ecuaciones originales para obtener C = 4. Después de usar el código alfabético simple en 2, 1 y 4, Zeke sabe que a Art le irá "MAL" en el examen de inglés de mañana. Al menos está practicando mucho álgebra.

Gracias a un hecho especial sobre las funciones polinómicas, puede transmitir un mensaje de cualquier longitud usando códigos Reed-Solomon. La clave es esta: Dada cualquier n puntos en el plano con diferentes x-coordenadas, existe un único polinomio de “grado” n − 1 que los atraviesa. El grado de un polinomio es la potencia más alta de una variable en la expresión, por lo que una función cuadrática como Ax² + Bx + C tiene grado 2, ya que la máxima potencia de x es 2. Y una función lineal tiene grado 1, ya que en la ecuación y = Ax + B, el poder supremo de x es 1.

En el primer ejemplo usamos el hecho de que dos puntos determinan un único polinomio lineal, o de grado 1. En el segundo, nos basamos en el hecho de que tres puntos determinan un único polinomio de grado 2, o cuadrático. Y si desea enviar un mensaje de longitud 10, simplemente codifique el mensaje como los 10 coeficientes de una función polinomial de grado 9. Una vez que tenga su función, calcule los 10 públicos y-valores evaluando la función en los 10 privados previamente acordados x-valores. Una vez que haga eso, puede pasar con seguridad esos y-coordenadas en público para que su receptor las decodifique. En la práctica, los códigos Reed-Solomon son un poco más complejos que esto, utilizan tipos de coeficientes y esquemas de traducción más sofisticados, pero la idea fundamental es la misma.

Además de mantener su mensaje seguro, los códigos Reed-Solomon también ofrecen formas simples y eficientes de detectar e incluso corregir errores. Esto es importante cada vez que se transmiten o almacenan datos, ya que siempre existe la posibilidad de que parte de la información se pierda o dañe.

Una solución a este problema sería simplemente enviar copias adicionales de los datos. Por ejemplo, Zeke puede enviar el mensaje [14, 14, 14, 15, 15, 15] en lugar de [14, 15]. Siempre que Art sepa que cada parte del mensaje se envía por triplicado, puede decodificar el mensaje y comprobar si hay errores. De hecho, si encuentra algún error, tiene muchas posibilidades de corregirlo. Si Art recibe [14, 14, 24, 15, 15, 15], el hecho de que los primeros tres números sean diferentes lo alerta de un error, y dado que dos de ellos son 14, puede adivinar que el 24 probablemente debería ser un 14 también. En lugar de pedir que se reenvíe el mensaje, Art puede continuar con su decodificación. Esta es una estrategia efectiva pero costosa. Sea cual sea el tiempo, la energía y el esfuerzo necesarios para enviar n piezas de información, esto requiere tres veces más.

Pero las matemáticas detrás de los códigos Reed-Solomon ofrecen una alternativa eficiente. En lugar de enviar varias copias de cada dato, ¡puedes enviar un punto extra! Si ese punto adicional se ajusta a tu polinomio, entonces la información es correcta. Si no es así, ha habido un error.

Para ver cómo funciona esto, suponga que desea verificar el mensaje "NO" en el primer ejemplo. Zeke puede simplemente enviar el adicional y-coordenada 155. Suponiendo que él y Art acordaron en un tercer privado x-coordinar de antemano, digamos x = 10, Art puede comparar este tercer punto con la línea que decodificó. cuando se enchufa x = 10 en y = 14x + 15 y ve que el resultado es 155, sabe que no hubo errores en la transmisión.

Esto no solo funciona para las líneas. Para permitir que Zeke marque "MALO" en el segundo ejemplo, Art puede enviar y = 25. Si han acordado que 3 es el extra privado x-coordenada, Zeke puede enchufar x = 3 en su función cuadrática y = 2x² + x + 4 y verifique que el punto (3, 25) encaje, confirmando nuevamente una transmisión sin errores con solo un punto más.

Y ese punto adicional también puede corregir errores. Si se detecta un error y el receptor no puede construir la función polinomial que contiene el mensaje, puede construir el polinomio de "mejor ajuste" utilizando técnicas de regresión. Como una línea de mejor ajuste en la clase de estadística, esta es la función polinomial que se determina matemáticamente para ajustarse más a los puntos dados, incluso si no pasa por todos ellos. Según la estructura del mensaje y la cantidad de información adicional que envíe, este polinomio de mejor ajuste puede ayudarlo a reconstruir el polinomio correcto y, por lo tanto, el mensaje correcto, incluso a partir de información corrupta.

Esta eficiencia en la transmisión y corrección de comunicaciones explica por qué la NASA ha utilizado códigos Reed-Solomon en sus misiones a la Luna y Marte. Y te da algo en lo que reflexionar mientras resuelves tu próximo sistema de ecuaciones. Mientras adivina, marque o elimine su camino hacia la solución, piense en el poder y la elegancia de los códigos Reed-Solomon y todos los secretos que su sistema podría revelar.

Ejercicios

1. Usando el mismo esquema que usaron en clase, Art publica los números públicos 33 y 57 para que Zeke los decodifique. ¿Cuál es el mensaje?

2. ¿Cómo pueden Art y Zeke estar seguros de que el sistema de ecuaciones que resulta de sus números privados x = 3 y x = 6 siempre tendrá una solución?

3. En respuesta al mensaje de Art de “MALO” sobre el examen de inglés, Zeke envía [90, 387, 534]. Asumiendo que usan el mismo esquema que usaron en clase, ¿cuál es su mensaje?

4. Lola te envía un mensaje de dos letras más un número de verificación de errores usando un código Reed-Solomon y el mismo cifrado alfabético simple que usan Art y Zeke. Has acordado en secreto el x-coordenadas 1, 3 y 10 de antemano, y Lola transmite los números públicos [27, 43, 90]. ¿El mensaje contiene un error?