วิธีตรวจสอบว่าตัวเลขเป็นจำนวนเฉพาะหรือไม่

วิดีโอ: การตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่ #คณิตเพิ่มเติม ม.1

เนื้อหา

ขั้นตอน
ส่วนที่ 1 จาก 3: การทดสอบความเรียบง่าย
ส่วนที่ 2 จาก 3: การทดสอบความเรียบง่ายทำงานอย่างไร
ส่วนที่ 3 ของ 3: การใช้ทฤษฎีบทเศษจีน
เคล็ดลับ
อะไรที่คุณต้องการ

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

ขั้นตอน

ส่วนที่ 1 จาก 3: การทดสอบความเรียบง่าย

บันทึก: ในทุกสูตร NS หมายถึงหมายเลขที่จะตรวจสอบ

1 การแจงนับตัวหาร แค่แบ่งก็พอ NS ถึงจำนวนเฉพาะทั้งหมดตั้งแต่ 2 ถึงค่าที่ปัดเศษ ( ${ displaystyle { sqrt {n}}}$ ).
2 ทฤษฎีบทเล็กๆ ของแฟร์มาต์ คำเตือน: บางครั้งการทดสอบจะระบุตัวเลขประกอบเป็นจำนวนเฉพาะอย่างไม่ถูกต้อง แม้กระทั่งสำหรับค่าทั้งหมดของ a
- มาเลือกจำนวนเต็มกัน NSโดยที่ 2 ≤ a ≤ n - 1
- ถ้า a (mod n) = a (mod n) แสดงว่าจำนวนนั้นน่าจะเป็นจำนวนเฉพาะ หากไม่พอใจความเท่าเทียมกัน จำนวน n จะประกอบ
- ตรวจสอบความเท่าเทียมกันที่กำหนดสำหรับค่าหลายค่า NSเพื่อเพิ่มโอกาสที่จำนวนที่กำลังทดสอบจะเป็นจำนวนเฉพาะอย่างแท้จริง
3 การทดสอบมิลเลอร์-ราบิน คำเตือน: บางครั้งถึงแม้จะไม่ค่อยบ่อยนักสำหรับค่าหลายค่าของ a การทดสอบจะระบุตัวเลขประกอบเป็นจำนวนเฉพาะอย่างไม่ถูกต้อง
- หาปริมาณ s และ d เช่นนั้น ${ displaystyle n-1 = 2 ^ {s} * d}$ .
- เลือกจำนวนเต็ม NS ในช่วง 2 ≤ a ≤ n - 1
- ถ้า a = +1 (mod n) หรือ -1 (mod n) แสดงว่า n เป็นจำนวนเฉพาะ ในกรณีนี้ ไปที่ผลการทดสอบ หากไม่เกิดความเท่าเทียมกัน ให้ไปยังขั้นตอนถัดไป
- ยกกำลังคำตอบของคุณ ( ${ displaystyle a ^ {2d}}$ ). หากคุณได้ -1 (mod n) แล้ว n น่าจะเป็นจำนวนเฉพาะ ในกรณีนี้ ไปที่ผลการทดสอบ หากความเท่าเทียมกันล้มเหลวให้ทำซ้ำ ( ${ displaystyle a ^ {4}}$ เป็นต้น) จนถึง ${ displaystyle a ^ {2 ^ {s-1} d}}$ .
- ถ้าในขั้นตอนใดหลังจากยกกำลังสองตัวเลขอื่นที่ไม่ใช่ ${ displaystyle pm 1}$ (mod n) คุณได้ +1 (mod n) ดังนั้น n จึงเป็นจำนวนประกอบ ถ้า ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n) แล้ว n ไม่ใช่จำนวนเฉพาะ
- ผลการทดสอบ: ถ้า n ผ่านการทดสอบ ให้ทำซ้ำสำหรับค่าอื่น NSเพื่อเพิ่มความมั่นใจ

ส่วนที่ 2 จาก 3: การทดสอบความเรียบง่ายทำงานอย่างไร

