A álgebra básica por trás dos códigos secretos e da comunicação espacial

A exploração espacial requer uma precisão tremenda. Quando você está pousando um rover em Marte a 70 milhões de milhas de distância do posto de gasolina mais próximo, você precisa maximizar a eficiência e se preparar para o inesperado. Isso se aplica a tudo, desde o projeto da espaçonave até a transmissão de dados: as mensagens que retornam à Terra como um fluxo constante de 0s e 1s podem conter alguns erros; portanto, você precisa ser capaz de identificá-los e corrigi-los sem desperdiçar tempo e energia preciosos.

É aí que entra a matemática. Os matemáticos inventaram maneiras engenhosas de transmitir e armazenar informações. Um método surpreendentemente eficaz usa Códigos Reed-Solomon, que são construídos sobre a mesma álgebra básica que os alunos aprendem na escola. Vamos assistir a uma aula de matemática para ver como os códigos Reed-Solomon ajudam a transmitir e proteger informações enquanto corrigem quaisquer erros dispendiosos que apareçam.

Dois alunos, Art e Zeke, estão trocando mensagens secretas na aula de matemática da Sra. Al-Jabr. Art revela a última nota de Zeke para revelar os números 57 e 99. Ele sabe que tem que fornecer o x-coordenadas 3 e 6 para criar os pontos (3, 57) e (6, 99). Art conecta cada ponto na equação linear y = Ax + B e produz o seguinte sistema de equações:

57 = 3A + B

99 = 6A + B

Para decodificar a mensagem, Art precisa resolver A e B. Ele começa subtraindo a primeira equação da segunda:

Isso elimina B. Dividindo ambos os lados desta nova equação por 3 diz a Art que A = 14 e, em seguida, substituindo isso de volta na primeira equação, 57 = 3 × 14 + Bdá B = 15.

Art agora sabe que a reta que passa por (3, 57) e (6, 99) é descrita pela equação y = 14x + 15. Mas ele também sabe que em um código Reed-Solomon, a mensagem secreta está escondida nos coeficientes. Ele decodifica a mensagem de Zeke usando a cifra alfabética simples combinada: 14 é “N” e 15 é “O”, o que diz a Art que não, Zeke não pode jogar videogame depois da escola hoje.

O segredo desse código Reed-Solomon simples começa com dois fatos básicos da geometria. Primeiro, através de quaisquer dois pontos existe uma única linha. Em segundo lugar, para coeficientes A e B, toda linha (não vertical) pode ser escrita na forma y = Ax + B. Juntos, esses dois fatos garantem que, se você conhece dois pontos em uma linha, pode encontrar A e B, e se você sabe A e B, você conhece todos os pontos na linha. Em suma, possuir qualquer conjunto de informações é equivalente a conhecer a linha.

Os códigos Reed-Solomon utilizam esses conjuntos equivalentes de informações. A mensagem secreta é codificada como os coeficientes A e B, e os pontos da linha são divididos em pedaços, alguns dos quais são transmitidos publicamente e alguns dos quais são mantidos em sigilo. Para decodificar a mensagem, basta coletar as peças e juntá-las novamente. E tudo o que isso requer é alguma álgebra simples.

As peças de Zeke eram os números 57 e 99, que ele enviou para a Art. Esses números são a parte pública da mensagem. Art os juntou com suas próprias peças, 3 e 6, para reconstruir os pontos (3, 57) e (6, 99). Aqui, o 3 e o 6 constituem a parte privada da mensagem, que Art e Zeke concordaram de antemão.

Os dois pontos estão em uma linha e, para decodificar a mensagem, você só precisa encontrar a equação dessa linha. Conectando cada ponto em y = Ax + B dá a você um sistema de duas equações sobre a reta que devem ser ambas verdadeiras. Agora a estratégia é direta: resolva o sistema, determine a linha e decodifique a mensagem.

Na aula de álgebra, você provavelmente aprendeu muitos métodos de resolução de sistemas de equações, como gráficos, suposições e verificações e substituição. Art usou a eliminação, um método em que você manipula as equações algebricamente para eliminar as variáveis ​​uma de cada vez. Cada vez que você elimina uma variável, o sistema fica um pouco mais fácil de resolver.

