พีชคณิตพื้นฐานเบื้องหลังรหัสลับและการสื่อสารในอวกาศ

การสำรวจอวกาศต้องใช้ความแม่นยำอย่างมาก เมื่อคุณนำรถโรเวอร์ลงจอดบนดาวอังคาร 70 ล้านไมล์จากสถานีบริการที่ใกล้ที่สุด คุณต้องเพิ่มประสิทธิภาพสูงสุดและเตรียมพร้อมสำหรับสิ่งที่ไม่คาดคิด สิ่งนี้ใช้กับทุกอย่างตั้งแต่การออกแบบยานอวกาศไปจนถึงการส่งข้อมูล: ข้อความที่ส่งกลับมายังโลกเป็นกระแสคงที่ที่ 0 และ 1 นั้นจะต้องมีข้อผิดพลาด ดังนั้นคุณต้องสามารถระบุและแก้ไขได้โดยไม่ต้องเสียเวลาและพลังงานอันมีค่า

นั่นคือที่มาของคณิตศาสตร์ นักคณิตศาสตร์ได้คิดค้นวิธีอันชาญฉลาดในการส่งและจัดเก็บข้อมูล วิธีหนึ่งที่ใช้ได้ผลอย่างน่าประหลาดใจ รหัสรีด-โซโลมอนซึ่งสร้างจากพีชคณิตพื้นฐานเดียวกับที่นักเรียนเรียนในโรงเรียน ลองมาเรียนวิชาคณิตศาสตร์เพื่อดูว่ารหัส Reed-Solomon ช่วยส่งและรักษาความปลอดภัยข้อมูลในขณะที่แก้ไขข้อผิดพลาดราคาแพงที่ปรากฏขึ้นได้อย่างไร

นักเรียนสองคน Art และ Zeke กำลังแลกเปลี่ยนข้อความลับในชั้นเรียนคณิตศาสตร์ของ Ms. Al-Jabr อาร์ตแฉโน้ตล่าสุดของซีค เผยเลข 57 และ 99 รู้ทั้งรู้ว่าต้องจัดหา x- พิกัด 3 และ 6 เพื่อสร้างจุด (3, 57) และ (6, 99) Art เสียบแต่ละจุดลงในสมการเชิงเส้น y = Ax + B และสร้างระบบสมการต่อไปนี้:

57 = 3A + B

99 = 6A + B

ในการถอดรหัสข้อความ Art จะต้องแก้ปัญหา A และ B. เขาเริ่มต้นด้วยการลบสมการแรกออกจากสมการที่สอง:

สิ่งนี้จะกำจัด B. การหารทั้งสองข้างของสมการใหม่ด้วย 3 จะบอกอาร์ตว่า A = 14 แล้วแทนค่านี้กลับเข้าไปในสมการแรก จะได้ 57 = 3 × 14 + Bให้ B = 15

ตอนนี้อาร์ตรู้แล้วว่าเส้นที่ผ่าน (3, 57) และ (6, 99) อธิบายโดยสมการ y = 14x + 15. แต่เขารู้ด้วยว่าในรหัสรีด-โซโลมอน ข้อความลับซ่อนอยู่ในค่าสัมประสิทธิ์ เขาถอดรหัสข้อความของซีคโดยใช้รหัสตัวอักษรที่ตกลงกันง่ายๆ: 14 คือ “N” และ 15 คือ “O” ซึ่งบอกอาร์ตว่า ไม่ วันนี้ซีคเล่นวิดีโอเกมหลังเลิกเรียนไม่ได้

ความลับของรหัส Reed-Solomon ที่เรียบง่ายนี้เริ่มต้นด้วยข้อเท็จจริงพื้นฐานสองประการของรูปทรงเรขาคณิต ประการแรก ผ่านจุดสองจุดใด ๆ จะมีเส้นที่ไม่ซ้ำกัน ประการที่สองสำหรับค่าสัมประสิทธิ์ A และ B, ทุกบรรทัด (ที่ไม่ใช่แนวตั้ง) สามารถเขียนในแบบฟอร์มได้ y = Ax + B. ข้อเท็จจริงทั้งสองนี้รับประกันได้ว่าหากคุณรู้จุดสองจุดบนเส้นตรง คุณจะหาเจอ A และ Bและถ้าคุณรู้ A และ Bคุณรู้จุดทั้งหมดบนบรรทัด กล่าวโดยย่อ การมีข้อมูลชุดใดชุดหนึ่งเทียบเท่ากับการรู้บรรทัด

