Aljabar Dasar Di Balik Kode Rahasia dan Komunikasi Ruang Angkasa

Eksplorasi ruang angkasa membutuhkan ketelitian yang luar biasa. Saat Anda mendaratkan penjelajah di Mars yang berjarak 70 juta mil dari stasiun layanan terdekat, Anda perlu memaksimalkan efisiensi dan mempersiapkan diri untuk hal yang tidak terduga. Ini berlaku untuk semuanya, mulai dari desain pesawat ruang angkasa hingga transmisi data: Pesan-pesan yang kembali ke Bumi sebagai aliran 0 dan 1 yang stabil pasti mengandung beberapa kesalahan, jadi Anda harus dapat mengidentifikasi dan memperbaikinya tanpa membuang waktu dan energi yang berharga.

Di situlah matematika masuk. Matematikawan telah menemukan cara cerdik untuk mengirimkan dan menyimpan informasi. Salah satu metode yang sangat efektif digunakan Kode Reed-Solomon, yang dibangun di atas aljabar dasar yang sama dengan yang dipelajari siswa di sekolah. Mari mampir ke kelas matematika untuk melihat bagaimana kode Reed-Solomon membantu mengirimkan dan mengamankan informasi sambil memperbaiki kesalahan mahal yang muncul.

Dua siswa, Art dan Zeke, bertukar pesan rahasia di kelas matematika Ms. Al-Jabr. Art membeberkan catatan terbaru Zeke untuk mengungkapkan angka 57 dan 99. Dia tahu dia harus memberikan x-koordinat 3 dan 6 untuk membuat titik (3, 57) dan (6, 99). Seni memasukkan setiap titik ke dalam persamaan linier y = Ax + B dan menghasilkan sistem persamaan berikut:

57 = 3A + B

99 = 6A + B

Untuk memecahkan kode pesan, Art harus menyelesaikannya A dan B. Dia mulai dengan mengurangkan persamaan pertama dari yang kedua:

Ini menghilangkan B. Membagi kedua sisi persamaan baru ini dengan 3 memberi tahu Art itu A = 14, lalu substitusikan kembali ke persamaan pertama, 57 = 3 × 14 + B, memberi B = 15.

Seni sekarang mengetahui bahwa garis yang melewati (3, 57) dan (6, 99) dijelaskan oleh persamaan y = 14x + 15. Tapi dia juga tahu bahwa dalam kode Reed-Solomon, pesan rahasia bersembunyi di koefisien. Dia menerjemahkan pesan Zeke menggunakan sandi alfabet sederhana yang disepakati: 14 adalah "N" dan 15 adalah "O", yang memberi tahu Art bahwa, tidak, Zeke tidak bisa bermain video game sepulang sekolah hari ini.

Rahasia kode Reed-Solomon sederhana ini dimulai dengan dua fakta dasar geometri. Pertama, melalui dua titik ada garis unik. Kedua, untuk koefisien A dan B, setiap baris (non-vertikal) dapat ditulis dalam bentuk y = Ax + B. Bersama-sama, kedua fakta ini menjamin bahwa jika Anda mengetahui dua titik pada suatu garis, Anda dapat menemukannya A dan B, dan jika Anda tahu A dan B, Anda tahu semua poin di telepon. Singkatnya, memiliki salah satu set informasi setara dengan mengetahui garis.

Kode Reed-Solomon memanfaatkan kumpulan informasi yang setara ini. Pesan rahasia dikodekan sebagai koefisien A dan B, dan titik-titik garis dipecah menjadi beberapa bagian, beberapa di antaranya ditransmisikan secara publik, dan beberapa di antaranya dirahasiakan. Untuk memecahkan kode pesan, Anda cukup mengumpulkan potongan-potongan itu dan menyatukannya kembali. Dan yang dibutuhkan hanyalah beberapa aljabar sederhana.