Como em outros esquemas de criptografia, é a combinação inteligente de informações públicas e privadas que mantém as mensagens seguras. Zeke poderia gritar seus números 57 e 99 em toda a sala de aula e isso não prejudicaria a segurança de sua mensagem para Art (embora isso pudesse colocá-lo em apuros com a Sra. Al-Jabr). Isso porque sem as informações privadas correspondentes - o x-coordenadas 3 e 6 — é impossível identificar a equação da reta. Desde que guardem esses valores para si mesmos, eles podem passar com segurança suas mensagens secretas em público.

A linha y = 14x + 15 é bom para transmitir a palavra de duas letras “não”, mas e se os alunos quiserem compartilhar um segredo mais longo? Aqui é onde entra em jogo todo o poder da álgebra, geometria e sistemas de equações lineares.

Suponha que Zeke queira saber como Art acha que ele se sairá no teste de inglês de amanhã. Art converte sua resposta de três letras nos números 14, 59 e 82 e os passa para Zeke. Os alunos concordaram de antemão que, ao usar códigos Reed-Solomon de comprimento 3, seus números privados são 2, 5 e 6, então Zeke junta as peças para reconstruir os pontos (2, 14), (5, 59) e (6, 82).

Agora, não há função linear que passe por esses três pontos. Mas há uma única função quadrática que o faz. E como toda função quadrática pode ser escrita na forma y = Ax² + Bx + C, o mesmo método geral pode ser aplicado. A única diferença é o tamanho do sistema.

Conectando cada ponto em y = Ax² + Bx + C produz uma equação, então os três pontos produzem o seguinte sistema de três equações:

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

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

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

Um sistema de três equações com três incógnitas requer um pouco mais de trabalho para resolver do que um sistema de duas equações com duas incógnitas, mas o objetivo é o mesmo: combinar pares de equações de forma inteligente para eliminar variáveis.

Por exemplo, se você subtrair a primeira equação da segunda, obtém a nova equação 45 = 21A + 3B. Da mesma forma, se você subtrair a segunda equação da terceira, obtém 23 = 11A + B. Essas manipulações algébricas produzem um novo sistema:

45 = 21A + 3B

23 = 11A + B

Agora você tem um sistema “dois por dois”: duas equações com duas incógnitas. Para resolvê-lo, você pode multiplicar a segunda equação por -3 e adicioná-lo à primeira equação:

Observe como a eliminação repetida transformou o sistema original de três equações em uma única equação que pode ser facilmente resolvida: A = 2. Trabalhando para trás, você pode conectar A = 2 em uma das equações no sistema dois por dois para encontrar B = 1 e, em seguida, insira ambos os valores em uma das equações originais para obter C = 4. Depois de usar a cifra do alfabeto simples em 2, 1 e 4, Zeke sabe que Art vai tirar “RUIM” na prova de inglês de amanhã. Pelo menos ele está praticando bastante álgebra.

Graças a um fato especial sobre funções polinomiais, você pode transmitir uma mensagem de qualquer comprimento usando códigos Reed-Solomon. A chave é esta: dado qualquer n pontos no plano com diferentes x-coordenadas, existe um único polinômio de “grau” n − 1 que passa por eles. O grau de um polinômio é a maior potência de uma variável na expressão, então uma função quadrática como Ax² + Bx + C tem grau 2, pois a maior potência de x é 2. E uma função linear tem grau 1, já que na equação y = Ax + B, a maior potência de x é 1.

No primeiro exemplo usamos o fato de que dois pontos determinam um polinômio linear único, ou polinômio de grau 1. No segundo, contamos com o fato de que três pontos determinam um único polinômio de grau 2, ou quadrático. E se você quiser enviar uma mensagem de comprimento 10, basta codificar a mensagem como os 10 coeficientes de uma função polinomial de grau 9. Depois de ter sua função, calcule os 10 públicos y-valores avaliando a função nos 10 privados previamente acordados x-valores. Depois de fazer isso, você pode passar com segurança aqueles y-coordenadas em público para o seu receptor decodificar. Na prática, os códigos Reed-Solomon são um pouco mais complexos do que isso, utilizando tipos mais sofisticados de coeficientes e esquemas de tradução, mas a ideia fundamental é a mesma.