รหัส Reed-Solomon ใช้ประโยชน์จากชุดข้อมูลที่เทียบเท่ากันเหล่านี้ ข้อความลับถูกเข้ารหัสเป็นค่าสัมประสิทธิ์ A และ Bและจุดของเส้นจะถูกแบ่งออกเป็นส่วนๆ ซึ่งบางส่วนจะถูกส่งต่อสาธารณะ และบางส่วนจะถูกเก็บไว้เป็นส่วนตัว ในการถอดรหัสข้อความ คุณเพียงแค่รวบรวมชิ้นส่วนต่างๆ และนำกลับมารวมกัน และทั้งหมดที่ต้องมีก็คือพีชคณิตง่ายๆ

ชิ้นส่วนของซีคคือหมายเลข 57 และ 99 ซึ่งเขาส่งให้อาร์ท ตัวเลขเหล่านี้เป็นส่วนสาธารณะของข้อความ ศิลปะนำสิ่งเหล่านี้มารวมกับชิ้นที่ 3 และ 6 ของเขาเองเพื่อสร้างจุด (3, 57) และ (6, 99) ขึ้นมาใหม่ ในที่นี้ เลข 3 และเลข 6 เป็นส่วนส่วนตัวของข้อความ ซึ่ง Art และ Zeke ตกลงกันไว้ล่วงหน้า

จุดสองจุดอยู่บนเส้นตรง และในการถอดรหัสข้อความ คุณเพียงแค่ต้องหาสมการของเส้นนั้น เสียบแต่ละจุดเข้าไป y = Ax + B ให้ระบบสมการสองสมการเกี่ยวกับเส้นตรงที่ต้องเป็นจริงทั้งคู่ ตอนนี้กลยุทธ์ตรงไปตรงมา: แก้ไขระบบ กำหนดบรรทัด และถอดรหัสข้อความ

ในชั้นเรียนพีชคณิต คุณอาจได้เรียนรู้วิธีการต่างๆ มากมายในการแก้ระบบสมการ เช่น การสร้างกราฟ การคาดเดาและการตรวจสอบ และการแทนที่ Art ใช้การกำจัด ซึ่งเป็นวิธีที่คุณจัดการสมการเชิงพีชคณิตเพื่อกำจัดตัวแปรทีละตัว แต่ละครั้งที่คุณกำจัดตัวแปร ระบบจะแก้ปัญหาได้ง่ายขึ้นเล็กน้อย

เช่นเดียวกับแผนการเข้ารหัสอื่น ๆ มันเป็นการผสมผสานที่ชาญฉลาดของข้อมูลสาธารณะและข้อมูลส่วนตัวที่รักษาความปลอดภัยให้กับข้อความ ซีคสามารถตะโกนหมายเลข 57 และ 99 ไปทั่วห้องเรียนได้ และมันจะไม่เป็นอันตรายต่อความปลอดภัยของข้อความที่เขาส่งถึงอาร์ท (แม้ว่ามันอาจทำให้เขามีปัญหากับคุณอัล-จาเบอร์) นั่นเป็นเพราะไม่มีข้อมูลส่วนตัวที่เกี่ยวข้อง — x-พิกัด 3 และ 6 — เป็นไปไม่ได้ที่จะระบุสมการของเส้นตรง ตราบใดที่พวกเขารักษาคุณค่าเหล่านั้นไว้กับตัวเอง พวกเขาก็สามารถส่งข้อความลับในที่สาธารณะได้อย่างปลอดภัย

เส้น y = 14x + 15 ใช้ได้สำหรับการส่งคำว่า "ไม่" สองตัวอักษร แต่ถ้านักเรียนต้องการแบ่งปันความลับที่ยาวกว่านี้ล่ะ นี่คือที่มาของพลังของพีชคณิต เรขาคณิต และระบบสมการเชิงเส้น

