ประกาศการแปล

เนื้อหาบางส่วนของบทความนี้ได้รับการแปลโดยได้รับความช่วยเหลือจาก GPT คำแปลอาจมีความคลาดเคลื่อน และคำศัพท์เฉพาะหรือบริบททางวัฒนธรรมบางส่วนอาจเข้าใจได้ยากเนื่องจากความแตกต่างทางภาษาและวัฒนธรรม หากต้องการตรวจสอบถ้อยคำที่ถูกต้อง โปรดอ่านฉบับต้นฉบับ หากมีข้อสงสัยเกี่ยวกับบริบททางวัฒนธรรมหรือเนื้อหา สามารถติดต่อผู้เขียนผ่านช่องทางติดต่อในแถบด้านข้างได้ เรายินดีช่วยอธิบาย

เกมทายตัวเลข

คนสามคนเดินทาง เหลือเศษสองเจ็ดสิบหา
ห้าต้นเหมยผลิบาน เหลือยี่สิบเอ็ดกิ่ง
ลูกเจ็ดกลับมาพร้อมหน้า ตรงกับครึ่งเดือนพอดี
หารด้วยหนึ่งร้อยห้า แล้วคำตอบจะปรากฏ

——— เฉิง ต้าจุ้ย（程大位）, ตำรารวมศิลปะการคำนวณ (ราชวงศ์หมิง)

ครั้งแรกที่ผมสนใจ {{ann|“ทฤษฎีบทเศษเหลือของจีน”|ทฤษฎีบทเศษเหลือของจีน (Chinese Remainder Theorem)|ทฤษฎีบทสำคัญในสาขาทฤษฎีจำนวน ใช้ในการหาคำตอบของระบบสมการเชิงโมดูลาร์ และเป็นพื้นฐานของคณิตศาสตร์และวิทยาการเข้ารหัสสมัยใหม่|}} ก็เพราะชื่อของมันโดดเด่นมากเมื่อเทียบกับทฤษฎีบทอื่น ๆ แม้แต่วิธีแก้ที่เรียกว่า {{ann|“วิธีหาค่าผกผันตามสูตรต้าเหยี่ยน ของฉินจิ่วเสา”|วิธีหาค่าผกผันตามสูตรต้าเหยี่ยน ของฉินจิ่วเสา|อัลกอริทึมสำหรับหาค่าผกผันเชิงโมดูลาร์ คิดค้นโดยนักคณิตศาสตร์จีน ฉินจิ่วเสา (秦九韶) ในคริสต์ศตวรรษที่ 13|}} ก็เป็นชื่อที่สง่างาม และกระตุ้นจินตนาการของนักเรียนมัธยมได้อย่างไม่รู้จบ ต้นกำเนิดของมรดกทางคณิตศาสตร์อันน่าทึ่งนี้อยู่ใน คัมภีร์คณิตศาสตร์ของซุนจื่อ ซึ่งรจนาขึ้นในช่วง {{ann|ราชวงศ์เหนือและใต้|ราชวงศ์เหนือและใต้|ช่วงเวลาของประวัติศาสตร์จีนระหว่างคริสต์ศตวรรษที่ 5–6 ก่อนการรวมแผ่นดินในสมัยราชวงศ์สุย|}} ผู้ประพันธ์ไม่ใช่ ซุนอู่ แม่ทัพแห่งรัฐอู๋ในปลายยุคชุนชิว ผู้เป็นที่รู้จักจากตำรา ศิลปะแห่งสงคราม (The Art of War) หากแต่เป็นนักคณิตศาสตร์อีกผู้หนึ่งที่มีชื่อว่า ซุนจื่อ โจทย์ {{ann|“ไก่กับกระต่ายอยู่ในกรงเดียวกัน”|ไก่กับกระต่ายอยู่ในกรงเดียวกัน|โจทย์คณิตศาสตร์โบราณของจีน โดยกำหนดจำนวนหัวและจำนวนขาของไก่กับกระต่าย แล้วให้หาว่ามีไก่และกระต่ายอย่างละกี่ตัว ตัวอย่างเช่น หากมี 35 หัว 94 ขา จะมีไก่ 23 ตัว และกระต่าย 12 ตัว โจทย์นี้เป็นที่รู้จักอย่างแพร่หลายในประเทศจีน และนักเรียนจีนแทบทุกคนเคยพบในช่วงวัยเรียน|}} ซึ่งถือเป็นโจทย์คณิตศาสตร์คลาสสิกที่คนจีนแทบทุกคนรู้จัก ก็ปรากฏอยู่ในหนังสือเล่มนี้เช่นกัน

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

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

สมมติว่าคุณย้อนเวลากลับไปยังยุคราชวงศ์เหนือและใต้ ถูกนายทหารจับในฐานะสายลับ นายทหารบอกว่าถ้าคุณรู้ว่าค่ายทหารมีคนอยู่กี่คน ก็แปลว่าคุณเป็นชาวฮั่นและจะปล่อยตัวไป แต่ถ้าไม่รู้ คุณก็คือสายลับที่ถูกส่งมาจากชาวหู ทว่า คุณมองเห็นได้เพียงสามอย่าง:

• จัดทหารเป็นแถวละ 3 คน เหลือ 2 คน
• จัดเป็นแถวละ 5 คน เหลือ 3 คน
• จัดเป็นแถวละ 7 คน เหลือ 2 คน

คุณจะเดาอย่างไร?

ปฏิกิริยาแรกของคนส่วนใหญ่น่าจะเป็น: ลองไปทีละตัว

ลอง 13 ไม่ใช่ ลอง 17 ไม่ใช่ ลอง 19 ไม่ใช่… ทดลองต่อไปเรื่อย ๆ จนกว่าจะพบตัวเลขที่ตรงกับทั้งสามเงื่อนไขพร้อมกัน

แน่นอนว่าทำแบบนั้นได้ เพียงแต่วิธีนี้อาจเป็นไปไม่ได้ในทางปฏิบัติ คุณอาจถูกตัดหัวหลังจากลองเพียงสามครั้ง และยังไม่ต้องพูดถึงกรณีที่มีคำตอบจำนวนมากซึ่งตรงกับเงื่อนไขทั้งสาม เพราะในโลกนี้มีจำนวนไม่รู้จบที่หารด้วย 3 แล้วเหลือเศษ 2 และมีจำนวนไม่รู้จบที่หารด้วย 5 แล้วเหลือเศษ 3 เช่นกัน…

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

ลองทำจริงกันดีกว่า

เริ่มจาก 1 แล้วหาจำนวนที่ “หารด้วย 3 เหลือเศษ 2” จะได้ 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32…

จากนั้นดูว่าในจำนวนเหล่านี้ มีจำนวนใด “หารด้วย 5 เหลือเศษ 3” บ้าง: 8, 23, 38…

จากนั้นดูว่าในกลุ่มนี้ มีจำนวนใด “หารด้วย 7 เหลือเศษ 2”: 23

คำตอบคือ 23

คำตอบนี้ให้ความรู้สึกยินดีปนไม่แน่ใจแบบหนึ่ง คุณหาเจอแล้ว แต่จะรู้ได้อย่างไรว่าหลังจากนั้นไม่มีคำตอบอื่นอีก

ผู้สร้าง: Cmglee, วิกิมีเดียคอมมอนส์, CC BY-SA 4.0

อย่าลองทีละตัว

เพราะเราคุ้นเคยเกินไปกับการมองจำนวนเต็มว่าเป็นสิ่งที่ “เรียงต่อกันทีละตัว”

1, 2, 3, 4, 5… เหมือนบันไดที่ทอดสูงขึ้นทีละขั้น ดังนั้นเมื่อเจอเงื่อนไขอย่าง “หารด้วย 3 เหลือเศษ 2, หารด้วย 5 เหลือเศษ 3, หารด้วย 7 เหลือเศษ 2” สัญชาตญาณจึงบอกว่า: งั้นก็ตรวจสอบตั้งแต่ต้นไปเรื่อย ๆ

แต่ปัญหาของวิธีนี้เห็นได้ชัดเจน: บันไดยาวเกินไป

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

เรื่องนี้คล้ายกับการคำนวณวันในปฏิทิน

วันนี้เป็นวันศุกร์ อีก 1 วันเป็นวันเสาร์ อีก 2 วันเป็นวันอาทิตย์ แล้วอีก 100 วันจะเป็นวันอะไร? ก็ไล่นับไปข้างหน้าสิ นับทีละวันจนครบหนึ่งร้อยวัน ถ้านับผิดก็กลับไปเริ่มใหม่

เศษเหลือได้แต่มองคุณอย่างเศร้าใจอยู่ข้าง ๆ

เศษเหลืออาจช่วยบอกไม่ได้ว่าอีก 100 วันจะเป็นวันอะไร แต่ช่วยบอกได้ว่าจำนวนเต็มนั้นอยู่ ณ ตำแหน่งใดในระบบวัฏจักรบางอย่าง

เศษเหลือช่วยเราได้อย่างไร?

ผมชอบแนวคิดเรื่องการคำนวณมอดุลาร์มาก มันคือการนำจำนวนหนึ่งไปหารด้วยอีกจำนวนหนึ่งแล้วพิจารณาเศษที่เหลือ แนวคิดนี้มีบรรยากาศใกล้ตัวอย่างยิ่ง

กลับมาที่ปัญหาเรื่องวันในสัปดาห์เมื่อครู่

วันนี้เป็นวันศุกร์ อีก 7 วันก็ยังเป็นวันศุกร์ อีก 14 วันก็ยังเป็นวันศุกร์ อีก 15 วันเหลือเศษ 1 วัน ถอยกลับไปหนึ่งวันก็เป็นวันเสาร์ อีก 20 วันนั้น 3 คูณ 7 ได้ 21 ขาดอีกหนึ่งวัน จึงถอยกลับไปหนึ่งวันและได้วันพฤหัสบดี ส่วน 100 วันนั้น หารด้วย 7 ได้ 14 เหลือเศษ 2 จึงเป็นวันอาทิตย์ ดังนั้นระบบวันในสัปดาห์จึงเป็นวัฏจักรโดยเนื้อแท้ คุณไม่จำเป็นต้องรู้ว่าผ่านไปกี่วัน ขอเพียงรู้ว่า “หารด้วย 7 เหลือเศษเท่าไร” ก็พอ