Karya Zeke adalah nomor 57 dan 99, yang dia kirim ke Art. Angka-angka ini adalah bagian publik dari pesan tersebut. Art menyatukannya dengan karya-karyanya sendiri, 3 dan 6, untuk merekonstruksi poin (3, 57) dan (6, 99). Di sini, angka 3 dan 6 merupakan bagian pribadi dari pesan, yang telah disetujui oleh Art dan Zeke sebelumnya.

Kedua titik terletak pada satu garis, dan untuk memecahkan kode pesannya, Anda hanya perlu menemukan persamaan garis itu. Memasukkan setiap titik ke dalam y = Ax + B memberi Anda sistem dua persamaan tentang garis yang keduanya harus benar. Sekarang strateginya mudah: Selesaikan sistemnya, tentukan garisnya dan dekode pesannya.

Di kelas aljabar Anda mungkin belajar banyak metode penyelesaian sistem persamaan, seperti grafik, tebakan dan pengecekan, dan substitusi. Seni menggunakan eliminasi, metode di mana Anda memanipulasi persamaan secara aljabar untuk menghilangkan variabel satu per satu. Setiap kali Anda menghilangkan variabel, sistem menjadi sedikit lebih mudah untuk diselesaikan.

Seperti skema enkripsi lainnya, kombinasi cerdas antara informasi publik dan pribadilah yang membuat pesan tetap aman. Zeke dapat meneriakkan nomor 57 dan 99 ke seberang kelas dan hal itu tidak akan membahayakan keamanan pesannya kepada Art (meski mungkin akan membuatnya bermasalah dengan Ms. Al-Jabr). Itu karena tanpa informasi pribadi yang sesuai — itu x-koordinat 3 dan 6 — tidak mungkin untuk mengidentifikasi persamaan garis. Selama mereka menyimpan nilai-nilai itu untuk diri mereka sendiri, mereka dapat dengan aman menyampaikan pesan rahasia mereka di depan umum.

Garis y = 14x + 15 baik untuk mengirimkan kata dua huruf "tidak", tetapi bagaimana jika siswa ingin berbagi rahasia yang lebih panjang? Di sinilah kekuatan penuh aljabar, geometri, dan sistem persamaan linier berperan.

Misalkan Zeke ingin tahu bagaimana menurut Art dia akan melakukan tes bahasa Inggris besok. Art mengubah jawaban tiga hurufnya menjadi angka 14, 59 dan 82 dan meneruskannya ke Zeke. Para siswa setuju sebelumnya bahwa ketika menggunakan kode Reed-Solomon dengan panjang 3, nomor pribadi mereka adalah 2, 5 dan 6, jadi Zeke menyatukan potongan-potongan itu untuk merekonstruksi titik (2, 14), (5, 59) dan (6, 82).

Sekarang, tidak ada fungsi linier yang melewati ketiga titik tersebut. Tapi ada fungsi kuadrat unik yang berfungsi. Dan karena setiap fungsi kuadrat dapat ditulis dalam bentuk y = Ax² + Bx + C, metode umum yang sama dapat diterapkan. Satu-satunya perbedaan adalah ukuran sistem.

Memasukkan setiap titik ke dalam y = Ax² + Bx + C menghasilkan satu persamaan, sehingga tiga titik menghasilkan sistem tiga persamaan berikut:

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

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

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

Sistem tiga persamaan dengan tiga yang tidak diketahui membutuhkan lebih banyak pekerjaan untuk dipecahkan daripada sistem dua persamaan dengan dua yang tidak diketahui, tetapi tujuannya sama: Menggabungkan pasangan persamaan dengan cerdik untuk menghilangkan variabel.

Misalnya, jika Anda mengurangkan persamaan pertama dari persamaan kedua, Anda mendapatkan persamaan baru 45 = 21A + 3B. Demikian juga, jika Anda mengurangkan persamaan kedua dari persamaan ketiga, Anda mendapatkan 23 = 11A + B. Manipulasi aljabar ini menghasilkan sistem baru:

45 = 21A + 3B