1 การแจงนับตัวหาร ตามนิยาม ตัวเลข NS ง่ายก็ต่อเมื่อหารด้วย 2 ไม่ลงตัวและจำนวนเต็มอื่น ๆ ยกเว้น 1 และตัวมันเอง สูตรข้างต้นช่วยให้คุณสามารถลบขั้นตอนที่ไม่จำเป็นและประหยัดเวลาได้ ตัวอย่างเช่น หลังจากตรวจสอบว่าตัวเลขหารด้วย 3 ลงตัวหรือไม่ ไม่จำเป็นต้องตรวจสอบว่าหารด้วย 9 ลงตัวหรือไม่
- ฟังก์ชันพื้น (x) ปัดเศษ x เป็นจำนวนเต็มที่ใกล้เคียงที่สุดที่น้อยกว่าหรือเท่ากับ x
2 เรียนรู้เกี่ยวกับเลขคณิตแบบแยกส่วน การดำเนินการ "x mod y" (mod เป็นตัวย่อของคำภาษาละติน "modulo" นั่นคือ "module") หมายถึง "หาร x ด้วย y และหาส่วนที่เหลือ" กล่าวอีกนัยหนึ่งในทางคณิตศาสตร์แบบแยกส่วนเมื่อถึงค่าที่แน่นอนซึ่งเรียกว่า โมดูล, ตัวเลข "เปลี่ยน" เป็นศูนย์อีกครั้ง ตัวอย่างเช่น นาฬิกานับถอยหลังด้วยโมดูล 12: จะแสดงเวลา 10, 11 และ 12 ชั่วโมง แล้วย้อนกลับเป็น 1
- เครื่องคิดเลขจำนวนมากมีปุ่ม mod ส่วนท้ายของส่วนนี้จะแสดงวิธีการคำนวณฟังก์ชันนี้สำหรับตัวเลขจำนวนมากด้วยตนเอง
3 เรียนรู้เกี่ยวกับหลุมพรางของทฤษฎีบทเล็กๆ ของแฟร์มาต์ ตัวเลขทั้งหมดที่ไม่ตรงตามเงื่อนไขการทดสอบนั้นประกอบกัน แต่ตัวเลขที่เหลือเป็นเพียงตัวเลข อาจจะ เป็นเรื่องง่าย หากคุณต้องการหลีกเลี่ยงผลลัพธ์ที่ไม่ถูกต้อง ให้ค้นหา NS ในรายการ "หมายเลข Carmichael" (ตัวเลขประกอบที่ตรงตามการทดสอบนี้) และ "หมายเลข Fermat pseudoprime" (ตัวเลขเหล่านี้ตรงตามเงื่อนไขการทดสอบสำหรับบางค่าเท่านั้น NS).
4 ถ้าสะดวก ให้ใช้การทดสอบ Miller-Rabin แม้ว่าวิธีนี้จะค่อนข้างยุ่งยากสำหรับการคำนวณด้วยตนเอง แต่ก็มักใช้ในโปรแกรมคอมพิวเตอร์ ให้ความเร็วที่ยอมรับได้และมีข้อผิดพลาดน้อยกว่าวิธีของแฟร์มาต์ ตัวเลขประกอบจะไม่ถูกนำมาเป็นจำนวนเฉพาะถ้าทำการคำนวณสำหรับค่ามากกว่า ¼ NS... หากคุณสุ่มเลือกค่าที่แตกต่างกัน NS และสำหรับการทดสอบทั้งหมดจะให้ผลในเชิงบวก เราสามารถสันนิษฐานได้ด้วยความมั่นใจค่อนข้างสูงว่า NS เป็นจำนวนเฉพาะ
5 สำหรับตัวเลขจำนวนมาก ให้ใช้เลขคณิตแบบแยกส่วน หากคุณไม่มีเครื่องคำนวณ mod ที่มีประโยชน์ หรือเครื่องคิดเลขไม่ได้ออกแบบมาเพื่อจัดการกับตัวเลขจำนวนมากเช่นนี้ ให้ใช้คุณสมบัติทางกำลังและเลขคณิตแบบแยกส่วนเพื่อทำให้การคำนวณง่ายขึ้น ด้านล่างเป็นตัวอย่างสำหรับ 350{ displaystyle 3 ^ {50}} สมัย 50:
- เขียนนิพจน์ใหม่ในรูปแบบที่สะดวกยิ่งขึ้น: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 การคำนวณด้วยตนเองอาจต้องมีการทำให้เข้าใจง่ายขึ้น
- ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ สมัย 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 ที่นี่เราคำนึงถึงคุณสมบัติของการคูณแบบแยกส่วน
- ${ displaystyle 3 ^ {25}}$ สมัย 50 = 43
- ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ displaystyle (43 * 43)}$ รุ่น 50
- ${ displaystyle = 1849}$ รุ่น 50
- ${ displaystyle = 49}$ .