ลองดูนาฬิกาเป็นอีกตัวอย่าง

ตอนนี้เป็นเวลา 3 นาฬิกา อีก 12 ชั่วโมงก็ยังเป็น 3 นาฬิกา นาฬิกาไม่ใช่เส้นตรงที่ทอดยาวไปไม่มีที่สิ้นสุด แต่เป็นวงกลม เวลาเดินไปบนวงกลมนั้น และสุดท้ายก็วนกลับมาเสมอ หากต้องการรู้เวลา แค่เหลือบมองนาฬิกา ผมเชื่อว่าไม่มีคนปกติคนไหนมองเห็นเลข 12 แล้วเริ่มนับย้อนหลังว่าผ่านไปกี่ชั่วโมงเพื่อคำนวณว่าตอนนี้กี่โมง แต่เราจะมองออกทันทีว่าเข็มชี้อยู่ตรงตำแหน่งใดบนหน้าปัด แม้หน้าปัดนั้นจะไม่มีตัวเลขก็ตาม

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

คณิตศาสตร์ดึงเรื่องนี้ออกมาเป็นนามธรรมและเรียกว่า “มอดุลัส” มอดุลัสหนึ่งตัวก็คือวัฏจักรหนึ่งรอบ ตัวอย่างเช่น “หารด้วย 7 แล้วพิจารณาเศษ” เราเรียกว่า “มอดุลัส 7 ($mod$ $7$)” ซึ่งเป็นการพูดในโลกของวันในสัปดาห์ ส่วน “หารด้วย 12 แล้วพิจารณาเศษ” ก็คือการพูดในโลกของนาฬิกา หนึ่งวันมี 24 ชั่วโมง ดังนั้นสำหรับคนที่อดนอนจนถึงตีหนึ่งของวันถัดไป เวลานั้นอาจเรียกได้ว่าเป็น 25 นาฬิกา แต่จริง ๆ แล้ว 25 นาฬิกา ≡ 1 นาฬิกา (mod 24)

ดังนั้น จำนวนหนึ่งจึงไม่ได้เป็นเพียงตัวมันเองอีกต่อไป เมื่ออยู่ในมอดุลัสที่ต่างกัน มันจะแสดงแง่มุมที่แตกต่างกันออกมา

เรื่องนี้คล้ายกับคนคนหนึ่ง

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

จำนวนเต็มหนึ่งจำนวนมีหน้าตาอย่างไรในมอดุลัส 3 มีหน้าตาอย่างไรในมอดุลัส 5 และมีหน้าตาอย่างไรในมอดุลัส 7 “เศษเหลือ” เหล่านี้ช่วยระบุตัวมันให้ชัดเจนขึ้น

จากตรงนี้เข้าสู่ทฤษฎีจำนวน

เกาส์กล่าวไว้ว่า:

คณิตศาสตร์คือราชินีแห่งวิทยาศาสตร์ และทฤษฎีจำนวนคือราชินีแห่งคณิตศาสตร์

แท้จริงแล้ว ทฤษฎีจำนวนก็คือการศึกษาจำนวนเต็ม

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

น่าอัศจรรย์จริง ๆ

การคำนวณมอดุลาร์เป็นหนึ่งในเครื่องมือสำคัญที่สุดของทฤษฎีจำนวน แคลคูลัสมีอนุพันธ์ พีชคณิตเชิงเส้นมีเมทริกซ์ เรขาคณิตมีพิกัด

ส่วนหนึ่งในเครื่องมือที่พบได้บ่อยที่สุดของทฤษฎีจำนวนก็คือมอดุลัส ในโลกของการคำนวณมอดุลาร์ จำนวนต่าง ๆ อาจถูกมองว่าเป็นจำนวนเดียวกัน เช่นเดียวกับ 25 นาฬิกา ≡ 1 นาฬิกา (mod 24) และวันที่แปดของสัปดาห์ ≡ วันจันทร์ (mod 7) ความสัมพันธ์แบบเท่าเทียมกันนี้เรียกว่า สมภาค (Congruence)

  graph TD

M["คณิตศาสตร์"]

M --> N["ทฤษฎีจำนวน"]
M --> FF["แคลคูลัส"]

N --> A["จำนวนเต็ม"]

A --> B["การหารลงตัว"]
B --> B1["ตัวหารร่วมมาก (GCD)"]
B --> B2["ตัวคูณร่วมน้อย (LCM)"]

A --> C["จำนวนเฉพาะ"]
C --> C1["การแยกตัวประกอบจำนวนเฉพาะ"]

B --> D["สมภาค (การคำนวณมอดุลาร์)"]


D --> E["ขั้นตอนวิธีแบบยุคลิด"]
E --> E1["ขั้นตอนวิธีแบบยุคลิดขยาย"]

D --> F["ทฤษฎีบทของออยเลอร์"]
D --> G["ทฤษฎีบทเล็กของแฟร์มาต์"]

D --> H["ทฤษฎีบทเศษเหลือของจีน"]