23 = 11A + B

Sekarang Anda memiliki sistem "dua-dua": dua persamaan dengan dua yang tidak diketahui. Untuk menyelesaikannya, Anda dapat mengalikan persamaan kedua dengan −3 dan menambahkannya ke persamaan pertama:

Perhatikan bagaimana eliminasi berulang telah mengubah sistem asli dari tiga persamaan menjadi satu persamaan yang dapat diselesaikan dengan mudah: A = 2. Bekerja mundur, Anda bisa pasang A = 2 ke salah satu persamaan dalam sistem dua-dua untuk mencari B = 1, lalu masukkan kedua nilai ke dalam salah satu persamaan awal untuk mendapatkan C = 4. Setelah menggunakan cipher alfabet sederhana pada 2, 1 dan 4, Zeke tahu bahwa Art akan mendapat nilai "BURUK" pada tes bahasa Inggris besok. Setidaknya dia mendapatkan banyak latihan aljabar.

Berkat fakta khusus tentang fungsi polinomial, Anda dapat mengirimkan pesan dengan panjang berapa pun menggunakan kode Reed-Solomon. Kuncinya adalah ini: Diberikan apapun n poin di pesawat dengan berbeda x-koordinat, ada polinomial unik "derajat" n − 1 yang melewatinya. Tingkat polinomial adalah kekuatan tertinggi dari variabel dalam ekspresi, jadi seperti fungsi kuadrat Ax² + Bx + C memiliki derajat 2, karena kekuatan tertinggi x adalah 2. Dan fungsi linier memiliki derajat 1, karena dalam persamaan y = Ax + B, kekuatan tertinggi dari x adalah 1.

Dalam contoh pertama kami menggunakan fakta bahwa dua titik menentukan polinomial linear, atau berderajat-1, unik. Yang kedua, kami mengandalkan fakta bahwa tiga titik menentukan derajat unik-2, atau kuadratik, polinomial. Dan jika Anda ingin mengirim pesan dengan panjang 10, cukup kodekan pesan tersebut sebagai koefisien 10 dari fungsi polinomial derajat-9. Setelah Anda memiliki fungsi, hitung 10 publik y-nilai dengan mengevaluasi fungsi pada 10 pribadi yang telah disepakati sebelumnya x-nilai. Setelah Anda melakukannya, Anda dapat melewatinya dengan aman y-koordinat di depan umum untuk penerima Anda untuk memecahkan kode. Dalam praktiknya, kode Reed-Solomon sedikit lebih kompleks dari ini, menggunakan jenis koefisien dan skema terjemahan yang lebih canggih, tetapi ide dasarnya sama.

Selain menjaga keamanan pesan Anda, kode Reed-Solomon juga menawarkan cara sederhana dan efisien untuk menangkap dan bahkan memperbaiki kesalahan. Ini penting kapan saja data ditransmisikan atau disimpan, karena selalu ada kemungkinan beberapa informasi akan hilang atau rusak.

Salah satu solusi untuk masalah ini adalah dengan mengirimkan salinan data tambahan. Misalnya, Zeke dapat mengirim pesan [14, 14, 14, 15, 15, 15] alih-alih [14, 15]. Selama Art mengetahui bahwa setiap bagian dari pesan dikirim dalam rangkap tiga, dia dapat memecahkan kode pesan dan memeriksa kesalahannya. Faktanya, jika dia menemukan kesalahan, dia memiliki peluang bagus untuk memperbaikinya. Jika Art menerima [14, 14, 24, 15, 15, 15], fakta bahwa tiga angka pertama berbeda mengingatkannya akan kesalahan, dan karena dua di antaranya adalah 14, dia dapat menebak bahwa 24 mungkin seharusnya menjadi a 14 juga. Alih-alih meminta agar pesan tersebut dikirim kembali, Art dapat melanjutkan decoding-nya. Ini adalah strategi yang efektif tetapi mahal. Berapa pun waktu, energi dan upaya yang diperlukan untuk mengirim n sepotong informasi, ini membutuhkan tiga kali lipat.