สมมติว่าซีคอยากรู้ว่าอาร์ตคิดว่าเขาจะทำได้ดีแค่ไหนในการทดสอบภาษาอังกฤษในวันพรุ่งนี้ อาร์ตแปลงคำตอบที่เป็นตัวอักษรสามตัวของเขาเป็นตัวเลข 14, 59 และ 82 แล้วส่งต่อให้ซีค นักเรียนตกลงกันล่วงหน้าว่าเมื่อใช้รหัส Reed-Solomon ที่มีความยาว 3 ตัวเลขส่วนตัวของพวกเขาคือ 2, 5 และ 6 ดังนั้น Zeke จึงนำชิ้นส่วนมารวมกันเพื่อสร้างจุด (2, 14), (5, 59) และ (6, 82).

ตอนนี้ ไม่มีฟังก์ชันเชิงเส้นที่ผ่านจุดทั้งสามนี้ แต่มีฟังก์ชันกำลังสองเฉพาะที่ทำ และเนื่องจากทุกฟังก์ชันกำลังสองสามารถเขียนในรูปได้ y = Ax² + Bx + Cสามารถใช้วิธีทั่วไปเดียวกันได้ ความแตกต่างเพียงอย่างเดียวคือขนาดของระบบ

เสียบแต่ละจุดเข้าไป y = Ax² + Bx + C ให้สมการหนึ่งสมการ ดังนั้นจุดสามจุดจึงสร้างระบบสมการสามสมการต่อไปนี้:

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

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

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

ระบบสมการ XNUMX สมการที่มีนิรนาม XNUMX สมการต้องการงานแก้มากกว่าระบบสมการ XNUMX สมการที่มีนิรนาม XNUMX สมการ แต่เป้าหมายเหมือนกัน: รวมคู่สมการอย่างชาญฉลาดเพื่อกำจัดตัวแปร

ตัวอย่างเช่น หากคุณลบสมการแรกออกจากสมการที่สอง คุณจะได้สมการใหม่ 45 = 21A + 3B. ในทำนองเดียวกัน หากคุณลบสมการที่สองจากสมการที่สาม คุณจะได้ 23 = 11A + B. การจัดการเกี่ยวกับพีชคณิตเหล่านี้สร้างระบบใหม่:

45 = 21A + 3B

23 = 11A + B

ตอนนี้คุณมีระบบ "สองต่อสอง": สองสมการที่มีสองค่าที่ไม่รู้จัก ในการแก้สมการ คุณสามารถคูณสมการที่สองด้วย −3 และเพิ่มเข้าไปในสมการแรก:

สังเกตว่าการกำจัดซ้ำๆ ได้เปลี่ยนระบบเดิมของสามสมการให้เป็นสมการเดียวที่แก้ได้ง่ายๆ ได้อย่างไร: A = 2. ทำงานย้อนหลังได้ A = 2 ลงในหนึ่งในสมการในระบบสองต่อสองเพื่อหา B = 1 แล้วแทนค่าทั้งสองลงในสมการเดิมจะได้ C = 4. หลังจากใช้รหัสตัวอักษรอย่างง่ายใน 2, 1 และ 4 ซีครู้ว่าอาร์ตกำลังจะทำข้อสอบภาษาอังกฤษวันพรุ่งนี้ว่า “แย่” อย่างน้อยเขาก็ได้ฝึกพีชคณิตมากมาย

ด้วยข้อเท็จจริงพิเศษเกี่ยวกับฟังก์ชันพหุนาม คุณสามารถส่งข้อความที่มีความยาวเท่าใดก็ได้โดยใช้รหัสรีด-โซโลมอน กุญแจสำคัญคือ: กำหนดให้ใด ๆ n จุดในระนาบที่แตกต่างกัน x-พิกัด มีพหุนามเฉพาะของ "องศา" n - 1 ที่ผ่านพวกเขา ดีกรีของพหุนามคือพลังสูงสุดของตัวแปรในนิพจน์ ดังนั้น ฟังก์ชันกำลังสองก็เช่น Ax² + Bx + C มีดีกรีเป็น 2 เนื่องจากอำนาจสูงสุดของ x คือ 2 และฟังก์ชันเชิงเส้นมีดีกรี 1 เนื่องจากในสมการ y = Ax + Bพลังสูงสุดของ x คือ 1