E1 --> H

H --> I["วิทยาการเข้ารหัสสมัยใหม่"]

I --> I1["RSA"]
I --> I2["ECC (การเข้ารหัสเส้นโค้งวงรี)"]
I --> I3["ลายเซ็นดิจิทัล"]
I3 --> I4["บล็อกเชน"]

กลับมาที่ปริศนา ในที่สุดก็มีสูตรปรากฏ

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

ดังนั้น ตอนนี้เราจะให้สูตรปรากฏขึ้น แต่จะค่อย ๆ ปรากฏทีละขั้น

สมมติว่าเราต้องการหาจำนวนเต็ม $(x)$ ที่สอดคล้องกับ:

$$x \equiv a_1 \pmod{m_1}$$$$x \equiv a_2 \pmod{m_2}$$$$\cdots$$$$x \equiv a_n \pmod{m_n}$$

กล่าวคือ $x$ หารด้วย $m_1$ เหลือเศษ $a_1$, หารด้วย $m_2$ เหลือเศษ $a_2$, … และหารด้วย $m_n$ เหลือเศษ $a_n$

ทฤษฎีบทเศษเหลือของจีนบอกเราว่า หากมอดุลัส $m_1,m_2,\dots,m_n$ ทุกคู่เป็นจำนวนที่ไม่เป็นตัวประกอบร่วมกัน ระบบสมการสมภาคนี้จะมีคำตอบเสมอ และภายใต้มอดุลัส

$$ M = m_1,m_2,\cdots,m_n $$

คำตอบนี้จะมีเพียงหนึ่งเดียว

“ทุกคู่ไม่เป็นตัวประกอบร่วมกัน” คืออะไร?

เราต้องการให้มอดุลัสเหล่านี้เป็นอิสระต่อกันมากที่สุด เพราะเราต้องการระบุตำแหน่งของจำนวนที่เฉพาะเจาะจง หากใช้ 6 และ 9 เป็นมอดุลัส ทั้งสองจำนวนมีตัวประกอบร่วมคือ 3 เศษที่ได้จึงเกิดการซ้อนทับกัน แบบนั้นจะไม่วุ่นวายไปหน่อยหรือ

ดังนั้น ตัวเลขที่เราใช้หารจะต้องไม่มีตัวประกอบร่วมกันเป็นคู่ ๆ ตัวอย่างเช่น 3 กับ 5 ไม่มีตัวประกอบร่วมกัน, 3 กับ 7 ก็ไม่มีตัวประกอบร่วมกัน และ 5 กับ 7 ก็เช่นกัน พวกมันไม่มีตัวประกอบร่วมกัน จึงไม่ทำให้โอกาสในการระบุตำแหน่งสูญเปล่า

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

ทำไมคำตอบจึง “มีเพียงหนึ่งเดียว”?

โปรดสังเกตว่า “มีเพียงหนึ่งเดียว” ในที่นี้ไม่ได้หมายความว่ามีจำนวนเต็มเพียงจำนวนเดียวที่สอดคล้องกับเงื่อนไขตลอดไป แต่หมายความว่าคำตอบมีเพียงหนึ่งเดียวภายใต้มอดุลัส $(M)$

กล่าวอีกอย่างคือ อาจมีจำนวนเต็มนับไม่ถ้วนที่สอดคล้องกับชุดเงื่อนไขเศษเหลือเดียวกัน แต่จำนวนเหล่านั้นต่างกันด้วยพหุคูณของ $(M)$ สำหรับโลกภายใต้มอดุลัส $(M)$ แล้ว พวกมันถือเป็นคำตอบเดียวกัน หรือก็คือสมภาคกัน

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

แนวคิดในการสร้างคำตอบคืออะไร?

คณิตศาสตร์ไม่ได้มอบเพียงข้อสรุป แต่ยังมอบเส้นทางสำหรับสร้างสะพานไปสู่ข้อสรุปนั้นด้วย

กำหนดให้

$$ M_i = \frac{M}{m_i} $$

กล่าวคือ นำผลคูณทั้งหมด $(M)$ มาหารด้วยมอดุลัสตัวที่ $(i)$ เพื่อให้ได้ส่วนที่เหลืออยู่นั้น

เนื่องจาก $M_i$ และ $m_i$ ไม่มีตัวประกอบร่วมกัน เราจึงสามารถหาจำนวนเต็ม $y_i$ ที่ทำให้

$$ M_i y_i \equiv 1 \pmod{m_i} $$

หมายความว่า เราต้องการทำให้ $(M_i)$ กลายเป็น 1 ในโลกภายใต้มอดุลัส $(m_i)$ เพียงคูณด้วยจำนวนที่เหมาะสม $(y_i)$ ก็ทำได้

ตอนนี้คำตอบสามารถเขียนได้เป็น:

$$ x \equiv \sum_{i=1}^n a_i M_i y_i \pmod{M} $$

ตรรกะของมันเรียบง่ายมาก เพราะเมื่อเรานำ $(M_i)$ ไปอยู่ในโลกภายใต้มอดุลัส $(m_j)$ ทุกพจน์ยกเว้นพจน์ที่ $(j=i)$ จะถูก $(m_j)$ หารลงตัวและกลายเป็น 0 เหลือเพียงพจน์ที่ตรงกัน ซึ่งมีค่าเท่ากับ $(a_i)$ พอดี