ส่วนที่ 3 ของ 3: การใช้ทฤษฎีบทเศษจีน

1 เลือกสองตัวเลข ตัวเลขตัวใดตัวหนึ่งจะต้องเป็นตัวเลขผสม และอีกตัวหนึ่งต้องเป็นตัวเลขที่คุณต้องการทดสอบเพื่อความเรียบง่าย
- หมายเลข 1 = 35
- หมายเลข 2 = 97
2 เลือกค่าสองค่าที่มากกว่าศูนย์และน้อยกว่าตัวเลข Number1 และ Number2 ตามลำดับ ค่าเหล่านี้ต้องไม่เท่ากัน
- ค่า 1 = 1
- ค่า2 = 2
3 คำนวณ MMI (การผกผันการคูณทางคณิตศาสตร์) สำหรับ Number1 และ Number2
- คำนวณMMI
  - MMI1 = Number2 ^ -1 Mod Number1
  - MMI2 = Number1 ^ -1 Mod Number2
- สำหรับจำนวนเฉพาะเท่านั้น (ซึ่งจะให้ตัวเลขสำหรับจำนวนประกอบ แต่จะไม่ใช่ MMI ของเขา):
  - MMI1 = (Number2 ^ (Number1-2))% Number1
  - MMI2 = (หมายเลข 1 ^ (หมายเลข 2-2))% Number2
- ตัวอย่างเช่น:
  - MMI1 = (97 ^ 33)% 35
  - MMI2 = (35 ^ 95)% 97
4 สร้างตารางสำหรับแต่ละโมดูล MMI จนถึง log2:
- สำหรับ MMI1
  - F (1) = Number2% Number1 = 97% 35 = 27
  - F (2) = F (1) * F (1)% Number1 = 27 * 27% 35 = 29
  - F (4) = F (2) * F (2)% Number1 = 29 * 29% 35 = 1
  - F (8) = F (4) * F (4)% Number1 = 1 * 1% 35 = 1
  - F (16) = F (8) * F (8)% Number1 = 1 * 1% 35 = 1
  - F (32) = F (16) * F (16)% Number1 = 1 * 1% 35 = 1
- คำนวณเลขคู่ 1 - 2
  - 35 -2 = 33 (10001) ฐาน 2
  - MMI1 = F (33) = F (32) * F (1) mod 35
  - MMI1 = F (33) = 1 * 27 mod 35
  - MMI1 = 27
- สำหรับ MMI2
  - F (1) = Number1% Number2 = 35% 97 = 35
  - F (2) = F (1) * F (1)% Number2 = 35 * 35 mod 97 = 61
  - F (4) = F (2) * F (2)% Number2 = 61 * 61 mod 97 = 35
  - F (8) = F (4) * F (4)% Number2 = 35 * 35 mod 97 = 61
  - F (16) = F (8) * F (8)% Number2 = 61 * 61 mod 97 = 35
  - F (32) = F (16) * F (16)% Number2 = 35 * 35 mod 97 = 61
  - F (64) = F (32) * F (32)% Number2 = 61 * 61 mod 97 = 35
  - F (128) = F (64) * F (64)% Number2 = 35 * 35 mod 97 = 61