Além de manter sua mensagem segura, os códigos Reed-Solomon também oferecem maneiras simples e eficientes de detectar e até mesmo corrigir erros. Isso é importante sempre que os dados são transmitidos ou armazenados, pois sempre há uma chance de que algumas das informações sejam perdidas ou corrompidas.

Uma solução para esse problema seria simplesmente enviar cópias extras dos dados. Por exemplo, Zeke pode enviar a mensagem [14, 14, 14, 15, 15, 15] em vez de [14, 15]. Contanto que Art saiba que todas as partes da mensagem são enviadas em triplicado, ele pode decodificar a mensagem e verificar se há erros. Na verdade, se ele encontrar algum erro, tem uma boa chance de corrigi-lo. Se Art receber [14, 14, 24, 15, 15, 15], o fato de os três primeiros números serem diferentes o alerta para um erro e, como dois deles são 14, ele pode adivinhar que o 24 provavelmente deveria ser um 14 também. Em vez de pedir que a mensagem seja reenviada, Art pode prosseguir com sua decodificação. Esta é uma estratégia eficaz, mas cara. Seja qual for o tempo, energia e esforço necessários para enviar n pedaços de informação, isso requer três vezes mais.

Mas a matemática por trás dos códigos Reed-Solomon oferece uma alternativa eficiente. Em vez de enviar várias cópias de cada dado, você pode enviar apenas um ponto extra! Se esse ponto adicional se ajustar ao seu polinômio, a informação está correta. Se não, houve um erro.

Para ver como isso funciona, suponha que você queira verificar a mensagem “NÃO” no primeiro exemplo. Zeke pode apenas enviar o adicional y-coordenar 155. Supondo que ele e Art concordaram em um terceiro privado x-coordene de antemão, diga x = 10, Art pode verificar este terceiro ponto contra a linha que ele decodificou. quando ele liga x = 10 em y = 14x +15 e vê que o resultado é 155, sabe que não houve erros na transmissão.

Isso não funciona apenas para linhas. Para permitir que Zeke marque “BAD” no segundo exemplo, Art pode enviar y = 25. Se eles concordaram que 3 é o extra privado x-coordenar, Zeke pode conectar x = 3 em sua função quadrática y = 2x² + x + 4 e verifique se o ponto (3, 25) se encaixa, novamente confirmando uma transmissão sem erros com apenas mais um ponto.

E esse ponto extra também pode potencialmente corrigir erros. Se for detectado um erro e o receptor não puder construir a função polinomial que contém a mensagem, ele pode, em vez disso, construir o polinômio de “melhor ajuste” usando técnicas de regressão. Como uma linha de melhor ajuste na aula de estatística, esta é a função polinomial que é determinada matematicamente para se ajustar melhor aos pontos dados, mesmo que não passe por todos eles. Dependendo da estrutura da mensagem e quanta informação extra você envia, este polinômio de melhor ajuste pode ajudá-lo a reconstruir o polinômio correto — e, portanto, a mensagem correta — mesmo a partir de informações corrompidas.

Essa eficiência na transmissão e correção das comunicações explica por que a NASA tem usado os códigos Reed-Solomon em suas missões à Lua e a Marte. E dá a você algo para ponderar enquanto resolve seu próximo sistema de equações. Ao adivinhar, verifique ou elimine o caminho para a solução, pense no poder e na elegância dos códigos Reed-Solomon e em todos os segredos que seu sistema pode revelar.

Exercícios

1. Usando o mesmo esquema que usaram na aula, Art publica os números públicos 33 e 57 para Zeke decodificar. Qual é a mensagem?

2. Como Art e Zeke podem ter certeza de que o sistema de equações que resulta de seus números privados x = 3 e x = 6 sempre terá solução?

3. Em resposta à mensagem de Art de “RUIM” sobre o teste de inglês, Zeke envia de volta [90, 387, 534]. Supondo que eles usem o mesmo esquema que usaram em sala de aula, qual é a mensagem dele?

4. Lola envia a você uma mensagem de duas letras mais um número de verificação de erro usando um código Reed-Solomon e a mesma cifra alfabética simples usada por Art e Zeke. Você secretamente concordou com o x-coordena 1, 3 e 10 com antecedência, e Lola transmite os números públicos [27, 43, 90]. A mensagem contém um erro?