นี่เป็นโครงสร้างแบบ “กำหนดทิศทาง” ที่งดงามมาก แต่ละพจน์พูดกับมอดุลัสของตัวเองเท่านั้น และเงียบกับมอดุลัสของผู้อื่น

ขั้นตอนวิธีแบบยุคลิดขยายคืออะไร?

คุณจะสังเกตว่า ในการสร้างคำตอบด้านบน เราจำเป็นต้องหา $(y_i)$ หรือก็คือการหาผกผันการคูณ (การหาจำนวนที่เมื่อคูณกับจำนวนเดิมแล้วได้ผลลัพธ์เป็น 1 เช่น $2\times\frac12=1$ โดย $\frac12$ คือผกผันการคูณของ 2) แล้วจะหาได้อย่างไร?

ตรงนี้เองที่ขั้นตอนวิธีแบบยุคลิดขยายเข้ามามีบทบาท

พูดอย่างง่าย ขั้นตอนวิธีแบบยุคลิดเดิมใช้สำหรับหาตัวหารร่วมมาก ส่วนรูปแบบขยายจะบอกเพิ่มเติมว่า หากจำนวนสองจำนวนไม่มีตัวประกอบร่วมกัน เราสามารถเขียน 1 ให้อยู่ในรูปผลรวมเชิงจำนวนเต็มของทั้งสองจำนวนได้ กล่าวคือ สามารถหาจำนวนเต็ม $u,v$ ที่ทำให้

$$ au + bv = 1 $$

เมื่อสามารถเขียน 1 ออกมาได้ ผกผันการคูณก็จะปรากฏตามมา

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

แก่นแท้สมัยใหม่: คำนวณ 23 ออกมาให้ได้จริง

ตอนนี้เรามาแก้โจทย์ก่อนหน้านี้กัน:

$$ x \equiv 2 \pmod{3} $$$$ x \equiv 3 \pmod{5} $$$$ x \equiv 2 \pmod{7} $$

มอดุลัสคือ 3, 5 และ 7 ตามลำดับ และทุกคู่ไม่มีตัวประกอบร่วมกัน ดังนั้นจึงใช้ทฤษฎีบทเศษเหลือของจีนได้

เริ่มจากหาผลคูณทั้งหมด:

$$ M = 3 \times 5 \times 7 = 105 $$

จากนั้นคำนวณทีละตัว:

$$ M_1 = \frac{105}{3} = 35,\quad M_2 = \frac{105}{5} = 21,\quad M_3 = \frac{105}{7} = 15 $$

ต่อไป เราต้องทำให้ $M_i$ แต่ละตัวมีค่าเป็น 1 ภายใต้มอดุลัสที่สอดคล้องกัน

สำหรับ $m_1=3$

เราต้องหา $y_1$ ที่ทำให้:

$$ 35y_1 \equiv 1 \pmod{3} $$

35 หารด้วย 3 เหลือเศษ 2 ดังนั้นจริง ๆ แล้วเรากำลังหา:

$$ 2y_1 \equiv 1 \pmod{3} $$

ลองดู เมื่อ $y_1=2$, $2\times 2=4\equiv 1 \pmod{3}$

ดังนั้น $y_1=2$

สำหรับ $m_2=5$

เราต้องหา $y_2$ ที่ทำให้:

$$ 21y_2 \equiv 1 \pmod{5} $$

21 หารด้วย 5 เหลือเศษ 1 ดังนั้น:

$$ y_2 \equiv 1 \pmod{5} $$

เลือกค่าที่ง่ายที่สุดคือ $y_2=1$

สำหรับ $m_3=7$

เราต้องหา $y_3$ ที่ทำให้:

$$ 15y_3 \equiv 1 \pmod{7} $$

15 หารด้วย 7 เหลือเศษ 1 ดังนั้น:

$$ y_3 \equiv 1 \pmod{7} $$

เลือกค่าที่ง่ายที่สุดคือ $y_3=1$

ดังนั้นสูตรให้ผลว่า:

$$ x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \pmod{105} $$

คำนวณทีละพจน์:

$$ 2 \cdot 35 \cdot 2 = 140 $$$$ 3 \cdot 21 = 63 $$$$ 2 \cdot 15 = 30 $$

เมื่อนำมาบวกกัน:

$ 140+63+30=233 $

จากนั้นหาค่ามอดุลัสด้วย 105:

$$ 233 \equiv 23 \pmod{105} $$

ดังนั้นคำตอบคือ:

$$ x \equiv 23 \pmod{105} $$

กล่าวคือ 23, 128, 233, 338… ล้วนสอดคล้องกับเงื่อนไขเศษเหลือชุดนี้ แต่ภายใต้มอดุลัส 105 ทั้งหมดถือเป็นคำตอบเดียวกัน

  flowchart LR

