L'algebra di base dietro i codici segreti e la comunicazione spaziale

L'esplorazione dello spazio richiede un'enorme precisione. Quando fai atterrare un rover su Marte a 70 milioni di miglia di distanza dalla stazione di servizio più vicina, devi massimizzare l'efficienza e prepararti all'imprevisto. Questo vale per tutto, dalla progettazione di veicoli spaziali alla trasmissione dei dati: quei messaggi che ritornano sulla Terra come un flusso costante di 0 e 1 sono destinati a contenere alcuni errori, quindi devi essere in grado di identificarli e correggerli senza sprecare tempo ed energia preziosi.

È qui che entra in gioco la matematica. I matematici hanno inventato modi ingegnosi per trasmettere e immagazzinare informazioni. Un metodo sorprendentemente efficace utilizza Codici Reed-Solomon, che si basano sulla stessa algebra di base che gli studenti imparano a scuola. Facciamo un salto in una lezione di matematica per vedere come i codici Reed-Solomon aiutano a trasmettere e proteggere le informazioni correggendo eventuali errori costosi che si presentano.

Due studenti, Art e Zeke, si scambiano messaggi segreti nella classe di matematica della signora Al-Jabr. Art spiega l'ultima nota di Zeke per rivelare i numeri 57 e 99. Sa che deve fornire il x-coordinate 3 e 6 per creare i punti (3, 57) e (6, 99). L'arte inserisce ogni punto nell'equazione lineare y = Ax + B e produce il seguente sistema di equazioni:

57 = 3A + B

99 = 6A + B

Per decodificare il messaggio, l'arte deve risolverlo A ed B. Inizia sottraendo la prima equazione dalla seconda:

Questo elimina B. Dividendo entrambi i lati di questa nuova equazione per 3 dice Art che A = 14, e poi sostituendolo nella prima equazione, 57 = 3 × 14 + B, dà B = 15.

L'arte ora sa che la retta passante per (3, 57) e (6, 99) è descritta dall'equazione y = 14x + 15. Ma sa anche che in un codice Reed-Solomon, il messaggio segreto si nasconde nei coefficienti. Decodifica il messaggio di Zeke usando il loro semplice codice alfabetico concordato: 14 è "N" e 15 è "O", il che dice ad Art che, no, Zeke non può giocare ai videogiochi oggi dopo la scuola.

Il segreto di questo semplice codice Reed-Solomon inizia con due fatti fondamentali della geometria. Innanzitutto, attraverso due punti qualsiasi c'è una linea unica. In secondo luogo, per i coefficienti A ed B, ogni riga (non verticale) può essere scritta nel form y = Ax + B. Insieme, questi due fatti garantiscono che se conosci due punti su una retta puoi trovarli A ed B, e se lo sai A ed B, conosci tutti i punti sulla linea. In breve, possedere l'uno o l'altro set di informazioni equivale a conoscere la linea.

I codici Reed-Solomon sfruttano questi insiemi equivalenti di informazioni. Il messaggio segreto è codificato come coefficienti A ed B, e i punti della linea sono suddivisi in parti, alcune delle quali vengono trasmesse pubblicamente, altre mantenute private. Per decodificare il messaggio basta raccogliere i pezzi e rimetterli insieme. E tutto ciò che richiede è un po' di semplice algebra.

I pezzi di Zeke erano i numeri 57 e 99, che ha inviato ad Art. Questi numeri sono la parte pubblica del messaggio. Art li ha messi insieme ai suoi pezzi, 3 e 6, per ricostruire i punti (3, 57) e (6, 99). Qui, il 3 e il 6 costituiscono la parte privata del messaggio, che Art e Zeke hanno concordato in anticipo.

I due punti giacciono su una linea e per decodificare il messaggio devi solo trovare l'equazione di quella linea. Collegando ogni punto in y = Ax + B ti dà un sistema di due equazioni sulla retta che devono essere entrambe vere. Ora la strategia è semplice: risolvi il sistema, determina la linea e decodifica il messaggio.

Nella lezione di algebra probabilmente hai imparato molti metodi per risolvere sistemi di equazioni, come la rappresentazione grafica, l'ipotesi e il controllo e la sostituzione. Art ha utilizzato l'eliminazione, un metodo in cui si manipolano le equazioni algebricamente per eliminare le variabili una alla volta. Ogni volta che elimini una variabile, il sistema diventa un po' più facile da risolvere.

