ในวิชาคณิตศาสตร์ เลขคณิตแบบแยกส่วนคือระบบการคำนวณสำหรับจำนวนเต็ม โดยช่วยให้ "พลิกกลับ" เมื่อถึงค่าหนึ่ง - โมดูล (หรือพหูพจน์ของพวกเขา) แนวทางสมัยใหม่สำหรับวิทยาศาสตร์ประเภทนี้ได้รับการพัฒนาโดย Carl Friedrich Gauss ใน Disquisitiones Arithmeticae ซึ่งตีพิมพ์ในปี 1801 นักวิทยาศาสตร์คอมพิวเตอร์ชอบใช้วิธีนี้มาก เพราะมันน่าสนใจมากและเป็นการเปิดโอกาสให้กับตัวเลขใหม่ๆ ในการดำเนินการต่างๆ
เอสเซนส์
เพราะจำนวนชั่วโมงเริ่มต้นอีกครั้งหลังจากถึง 12 จึงเป็นโมดูโลเลขคณิต 12 ตามคำจำกัดความด้านล่าง 12 ไม่เพียงสอดคล้องกับ 12 เท่านั้น แต่ยังรวมถึง 0 อีกด้วย ดังนั้นเราสามารถตั้งชื่อเวลาที่เรียกว่า " 12:00". "00:00" ท้ายที่สุดแล้ว 12 ก็เหมือนกับ 0 โมดูโล 12.
เลขคณิตแบบแยกส่วนสามารถประมวลผลทางคณิตศาสตร์ได้โดยการแนะนำความสัมพันธ์ที่สอดคล้องกันกับจำนวนเต็มที่เข้ากันได้กับการดำเนินการกับจำนวนเต็มตัวเลข: การบวก การลบ และการคูณ สำหรับจำนวนเต็มบวก n ตัวเลขสองตัว a และ b เรียกว่าโมดูโลคอนกรูเอนต์ ถ้าผลต่างของ a - b คือผลคูณของ n (นั่นคือ ถ้ามีจำนวนเต็ม k เช่นนั้น a - b=kn)
การหัก
ในวิชาคณิตศาสตร์เชิงทฤษฎี เลขคณิตแบบแยกส่วนเป็นหนึ่งในพื้นฐานของทฤษฎีจำนวน ส่งผลกระทบต่อเกือบทุกด้านของการศึกษา และยังใช้กันอย่างแพร่หลายในทฤษฎีกลุ่ม วงแหวน นอต และพีชคณิตนามธรรม ในสาขาคณิตศาสตร์ประยุกต์ ใช้ในพีชคณิตคอมพิวเตอร์ การเข้ารหัส วิทยาการคอมพิวเตอร์ เคมี ทัศนศิลป์ และดนตรี
ฝึกหัด
แอปพลิเคชั่นที่ใช้งานได้จริงคือการคำนวณเช็คซัมในตัวระบุหมายเลขซีเรียล ตัวอย่างเช่น มาตรฐานหนังสือทั่วไปบางมาตรฐานใช้โมดูโลเลขคณิต 11 (หากเผยแพร่ก่อน 1 มกราคม 2550) หรือโมดูโล 10 (หากเผยแพร่ก่อนหรือหลังวันที่ 1 มกราคม 2550) ในทำนองเดียวกัน ตัวอย่างเช่น ในหมายเลขบัญชีธนาคารระหว่างประเทศ (IBAN) ใช้เลขคณิตโมดูโล 97 เพื่อตรวจหาข้อผิดพลาดในการป้อนข้อมูลของผู้ใช้ในหมายเลขบัญชีธนาคาร
ในวิชาเคมี หลักสุดท้ายของหมายเลขทะเบียน CAS (หมายเลขประจำตัวเฉพาะสำหรับสารเคมีแต่ละชนิด) คือเลขตรวจสอบ คำนวณโดยการนำหลักสุดท้ายของสองส่วนแรกของหมายเลขทะเบียน CAS คูณด้วย 1 หลักก่อนหน้า 2 ครั้ง ตัวเลขก่อนหน้า 3 ครั้ง ฯลฯ รวมกันแล้วคำนวณผลรวมโมดูโล 10
การเข้ารหัสคืออะไร? ความจริงก็คือมีความสัมพันธ์ที่แน่นแฟ้นกับหัวข้อที่กำลังสนทนาอยู่ ในวิทยาการเข้ารหัส กฎของเลขคณิตแบบแยกส่วนรองรับระบบกุญแจสาธารณะโดยตรง เช่น RSA และ Diffie-Hellman ข้อมูลนี้มีฟิลด์จำกัดที่อยู่ภายใต้เส้นโค้งวงรี ใช้ในอัลกอริธึมคีย์สมมาตรต่างๆ รวมถึง Advanced Encryption Standard (AES), International Data Encryption Algorithm และ RC4
แอปพลิเคชัน
วิธีนี้ใช้ในพื้นที่ที่คุณต้องอ่านตัวเลข ได้รับการพัฒนาโดยนักคณิตศาสตร์ และทุกคนก็ใช้มัน โดยเฉพาะนักวิทยาศาสตร์คอมพิวเตอร์ สิ่งนี้ได้รับการบันทึกไว้อย่างดีในหนังสือเช่น Modular Arithmetic for Dummies อย่างไรก็ตาม ผู้เชี่ยวชาญจำนวนหนึ่งแนะนำว่าอย่าจริงจังกับวรรณกรรมดังกล่าว
ในวิทยาการคอมพิวเตอร์ การคำนวณแบบแยกส่วนมักใช้ในระดับบิตและการดำเนินการอื่นๆ ที่เกี่ยวข้องกับโครงสร้างข้อมูลวงกลมที่มีความกว้างคงที่ นักวิเคราะห์ชอบที่จะใช้มัน การดำเนินการแบบโมดูโลถูกนำไปใช้ในภาษาโปรแกรมและเครื่องคำนวณมากมาย ในกรณีนี้ เป็นตัวอย่างหนึ่งของแอปพลิเคชันดังกล่าว การเปรียบเทียบโมดูโล การหารด้วยเศษ และลูกเล่นอื่นๆ ก็ใช้ในการเขียนโปรแกรมเช่นกัน
ในดนตรี โมดูโลเลขคณิต 12 ใช้เมื่อพิจารณาถึงระบบอารมณ์ที่เท่ากันของเสียงสิบสองโทน ซึ่งทั้งอ็อกเทฟและเอนฮาร์โมนิกมีค่าเท่ากัน กล่าวอีกนัยหนึ่ง คีย์ในอัตราส่วน 1-2 หรือ 2-1 มีค่าเท่ากัน ในดนตรีและมนุษยศาสตร์อื่นๆ เลขคณิตมีบทบาทค่อนข้างสำคัญ แต่ในหนังสือเรียนนักวิทยาศาสตร์คอมพิวเตอร์มักจะไม่เขียนเกี่ยวกับมัน
วิธีลดเก้า
วิธีการแปลง 9s ให้การตรวจสอบการคำนวณเลขคณิตทศนิยมด้วยตนเองอย่างรวดเร็ว มันขึ้นอยู่กับโมดูโลเลขคณิตแบบแยกส่วน 9 และโดยเฉพาะอย่างยิ่งในคุณสมบัติชี้ขาด 10 10 1.
มีตัวอย่างอื่นๆ โมดูโลเลขคณิต 7 ใช้ในอัลกอริธึมที่กำหนดวันในสัปดาห์สำหรับวันที่เฉพาะ โดยเฉพาะอย่างยิ่ง ความสอดคล้องของ Zeller และอัลกอริธึม Doomsday ใช้โมดูโลเลขคณิต 7 อย่างหนัก
แอปพลิเคชั่นอื่นๆ
มีการกล่าวเกี่ยวกับการคำนวณแบบแยกส่วนในการเข้ารหัสแล้ว ในพื้นที่นี้เธอไม่สามารถถูกแทนที่ได้ โดยทั่วไป เลขคณิตแบบแยกส่วนยังพบการประยุกต์ใช้ในสาขาวิชาต่างๆ เช่น กฎหมาย เศรษฐศาสตร์ (เช่น ทฤษฎีเกม) และสาขาอื่นๆ ของสังคมศาสตร์ กล่าวอีกนัยหนึ่ง การแบ่งตามสัดส่วนและการกระจายทรัพยากรมีบทบาทสำคัญ
เนื่องจากการคำนวณแบบแยกส่วนมีการใช้งานที่หลากหลาย จึงเป็นสิ่งสำคัญที่จะต้องรู้ว่าการแก้ปัญหาระบบการเปรียบเทียบเป็นเรื่องยากเพียงใด ระบบเชิงเส้นตรงของความสอดคล้องสามารถแก้ไขได้ในเวลาพหุนามในรูปแบบของการกำจัดเกาส์เซียน สิ่งนี้อธิบายในรายละเอียดเพิ่มเติมโดยทฤษฎีบทความสอดคล้องเชิงเส้น อัลกอริธึมเช่นการลดมอนต์โกเมอรี่ยังมีอยู่เพื่อให้การดำเนินการเลขคณิตอย่างง่ายสามารถดำเนินการได้อย่างมีประสิทธิภาพ ตัวอย่างเช่น โมดูโลการคูณและยกกำลัง n สำหรับจำนวนมาก นี้เป็นสิ่งสำคัญมากที่จะรู้เพื่อที่จะเข้าใจสิ่งที่การเข้ารหัส ท้ายที่สุด มันก็ใช้งานได้กับการดำเนินการที่คล้ายคลึงกัน
สอดคล้อง
การดำเนินการบางอย่าง เช่น การค้นหาลอการิทึมที่ไม่ต่อเนื่องหรือความสอดคล้องกันกำลังสอง ดูเหมือนจะซับซ้อนพอๆ กับการแยกตัวประกอบจำนวนเต็ม และด้วยเหตุนี้จึงเป็นจุดเริ่มต้นของอัลกอริทึมการเข้ารหัสลับและการเข้ารหัส ปัญหาเหล่านี้อาจเป็น NP-intermediate
ตัวอย่าง
ต่อไปนี้คือฟังก์ชัน C ที่ค่อนข้างเร็วสามฟังก์ชัน - สองฟังก์ชันสำหรับการคูณแบบแยกส่วน และอีกฟังก์ชันสำหรับการเพิ่มเป็นตัวเลขแบบแยกส่วนสำหรับจำนวนเต็มที่ไม่ได้ลงนามสูงสุด 63 บิต โดยไม่มีโอเวอร์โฟลว์ชั่วคราว
ไม่นานหลังจากค้นพบจำนวนเต็ม (1, 2, 3, 4, 5…) เห็นได้ชัดว่าพวกมันถูกแบ่งออกเป็นสองกลุ่ม:
- คู่: หารด้วย 2 (0, 2, 4, 6..).
- คี่: ไม่หารด้วย 2 (1, 3, 5, 7…).
ทำไมความแตกต่างนี้จึงสำคัญ? นี่คือจุดเริ่มต้นของนามธรรม เราสังเกตเห็นคุณสมบัติของตัวเลข (เช่น คู่หรือคี่) ไม่ใช่แค่ตัวตัวเลขเอง ("37")
สิ่งนี้ทำให้เราสามารถสำรวจคณิตศาสตร์ในระดับที่ลึกซึ้งยิ่งขึ้นและค้นหาความสัมพันธ์ระหว่างประเภทตัวเลขมากกว่าประเภทเฉพาะ
คุณสมบัติของตัวเลข
การเป็น "สาม" เป็นเพียงคุณสมบัติของตัวเลขอีกตัวหนึ่ง อาจไม่มีประโยชน์ในทันทีเท่าคู่/คี่ แต่ก็มีอยู่ เราสามารถสร้างกฎเช่น "สิบสาม x สามเส้น=สิบสาม" เป็นต้น แต่มันบ้า เราไม่สามารถสร้างคำใหม่ได้ตลอดเวลา
การทำงานของโมดูโล (ตัวย่อ mod หรือ "%" ในภาษาการเขียนโปรแกรมหลายภาษา) เป็นส่วนที่เหลือเมื่อแผนก. ตัวอย่างเช่น "5 mod 3=2" ซึ่งหมายความว่า 2 คือเศษที่เหลือเมื่อคุณหาร 5 ด้วย 3
เมื่อแปลงคำศัพท์ในชีวิตประจำวันเป็นคณิตศาสตร์ "เลขคู่" คือตำแหน่ง "0 mod 2" ซึ่งหมายความว่าเศษที่เหลือคือ 0 เมื่อหารด้วย 2 เลขคี่คือ "1 mod 2" (มีเศษเหลือ) จาก 1).
เลขคู่และคี่
คู่ x คู่ x คี่ x คี่ คืออะไร? มันคือ 0 x 0 x 1 x 1=0 ที่จริงแล้ว คุณสามารถดูได้ว่าเลขคู่ถูกคูณทุกที่หรือไม่ โดยที่ผลลัพธ์ทั้งหมดจะเป็นศูนย์
เคล็ดลับของคณิตศาสตร์แบบแยกส่วนคือเราใช้มันเพื่อเก็บเวลาแล้ว ซึ่งบางครั้งเรียกว่า "เลขคณิตของนาฬิกา"
ตัวอย่างเช่น: 7:00 น. (am/pm - ไม่สำคัญ) เข็มชั่วโมงจะอยู่ที่ใดใน 7 ชั่วโมง
การดัดแปลง
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 คือเศษที่เหลือเมื่อ 14 หารด้วย 12 สมการ 14 mod 12=2 mod 12 หมายถึง 14 ชั่วโมงและ 2 ชั่วโมงดู เหมือนกันในนาฬิกา 12 ชั่วโมง มีความสอดคล้องกัน โดยระบุด้วยเครื่องหมายเท่ากับสามเท่า: 14 ≡ 2 mod 12.
อีกตัวอย่าง: 8.00 น. ไพ่ใบใหญ่จะอยู่ตรงไหนใน 25 ชั่วโมง
แทนที่จะบวก 25 ถึง 8 คุณสามารถเข้าใจได้ว่า 25 ชั่วโมงเป็นเพียง "1 วัน + 1 ชั่วโมง" คำตอบนั้นง่าย ดังนั้นนาฬิกาจะสิ้นสุดก่อน 1 ชั่วโมง - เวลา 9:00 น.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. คุณแปลง 25 เป็น 1 อย่างสังหรณ์ใจและเพิ่มสิ่งนี้ ถึง 8.
ใช้นาฬิกาเปรียบเทียบ เราสามารถหาได้ว่ากฎของเลขคณิตแบบแยกส่วนและมันได้ผล
การบวก/การลบ
สมมุติว่านาฬิกาของเราหน้าเหมือนกันสองครั้ง ("2:00" กับ "14:00") ถ้าเราบวก x ชั่วโมงเท่ากันทั้งสองจะเกิดอะไรขึ้น? พวกเขาเปลี่ยนในจำนวนเท่ากันบนนาฬิกา! 2:00 + 5 ชั่วโมง ≡ 14:00 + 5 ชั่วโมง - ทั้งคู่จะแสดง 7:00.
ทำไม? เราแค่บวก 5 เข้ากับ 2 เศษที่เหลือที่ทั้งคู่มีและพวกมันเลื่อนไปในทางเดียวกัน สำหรับจำนวนที่เท่ากันทั้งหมด (2 และ 14) การบวกและการลบมีผลเหมือนกัน
มันยากกว่าที่จะรู้ว่าการคูณยังคงเหมือนเดิมหรือไม่ ถ้า 14 ≡ 2 (mod 12) เราสามารถคูณตัวเลขทั้งสองแล้วได้ผลลัพธ์เหมือนกันหรือไม่? มาดูกันว่าจะเกิดอะไรขึ้นเมื่อเราคูณด้วย 3.
ก็ 2:003 × 6:00 น. แต่ 14:003 คืออะไร
จำไว้ 14=12 + 2 เราก็ว่าได้
143=(12 + 2)3=(123) + (23)
ภาคแรก (123) พลาดไม่ได้! ล้น 12 ชั่วโมงที่มี 14 เพียงทำซ้ำหลายครั้ง แต่ใครจะสนล่ะ? เราละเลยการล้นอยู่ดี
การคูณ
เมื่อคูณ เฉพาะส่วนที่เหลือคือ 2 ชั่วโมงเดียวกันคือ 14:00 น. และ 2:00 น. ตามสัญชาตญาณ นี่คือสิ่งที่ฉันเห็นการคูณไม่เปลี่ยนความสัมพันธ์กับคณิตศาสตร์แบบแยกส่วน (คุณสามารถคูณความสัมพันธ์แบบแยกส่วนทั้งสองด้านและได้ผลลัพธ์เหมือนกัน)
เราทำอย่างสังหรณ์ใจ แต่ก็ดีที่ได้ตั้งชื่อให้ คุณมีเที่ยวบินมาถึงเวลา 15.00 น. เขาล่าช้าไป 14 ชม. จะลงจอดกี่โมง
14 ≡ 2 mod 12. คิดว่าเป็น 2 โมง เครื่องบินจะลงจอดตอน 5 โมงเช้า วิธีแก้ปัญหานั้นง่าย: 3 + 2=5 น. สิ่งนี้ซับซ้อนกว่าการดำเนินการแบบโมดูโลธรรมดาเล็กน้อย แต่หลักการก็เหมือนกัน