ในตัวอย่างแรก เราใช้ข้อเท็จจริงที่ว่าจุดสองจุดกำหนดพหุนามเชิงเส้นเฉพาะหรือดีกรี-1 ประการที่สอง เราอาศัยความจริงที่ว่าจุดสามจุดกำหนดพหุนามดีกรี-2 หรือกำลังสองที่ไม่ซ้ำกัน และถ้าคุณต้องการส่งข้อความที่มีความยาว 10 เพียงเข้ารหัสข้อความเป็นค่าสัมประสิทธิ์ 10 ของฟังก์ชันพหุนามดีกรี-9 เมื่อคุณมีฟังก์ชันของคุณแล้ว ให้คำนวณ 10 สาธารณะ y- ค่าโดยการประเมินฟังก์ชั่นที่ตกลงกันไว้ก่อนหน้านี้ 10 ส่วนตัว x- ค่า เมื่อคุณทำได้แล้ว คุณก็จะผ่านมันไปได้อย่างปลอดภัย y-ประสานงานในที่สาธารณะเพื่อให้ผู้รับของคุณถอดรหัส ในทางปฏิบัติ รหัส Reed-Solomon นั้นซับซ้อนกว่านี้เล็กน้อย โดยใช้ค่าสัมประสิทธิ์และรูปแบบการแปลที่ซับซ้อนกว่า แต่แนวคิดพื้นฐานก็เหมือนกัน

นอกจากการรักษาข้อความของคุณให้ปลอดภัยแล้ว รหัส Reed-Solomon ยังนำเสนอวิธีที่ง่ายและมีประสิทธิภาพในการตรวจจับและแม้แต่แก้ไขข้อผิดพลาด นี่เป็นสิ่งสำคัญทุกครั้งที่มีการส่งหรือจัดเก็บข้อมูล เนื่องจากมีโอกาสเสมอที่ข้อมูลบางส่วนจะสูญหายหรือเสียหาย

วิธีหนึ่งในการแก้ปัญหานี้คือเพียงแค่ส่งสำเนาข้อมูลเพิ่มเติม ตัวอย่างเช่น Zeke สามารถส่งข้อความ [14, 14, 14, 15, 15, 15] แทน [14, 15] ตราบใดที่อาร์ตรู้ว่าทุกส่วนของข้อความถูกส่งเป็นสามเท่า เขาสามารถถอดรหัสข้อความและตรวจสอบข้อผิดพลาดได้ ในความเป็นจริงหากเขาพบข้อผิดพลาดใด ๆ เขามีโอกาสที่จะแก้ไขให้ถูกต้อง ถ้าอาร์ตได้รับ [14, 14, 24, 15, 15, 15] ข้อเท็จจริงที่ว่าตัวเลขสามตัวแรกต่างกันจะเตือนเขาถึงข้อผิดพลาด และเนื่องจากตัวเลขสองตัวคือ 14 เขาเดาได้ว่า 24 น่าจะเป็น 14 เช่นกัน แทนที่จะขอข้อความให้ไม่พอใจ Art สามารถถอดรหัสของเขาต่อไปได้ นี่เป็นกลยุทธ์ที่มีประสิทธิภาพแต่มีค่าใช้จ่ายสูง ไม่ว่าจะต้องใช้เวลา แรงกายแรงใจ ในการส่งสิ่งใด n ต้องใช้ข้อมูลมากเป็นสามเท่า

แต่คณิตศาสตร์ที่อยู่เบื้องหลังรหัส Reed-Solomon เสนอทางเลือกที่มีประสิทธิภาพ แทนที่จะต้องส่งสำเนาข้อมูลทุกชิ้นหลายชุด คุณสามารถส่งเพิ่มอีกจุดเดียวได้! หากจุดเพิ่มเติมนั้นตรงกับพหุนามของคุณ แสดงว่าข้อมูลนั้นถูกต้อง หากไม่เป็นเช่นนั้น แสดงว่ามีข้อผิดพลาด