Come con altri schemi di crittografia, è l'intelligente combinazione di informazioni pubbliche e private che mantiene i messaggi al sicuro. Zeke potrebbe gridare i suoi numeri 57 e 99 in tutta la classe e non metterebbe a repentaglio la sicurezza del suo messaggio ad Art (anche se potrebbe metterlo nei guai con la signora Al-Jabr). Questo perché senza le corrispondenti informazioni private — the x-coordinate 3 e 6 — è impossibile identificare l'equazione della retta. Finché mantengono questi valori per sé, possono tranquillamente trasmettere i loro messaggi segreti in pubblico.

La linea y = 14x + 15 va bene per trasmettere la parola di due lettere "no", ma cosa succede se gli studenti vogliono condividere un segreto più lungo? È qui che entra in gioco tutta la potenza dell'algebra, della geometria e dei sistemi di equazioni lineari.

Supponiamo che Zeke voglia sapere come Art pensa che se la caverà al test di inglese di domani. Art converte la sua risposta di tre lettere nei numeri 14, 59 e 82 e li passa a Zeke. Gli studenti hanno concordato in anticipo che quando si usano i codici Reed-Solomon di lunghezza 3, i loro numeri privati ​​sono 2, 5 e 6, quindi Zeke mette insieme i pezzi per ricostruire i punti (2, 14), (5, 59) e (6, 82).

Ora, non c'è nessuna funzione lineare che passi per questi tre punti. Ma c'è una funzione quadratica unica che lo fa. E poiché ogni funzione quadratica può essere scritta nella forma y = Ax² + Bx + C, si può applicare lo stesso metodo generale. L'unica differenza è la dimensione del sistema.

Collegando ogni punto in y = Ax² + Bx + C produce un'equazione, quindi i tre punti producono il seguente sistema di tre equazioni:

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

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

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

Un sistema di tre equazioni con tre incognite richiede un po' più di lavoro per risolverlo rispetto a un sistema di due equazioni con due incognite, ma l'obiettivo è lo stesso: combinare abilmente coppie di equazioni per eliminare le variabili.

Ad esempio, se sottrai la prima equazione dalla seconda, ottieni la nuova equazione 45 = 21A + 3B. Allo stesso modo, se sottrai la seconda equazione dalla terza, ottieni 23 = 11A + B. Queste manipolazioni algebriche producono un nuovo sistema:

45 = 21A + 3B

23 = 11A + B

Ora hai un sistema "due a due": due equazioni con due incognite. Per risolverlo, puoi moltiplicare la seconda equazione per −3 e aggiungerla alla prima equazione:

Nota come l'eliminazione ripetuta ha trasformato il sistema originale di tre equazioni in un'unica equazione che può essere facilmente risolta: A = 2. Lavorando all'indietro, puoi tappare A = 2 in una delle equazioni del sistema due per due da trovare B = 1, quindi inserire entrambi i valori in una delle equazioni originali per ottenere C = 4. Dopo aver usato il semplice cifrario alfabetico su 2, 1 e 4, Zeke sa che Art farà "BAD" al test di inglese di domani. Almeno sta facendo molta pratica di algebra.

Grazie a un fatto speciale sulle funzioni polinomiali, puoi trasmettere un messaggio di qualsiasi lunghezza utilizzando i codici Reed-Solomon. La chiave è questa: Dato qualsiasi n punti nel piano con diversi x-coordinate, esiste un unico polinomio di “grado” n − 1 che li attraversa. Il grado di un polinomio è la massima potenza di una variabile nell'espressione, quindi una funzione quadratica come Ax² + Bx + C ha grado 2, poiché la più alta potenza di x è 2. E una funzione lineare ha grado 1, poiché nell'equazione y = Ax + B, il più alto potere di x è 1.

Nel primo esempio abbiamo utilizzato il fatto che due punti determinano un unico polinomio lineare, o di grado 1. Nel secondo, ci siamo basati sul fatto che tre punti determinano un unico polinomio di grado 2, o quadratico. E se vuoi inviare un messaggio di lunghezza 10, basta codificare il messaggio come i 10 coefficienti di una funzione polinomiale di grado 9. Una volta che hai la tua funzione, calcola i 10 pubblici y-valori valutando la funzione al 10 privato precedentemente concordato x-i valori. Una volta che lo fai, puoi tranquillamente passarli y-coordinate in pubblico affinché il tuo ricevitore possa decodificarle. In pratica, i codici Reed-Solomon sono un po' più complessi di così, poiché utilizzano tipi di coefficienti e schemi di traduzione più sofisticati, ma l'idea fondamentale è la stessa.