- คำนวณเลขคู่ 2 - 2
  - 97 - 2 = 95 = (1011111) ฐาน 2
  - MMI2 = ((((((F (64)) * F (16)% 97)) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
  - MMI2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
  - MMI2 = 61
5 คำนวณ (Value1 * Number2 * MMI1 + Value2 * Number1 * MMI2)% (Number1 * Number2)
- คำตอบ = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
- คำตอบ = (2619 + 4270)% 3395
- คำตอบ = 99
6 ตรวจสอบว่า Number1 ไม่ใช่จำนวนเฉพาะ
- คำนวณ (คำตอบ - มูลค่า1)% Number1
- 99 – 1 % 35 = 28
- เนื่องจาก 28 มากกว่า 0, 35 ไม่ใช่จำนวนเฉพาะ
7 ตรวจสอบว่า Number2 เป็นจำนวนเฉพาะ
- คำนวณ (คำตอบ - มูลค่า2)% Number2
- 99 – 2 % 97 = 0
- เนื่องจาก 0 คือ 0, 97 จึงเป็นจำนวนเฉพาะมากที่สุด
8 ทำซ้ำขั้นตอนที่ 1 ถึง 7 อย่างน้อยสองครั้ง
- หากคุณได้รับ 0 ในขั้นตอนที่ 7:
  - ใช้ Number1 อื่นหาก Number1 ไม่ใช่จำนวนเฉพาะ
  - ใช้ Number1 อื่นหาก Number1 เป็นจำนวนเฉพาะ ในกรณีนี้ คุณควรได้ 0 ในขั้นตอนที่ 6 และ 7
  - ใช้ความหมาย1และความหมาย2ที่แตกต่างกัน
- หากในขั้นตอนที่ 7 คุณได้รับ 0 อย่างสม่ำเสมอ แสดงว่าหมายเลข 2 เป็นจำนวนเฉพาะ
- ขั้นตอนที่ 1 ถึง 7 อาจส่งผลให้เกิดข้อผิดพลาดหาก Number1 ไม่ใช่จำนวนเฉพาะและ Number2 เป็นตัวหารของ Number1 วิธีการที่อธิบายไว้ใช้ได้ในทุกกรณีเมื่อทั้งสองจำนวนเป็นจำนวนเฉพาะ
- เหตุผลที่คุณต้องทำซ้ำขั้นตอนที่ 1 ถึง 7 เนื่องจากในบางกรณี แม้ว่าหมายเลข 1 และหมายเลข 2 จะไม่ใช่จำนวนเฉพาะ ในขั้นตอนที่ 7 คุณจะได้ 0 (สำหรับตัวเลขหนึ่งหรือทั้งสอง) สิ่งนี้ไม่ค่อยเกิดขึ้นเลือก Number1 อื่น (คอมโพสิต) และหาก Number2 ไม่ใช่จำนวนเฉพาะ ดังนั้น Number2 จะไม่เท่ากับศูนย์ในขั้นตอนที่ 7 (ยกเว้นกรณีที่ Number1 เป็นตัวหารของ Number2 - เฉพาะในที่นี้ จำนวนเฉพาะจะเท่ากับศูนย์เสมอในขั้นตอนที่ 7)

เคล็ดลับ

จำนวนเฉพาะจาก 168 ถึง 1000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
แม้ว่าการทดสอบกำลังเดรัจฉานจะเป็นการทดสอบที่น่าเบื่อเมื่อทำงานกับตัวเลขจำนวนมาก แต่ก็ค่อนข้างมีประสิทธิภาพสำหรับตัวเลขขนาดเล็ก แม้แต่ในกรณีของตัวเลขจำนวนมาก ให้เริ่มด้วยการทดสอบตัวหารเล็ก จากนั้นไปยังวิธีการที่ซับซ้อนมากขึ้นในการตรวจสอบความเรียบง่ายของตัวเลข (หากไม่พบตัวหารเล็ก)