หากต้องการดูวิธีการทำงาน สมมติว่าคุณต้องการตรวจสอบข้อความ “NO” ในตัวอย่างแรก ซีคสามารถส่งเพิ่มเติมได้ y-ประสานงาน 155 สมมติว่าเขาและอาร์ตตกลงในเอกชนรายที่สาม x- ประสานงานล่วงหน้าพูด x = 10, Art สามารถตรวจสอบจุดที่สามนี้กับบรรทัดที่เขาถอดรหัสได้ เมื่อเขาเสียบ x = 10 เข้าไป y = 14x + 15 และเห็นว่าผลลัพธ์คือ 155 เขารู้ว่าไม่มีข้อผิดพลาดในการส่ง

วิธีนี้ใช้ไม่ได้กับสายเท่านั้น เพื่อให้ Zeke ตรวจสอบ "BAD" ในตัวอย่างที่สอง Art สามารถส่ง y = 25. ถ้าพวกเขาตกลงให้ 3 เป็นไพรเวทพิเศษ x-ประสานงานกัน เซเก้ เสียบได้ x = 3 เป็นฟังก์ชันกำลังสอง y = 2x² + x + 4 และตรวจสอบว่าจุด (3, 25) เหมาะสม ยืนยันการส่งสัญญาณอีกครั้งโดยปราศจากข้อผิดพลาดด้วยอีกเพียงจุดเดียว

และจุดพิเศษนั้นอาจแก้ไขข้อผิดพลาดได้เช่นกัน หากตรวจพบข้อผิดพลาดและเครื่องรับไม่สามารถสร้างฟังก์ชันพหุนามที่มีข้อความได้ พวกเขาสามารถสร้างพหุนามที่ "เหมาะสมที่สุด" แทนโดยใช้เทคนิคการถดถอย เช่นเดียวกับเส้นที่เหมาะสมที่สุดในคลาสสถิติ นี่คือฟังก์ชันพหุนามที่ถูกกำหนดทางคณิตศาสตร์เพื่อให้พอดีกับจุดที่ให้ไว้มากที่สุด แม้ว่าจะไม่ผ่านทั้งหมดก็ตาม ขึ้นอยู่กับโครงสร้างของข้อความและจำนวนข้อมูลเพิ่มเติมที่คุณส่ง พหุนามที่เหมาะสมที่สุดนี้สามารถช่วยคุณสร้างพหุนามที่ถูกต้องขึ้นใหม่ — และด้วยเหตุนี้จึงเป็นข้อความที่ถูกต้อง — แม้จากข้อมูลที่เสียหาย

ประสิทธิภาพในการส่งและแก้ไขการสื่อสารนี้อธิบายว่าทำไม NASA จึงใช้รหัส Reed-Solomon ในภารกิจไปยังดวงจันทร์และดาวอังคาร และมันทำให้คุณต้องไตร่ตรองเมื่อคุณแก้สมการระบบต่อไป ในขณะที่คุณคาดเดา ตรวจสอบหรือกำจัดวิธีการแก้ปัญหาของคุณ ให้นึกถึงพลังและความสง่างามของรหัส Reed-Solomon และความลับทั้งหมดที่ระบบของคุณอาจเปิดเผย

การออกกำลังกาย

1. ใช้รูปแบบเดียวกับที่ใช้ในชั้นเรียน Art โพสต์หมายเลขสาธารณะ 33 และ 57 เพื่อให้ Zeke ถอดรหัส มีอะไรข้อความ?

2. Art และ Zeke แน่ใจได้อย่างไรว่าระบบสมการที่เป็นผลมาจากตัวเลขส่วนตัวของพวกเขา x = 3 และ x = 6 จะมีทางออกเสมอ?

3. ในการตอบกลับข้อความ "BAD" ของ Art เกี่ยวกับการทดสอบภาษาอังกฤษ Zeke ส่ง [90, 387, 534] กลับมา สมมติว่าพวกเขาใช้รูปแบบเดียวกับที่ใช้ในชั้นเรียน ข้อความของเขาคืออะไร

4. Lola ส่งข้อความสองตัวอักษรพร้อมหมายเลขตรวจสอบข้อผิดพลาดหนึ่งหมายเลขโดยใช้รหัส Reed-Solomon และรหัสตัวอักษรแบบเดียวกับที่ Art และ Zeke ใช้ คุณได้ตกลงอย่างลับๆ x- พิกัด 1, 3 และ 10 ล่วงหน้า และ Lola ส่งหมายเลขสาธารณะ [27, 43, 90] ข้อความมีข้อผิดพลาดหรือไม่?