Oltre a proteggere il tuo messaggio, i codici Reed-Solomon offrono anche modi semplici ed efficienti per rilevare e persino correggere gli errori. Questo è importante ogni volta che i dati vengono trasmessi o archiviati, poiché c'è sempre la possibilità che alcune informazioni vengano perse o danneggiate.

Una soluzione a questo problema sarebbe semplicemente inviare copie extra dei dati. Ad esempio, Zeke può inviare il messaggio [14, 14, 14, 15, 15, 15] invece di [14, 15]. Finché Art sa che ogni parte del messaggio viene inviata in triplice copia, può decodificare il messaggio e verificare la presenza di errori. Infatti, se trova degli errori, ha buone possibilità di correggerli. Se Arte riceve [14, 14, 24, 15, 15, 15], il fatto che i primi tre numeri siano diversi lo avverte di un errore, e poiché due di essi sono 14, può intuire che il 24 dovrebbe probabilmente essere un 14 pure. Invece di chiedere il rinvio del messaggio, Art può continuare la sua decodifica. Questa è una strategia efficace ma costosa. Qualunque sia il tempo, l'energia e lo sforzo necessari per inviare n pezzi di informazioni, questo richiede tre volte tanto.

Ma la matematica alla base dei codici Reed-Solomon offre un'alternativa efficiente. Invece di inviare più copie di ogni dato, puoi semplicemente inviare un punto in più! Se quel punto aggiuntivo si adatta al tuo polinomio, allora l'informazione è corretta. In caso contrario, c'è stato un errore.

Per vedere come funziona, supponiamo di voler controllare il messaggio "NO" nel primo esempio. Zeke può semplicemente inviare l'ulteriore y-coordinate 155. Supponendo che lui e Art si accordassero su un terzo privato x- coordinare in anticipo, diciamo x = 10, Art può confrontare questo terzo punto con la riga che ha decodificato. Quando si collega x = 10 dentro y = 14x + 15 e vede che il risultato è 155, sa che non ci sono stati errori di trasmissione.

Questo non funziona solo per le linee. Per consentire a Zeke di controllare "BAD" nel secondo esempio, Art può inviare y = 25. Se hanno concordato che 3 è il privato extra x-coordinate, Zeke può collegarsi x = 3 nella sua funzione quadratica y = 2x² + x + 4 e verificare che il punto (3, 25) si adatti, confermando ancora una volta una trasmissione senza errori con un solo punto in più.

E quel punto in più può potenzialmente correggere anche gli errori. Se viene rilevato un errore e il destinatario non è in grado di costruire la funzione polinomiale che contiene il messaggio, può invece costruire il polinomio "migliore" utilizzando tecniche di regressione. Come una linea di miglior adattamento nella classe statistica, questa è la funzione polinomiale determinata matematicamente per adattarsi al meglio ai punti dati, anche se non li attraversa tutti. A seconda della struttura del messaggio e della quantità di informazioni aggiuntive che invii, questo polinomio più adatto può aiutarti a ricostruire il polinomio corretto, e quindi il messaggio corretto, anche da informazioni corrotte.

Questa efficienza nella trasmissione e correzione delle comunicazioni spiega perché la NASA ha utilizzato i codici Reed-Solomon nelle sue missioni sulla luna e su Marte. E ti dà qualcosa su cui riflettere mentre risolvi il tuo prossimo sistema di equazioni. Mentre indovini, controlli o elimini la tua strada verso la soluzione, pensa alla potenza e all'eleganza dei codici Reed-Solomon ea tutti i segreti che il tuo sistema potrebbe rivelare.

esercizi

1. Utilizzando lo stesso schema che hanno usato in classe, Art pubblica i numeri pubblici 33 e 57 affinché Zeke li decodifichi. Qual è il messaggio?

2. Come possono Art e Zeke essere sicuri che il sistema di equazioni che risulta dai loro numeri privati x = 3 e x = 6 avrà sempre una soluzione?

3. In risposta al messaggio di Art di "BAD" sul test di inglese, Zeke rimanda indietro [90, 387, 534]. Supponendo che usino lo stesso schema che hanno usato in classe, qual è il suo messaggio?

4. Lola ti invia un messaggio di due lettere più un numero di controllo degli errori utilizzando un codice Reed-Solomon e lo stesso semplice codice alfabetico utilizzato da Art e Zeke. Hai segretamente accettato il x-coordina in anticipo 1, 3 e 10, e Lola trasmette i numeri pubblici [27, 43, 90]. Il messaggio contiene un errore?