Tapi matematika di balik kode Reed-Solomon menawarkan alternatif yang efisien. Alih-alih mengirim banyak salinan dari setiap bagian data, Anda cukup mengirim satu poin tambahan! Jika titik tambahan itu cocok dengan polinomial Anda, maka informasinya benar. Jika tidak, ada kesalahan.

Untuk melihat cara kerjanya, misalkan Anda ingin mencentang pesan “TIDAK” pada contoh pertama. Zeke hanya dapat mengirim tambahan y-koordinat 155. Dengan asumsi dia dan Art menyetujui pribadi ketiga x-berkoordinasi sebelumnya, katakanlah x = 10, Art dapat mencocokkan poin ketiga ini dengan baris yang dia dekodekan. Saat dia pasang x = 10 ke dalam y = 14x +15 dan melihat bahwa hasilnya adalah 155, dia tahu tidak ada kesalahan dalam transmisi.

Ini tidak hanya berfungsi untuk garis. Untuk memungkinkan Zeke mencentang "BAD" pada contoh kedua, Art dapat mengirim y = 25. Jika mereka sudah sepakat bahwa 3 adalah extra private x-koordinat, Zeke bisa pasang x = 3 ke dalam fungsi kuadratnya y = 2x² + x + 4 dan verifikasi bahwa titik (3, 25) cocok, sekali lagi mengonfirmasi transmisi bebas kesalahan hanya dengan satu titik lagi.

Dan poin ekstra itu berpotensi memperbaiki kesalahan juga. Jika kesalahan terdeteksi dan penerima tidak dapat membuat fungsi polinomial yang berisi pesan, mereka dapat membuat polinomial "paling cocok" menggunakan teknik regresi. Seperti garis yang paling cocok di kelas statistik, ini adalah fungsi polinomial yang secara matematis ditentukan paling cocok dengan titik yang diberikan, meskipun tidak melewati semuanya. Bergantung pada struktur pesan dan seberapa banyak informasi tambahan yang Anda kirim, polinomial yang paling cocok ini dapat membantu Anda merekonstruksi polinomial yang benar — dan dengan demikian pesan yang benar — bahkan dari informasi yang rusak.

Efisiensi dalam mentransmisikan dan memperbaiki komunikasi ini menjelaskan mengapa NASA menggunakan kode Reed-Solomon dalam misinya ke bulan dan Mars. Dan itu memberi Anda sesuatu untuk direnungkan saat Anda menyelesaikan sistem persamaan Anda berikutnya. Seperti yang Anda tebak, periksa atau hilangkan jalan Anda menuju solusi, pikirkan kekuatan dan keanggunan kode Reed-Solomon dan semua rahasia yang mungkin diungkapkan oleh sistem Anda.

Latihan

1. Dengan menggunakan skema yang sama yang mereka gunakan di kelas, Art memposting nomor publik 33 dan 57 untuk didekode oleh Zeke. Apa pesannya?

2. Bagaimana Art dan Zeke dapat memastikan sistem persamaan yang dihasilkan dari bilangan pribadi mereka x = 3 dan x = 6 akan selalu punya solusi?

3. Menanggapi pesan Art "BAD" tentang tes bahasa Inggris, Zeke mengirimkan kembali [90, 387, 534]. Dengan asumsi mereka menggunakan skema yang sama dengan yang mereka gunakan di kelas, apa pesannya?

4. Lola mengirimi Anda pesan dua huruf plus satu nomor pengecekan kesalahan menggunakan kode Reed-Solomon dan sandi alfabet sederhana yang sama yang digunakan oleh Art dan Zeke. Anda telah diam-diam menyetujui x-koordinat 1, 3 dan 10 terlebih dahulu, dan Lola mengirimkan nomor publik [27, 43, 90]. Apakah pesan tersebut mengandung kesalahan?