A["การคำนวณด้วยกุญแจส่วนตัว RSA
m^d mod n"]

A --> B["แยกออก"]

B --> C["คำนวณมอดุลัส p"]
B --> D["คำนวณมอดุลัส q"]

C --> E["ประกอบกลับด้วย CRT"]
D --> E

E --> F["ผลลัพธ์สุดท้ายของการลงลายเซ็น/ถอดรหัส"]

F --> G["HTTPS / SSH / VPN"]

วิธีของคนโบราณ: กลับไปที่บทกลอนตอนต้น

ตอนนี้ลองกลับไปดูบทกลอนช่วยจำตอนต้นอีกครั้ง นี่คือบทสรุปวิธีของฉินจิ่วเสาที่เฉิง ต้าจุ้ย เรียบเรียงไว้:

คนสามคนเดินทาง เหลือเศษสองเจ็ดสิบหา

นำเศษจากการหารด้วย 3 ไปคูณด้วย 70

เพราะ $70\equiv35=5\times7$ และสอดคล้องกับ $70\equiv1\pmod3$, $70\equiv0\pmod5$, $70\equiv0\pmod7$ พร้อมกัน

นั่นหมายความว่า หลังจากคูณด้วย 70 แล้ว ค่าของมันในโลกภายใต้มอดุลัส 3 จะยังคงรักษาเศษเดิมไว้ แต่ในโลกภายใต้มอดุลัส 5 และ 7 มันจะ “หายไป” โดยสมบูรณ์

ห้าต้นเหมยผลิบาน เหลือยี่สิบเอ็ดกิ่

“ยี่สิบเอ็ด” ก็คือ 21

นำเศษจากการหารด้วย 5 ไปคูณด้วย 21

เพราะ $21=3\times7$ และ $21\equiv1\pmod5$ ขณะเดียวกัน $21\equiv0\pmod3, 21\equiv0\pmod7$ ดังนั้นมันจะส่งผลต่อเงื่อนไขมอดุลัส 5 เท่านั้น และไม่รบกวนอีกสองเงื่อนไข

ลูกเจ็ดกลับมาพร้อมหน้า ตรงกับครึ่งเดือนพอดี

คนโบราณกล่าวว่า “ครึ่งเดือน” หมายถึง 15

นำเศษจากการหารด้วย 7 ไปคูณด้วย 15

เพราะ $15=3\times5$, สอดคล้องกับ $15\equiv1\pmod7$ และในขณะเดียวกัน $15\equiv0\pmod3,15\equiv0\pmod5$

มันรับผิดชอบเฉพาะเงื่อนไขของตัวเองเช่นเดียวกัน ดังนั้นเราจึงได้ตัวเลขมหัศจรรย์สามตัว:

สัมประสิทธิ์	มอดุลัส 3	มอดุลัส 5	มอดุลัส 7
70	1	0	0
21	0	1	0
15	0	0	1

• 70 รับผิดชอบเฉพาะมอดุลัส 3
• 21 รับผิดชอบเฉพาะมอดุลัส 5
• 15 รับผิดชอบเฉพาะมอดุลัส 7

ไม่ว่าจะนำมาบวกกันอย่างไร พวกมันก็จะไม่ส่งผลกระทบต่อกัน

หารด้วยหนึ่งร้อยห้า แล้วคำตอบจะปรากฏ

“หนึ่งร้อยห้า” ในที่นี้ก็คือ $105=3\times5\times7$

หลังจากนำสามพจน์แรกมาบวกกันแล้ว ให้ลบ 105 ออกซ้ำ ๆ (หรือที่เรียกในปัจจุบันว่า หาค่ามอดุลัสด้วย 105) จนเหลือจำนวนเต็มบวกที่เล็กที่สุด นั่นคือคำตอบสุดท้าย

เมื่ออ่านมาถึงตรงนี้ คุณอาจรู้สึกว่าวิธีนี้ดูแตกต่างจากวิธีสมัยใหม่ที่แนะนำไปก่อนหน้าอยู่บ้าง ในสูตรที่เราเพิ่งเรียน เรายังต้องคำนวณ “ผกผันการคูณ” แล้วทำไมบทช่วยจำนี้จึงไม่ได้กล่าวถึง?

เหตุผลก็คือ นี่เป็น กรณีพิเศษที่โชคดีอย่างยิ่ง

สำหรับมอดุลัส (3, 5, 7)

$$ 70\equiv1\pmod3, $$$$ 21\equiv1\pmod5, $$$$ 15\equiv1\pmod7 $$

สัมประสิทธิ์ทั้งสามตัวเป็นผกผันการคูณของตัวเองอยู่แล้ว จึงไม่จำเป็นต้องคำนวณเพิ่มเติม

แต่สำหรับปัญหาทฤษฎีบทเศษเหลือของจีนทั่วไป ความโชคดีเช่นนี้มักไม่เกิดขึ้น ตัวอย่างเช่น เมื่อเปลี่ยนมอดุลัสเป็น (4, 9, 11) หรือ (5, 7, 11) การใช้เพียง $M_i=\frac{M}{m_i}$ จะไม่เพียงพอ ยังต้องคูณด้วยผกผันการคูณที่สอดคล้องกันอีกด้วย นี่คือสูตรทั่วไปที่ใช้ในตำราเรียนสมัยใหม่:

$$ x\equiv\sum a_iM_iN_i\pmod M, $$

โดย $(N_i)$ คือผกผันการคูณของ $(M_i)$ ภายใต้มอดุลัสที่สอดคล้องกัน

กล่าวอีกอย่างคือ บทช่วยจำนี้ไม่ใช่ขั้นตอนวิธีอีกแบบที่แตกต่างออกไปโดยสิ้นเชิง แต่เป็นวิธีแก้ที่งดงามของสูตรทฤษฎีบทเศษเหลือของจีนสมัยใหม่ในกรณีที่ มอดุลัสพอดีเป็น 3, 5 และ 7 เช่นเดียวกับชุด 3-4-5 ใน “ทฤษฎีบทพีทาโกรัส” ซึ่งล้วนเป็นกรณีพิเศษของทฤษฎีบทที่นักคณิตศาสตร์จีนโบราณค้นพบ

คนโบราณเมื่อกว่าพันปีก่อนไม่รู้จักคำว่า “ผกผันการคูณ” และไม่สามารถเขียนสูตรสมภาคในรูปแบบสมัยใหม่ได้ แต่พวกเขาค้นพบตัวเลขมหัศจรรย์สามตัวนี้แล้ว ได้แก่ 70, 21 และ 15 และย่อแนวคิดเหล่านั้นไว้ในบทช่วยจำ 28 ตัวอักษร จนถึงทุกวันนี้ เมื่อเรามองย้อนกลับไปด้วยพีชคณิตสมัยใหม่ ก็ยังพบว่านี่คือแก่นสำคัญที่สุดของทฤษฎีบทเศษเหลือของจีน

อินเทอร์เน็ตนำไปใช้อย่างไร

เมื่อคุณเปิดเว็บไซต์ HTTPS

ตัวอย่างเช่น เข้าสู่เว็บไซต์นี้:

https://hpu.edu.kg

เบราว์เซอร์ของคุณจะทำการจับมือกับเซิร์ฟเวอร์ของผม

ในขั้นตอนนี้ เซิร์ฟเวอร์ต้องพิสูจน์ว่า:

“ฉันคือ hpu.edu.kg จริง ๆ”

วิธีการคือ:

ใช้ กุญแจส่วนตัว RSA ของตนลงลายเซ็นดิจิทัลบนข้อมูลชุดหนึ่ง

ปัญหาคือ

การคำนวณด้วยกุญแจส่วนตัวของ RSA ช้ามาก

เพราะต้องคำนวณสิ่งที่มีรูปแบบคล้าย

$$ m^d \bmod n $$

โดยที่

• $(n=pq)$
• $(p,q)$ เป็นจำนวนเฉพาะขนาดใหญ่ที่มีความยาวหลายร้อยหลัก

การคำนวณเลขยกกำลังขนาดใหญ่เช่นนี้โดยตรงเพียงครั้งเดียว ต้องจัดการกับจำนวนเต็มขนาดใหญ่ที่มีมากกว่าหนึ่งพันหลัก

ทฤษฎีบทเศษเหลือของจีนช่วยเร่งความเร็วได้อย่างไร?

กุญแจส่วนตัว RSA มีข้อมูลที่ผู้อื่นไม่มี:

เซิร์ฟเวอร์รู้ว่า

$$ n=pq $$

ดังนั้นจึงไม่จำเป็นต้องคำนวณโดยตรง

$$ m^d\bmod n $$

แต่สามารถแยกออกเป็นปัญหาสองข้อที่เล็กกว่าได้

คำนวณก่อนว่า

$$ m^d\bmod p $$

จากนั้นคำนวณ

$$ m^d\bmod q $$

มอดุลัสทั้งสองมีความยาวเพียงประมาณครึ่งหนึ่งของเดิม

จึงคำนวณได้เร็วขึ้นมาก

สุดท้ายใช้ ทฤษฎีบทเศษเหลือของจีน:

นำคำตอบทั้งสองกลับมาประกอบเป็น

$$ m^d\bmod n $$

กระบวนการทั้งหมดเป็นดังนี้:

  flowchart LR

A["การคำนวณด้วยกุญแจส่วนตัว RSA
m^d mod n"]

A --> B["แยกออก"]

B --> C["คำนวณมอดุลัส p"]
B --> D["คำนวณมอดุลัส q"]

C --> E["ประกอบกลับด้วย CRT"]
D --> E

E --> F["ผลลัพธ์สุดท้ายของการลงลายเซ็น/ถอดรหัส"]

F --> G["HTTPS / SSH / VPN"]

นี่คือการประยุกต์ใช้ CRT ที่มีชื่อเสียงที่สุดใน RSA

ทำไมจึงเร็วขึ้นมาก?

สมมติว่า RSA มีความยาว 2048 บิต

ดังนั้น

• p มีความยาวประมาณ 1024 บิต
• q มีความยาวประมาณ 1024 บิต

ความซับซ้อนของการคูณสมัยใหม่ไม่ได้เพิ่มขึ้นแบบเชิงเส้น

เมื่อความยาวของจำนวนเต็มลดลงครึ่งหนึ่ง

ปริมาณการคำนวณมักลดลงเหลือประมาณหนึ่งในสี่

เมื่อนำหนึ่งในสี่สองส่วนมารวมกัน

ก็จะใกล้เคียง

ครึ่งหนึ่งของปริมาณเดิม

และเมื่อพิจารณาร่วมกับขั้นตอนวิธีเลขยกกำลังเร็วแล้ว

ในทางปฏิบัติ:

CRT-RSA มักเร็วกว่าการคำนวณด้วยกุญแจส่วนตัว RSA โดยตรงประมาณ 3 ถึง 4 เท่า

ดังนั้น การใช้งาน RSA แทบทั้งหมดจึงใช้ CRT

หากไม่ใช้ CRT

ประสิทธิภาพของเซิร์ฟเวอร์จะลดลงอย่างมาก

แล้วมันส่งผลต่ออะไรบ้าง?

แทบทุกพื้นที่ที่ใช้กุญแจส่วนตัว RSA

ตัวอย่างเช่น:

• ใบรับรองเว็บไซต์ HTTPS
• การเข้าสู่ระบบผ่าน SSH
• การยืนยันตัวตนของ VPN
• ลายเซ็นดิจิทัลของซอฟต์แวร์
• ลายเซ็นดิจิทัลของ PDF
• การเข้ารหัสอีเมล (S/MIME)

ตราบใดที่เซิร์ฟเวอร์ต้องคำนวณด้วยกุญแจส่วนตัว RSA

CRT ก็แทบจะมีส่วนร่วมอยู่เสมอ

---

แล้วบล็อกเชนล่ะ?

เมื่อพูดถึงบล็อกเชน ทุกคนคงนึกถึงสกุลเงินดิจิทัลเป็นอันดับแรก เช่น บิตคอยน์ (Bitcoin) และอีเธอเรียม (Ethereum) แต่สิ่งเหล่านี้แทบไม่เกี่ยวข้องกับ CRT เพราะโดยหลักแล้วใช้ ECDSA (ลายเซ็นดิจิทัลบนเส้นโค้งวงรี) ไม่ใช่ RSA ดังนั้น CRT จึงไม่ใช่แกนหลัก

อย่างไรก็ตาม เทคโนโลยีบล็อกเชนพึ่งพาลายเซ็นดิจิทัล และลายเซ็นดิจิทัลก็มีวิธีการใช้งานอยู่หลายรูปแบบ

  flowchart LR

A["ทฤษฎีบทเศษเหลือของจีน"]

A --> B["RSA"]

B --> C["ลายเซ็นดิจิทัล"]

C --> D["HTTPS"]

C --> E["ลายเซ็นซอฟต์แวร์"]

C --> F["การยืนยันตัวตน"]

C -. "บล็อกเชนสมัยใหม่ใช้\nลายเซ็นดิจิทัลบนเส้นโค้งวงรีมากขึ้น" .-> G["บล็อกเชน"]

บทส่งท้าย

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

เมื่อคุณต้องพิสูจน์ตัวตน เซิร์ฟเวอร์จะใช้กุญแจส่วนตัวเพื่อลงลายเซ็นดิจิทัล ขณะที่ทฤษฎีบทเศษเหลือของจีนช่วยแยกการคำนวณมอดุลัสขนาดใหญ่ออกเป็นการคำนวณเล็ก ๆ สองส่วน แล้วนำผลลัพธ์กลับมารวมกันใหม่ ในการใช้งาน RSA แทบทั้งหมด การเพิ่มประสิทธิภาพที่เรียกว่า CRT-RSA ได้กลายเป็นวิธีมาตรฐาน ทำให้การคำนวณด้วยกุญแจส่วนตัวเร็วขึ้นประมาณ 3 ถึง 4 เท่า ด้วยเหตุนี้ ทฤษฎีบททางคณิตศาสตร์ที่ถือกำเนิดขึ้นเมื่อกว่าสองพันปีก่อนจึงยังคงทำงานอย่างเงียบ ๆ อยู่เบื้องหลังโครงสร้างพื้นฐานอินเทอร์เน็ตสมัยใหม่ เช่น HTTPS, SSH, VPN และลายเซ็นซอฟต์แวร์ จนเราสามารถใช้ VPN เข้าถึง Google, YouTube และ ChatGPT ได้ เราก็ควรขอบคุณสูตรคณิตศาสตร์โบราณเหล่านี้ที่เคยถูกเขียนลงบนกระดาษหยาบ ๆ ด้วย

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

ผมไม่รู้ว่าตั้งแต่วันที่มนุษย์เริ่มบันทึกวันที่จนถึงวันนี้ เวลาผ่านไปแล้วกี่วัน ตัวเลขนั้นใหญ่เกินไป แต่ถ้านำจำนวนนี้ไปหารด้วย 7 แล้วดูเศษ ผมก็รู้ว่าวันนี้เป็นวันอะไรในสัปดาห์ ถ้านำไปหารด้วย 12 แล้วดูเศษ ผมก็รู้ว่ามันสอดคล้องกับเดือนใด และถ้านำไปหารด้วย 365 แล้วดูเศษ ผมก็รู้ว่ามันเป็นวันที่เท่าไรของปี