จำนวนเฉพาะขนาดใหญ่ตัวใหม่ช่วยไขปัญหาที่ตั้งมานานกว่า 50 ปี (และอัพเดทเลข Mersenne Prime ตัวที่ 49)

By: tonwachara on Tue, 29/11/2016 - 15:09

ในวันที่ 31 ตุลาคม พ.ศ. 2559 โครงการ Seventeen or Bust ภายใต้โครงการ PrimeGrid ซึ่งใช้การประมวลผลแบบกระจาย (distributed computing) ช่วยค้นหาจำนวนเฉพาะที่สนใจ ได้รายงานจำนวนเฉพาะตัวใหม่คือ 10223×231,172,165 + 1 ประกอบด้วยเลขโดด 9,383,761 ตัว และใหญ่เป็นอันดับ 7 ใน The Largest Known Primes Database รวมทั้งยังช่วยไขปัญหา Sierpiński ซึ่งตั้งขึ้นในปีค.ศ. 1967 ได้อีกด้วย

ปัญหา Sierpiński เกี่ยวข้องกับเลข Sierpiński ซึ่งคือตัวเลขที่คูณ 2n แล้วบวก 1 จะได้จำนวนประกอบเสมอ ไม่มีทางได้จำนวนเฉพาะ ยกตัวอย่างเช่น เลข 19 ไม่ใช่เลข Sierpiński เพราะ 19×26 + 1 = 1216 + 1 = 1217 เป็นจำนวนเฉพาะ เลขที่น้อยที่สุดที่ได้รับการยืนยันในปัจจุบันว่าเป็นเลข Sierpiński คือ 78557 โดย John Selfridge ในปีค.ศ. 1962 โดยพิสูจน์ว่าไม่ว่า n จะเป็นจำนวนเต็มบวกใด ๆ เลข 78557×2n + 1 ย่อมหาร 3, 5, 7, 13, 19, 37, 73 ตัวใดตัวหนึ่งลงตัว (เรียกว่า covering set)

แม้ Wacław Sierpiński ได้พิสูจน์ในปีค.ศ. 1960 ว่าเลข Sierpiński มีได้ไม่จำกัด แต่คำถามที่ว่าเลข 78557 เป็นเลข Sierpiński ที่น้อยที่สุดหรือยัง ? อันเป็นปัญหาที่ตั้งโดย Sierpiński และ Selfridge ในปีค.ศ. 1967 กลับยังไม่ได้รับการพิสูจน์จนถึงปัจจุบัน เนื่องจากต้องไล่ทุก ๆ เลข k ที่น้อยกว่า 78557 ว่าต้องมี n ที่ทำให้ k×2n + 1 เป็นจำนวนเฉพาะ (เช่นเลข 19 มี n=6 ให้ 1217 เป็นจำนวนเฉพาะดังตัวอย่างข้างต้น) ก่อนหน้าการค้นพบตามข่าวนี้ มีเลข 6 ตัวที่เรายังไม่พบจำนวนเฉพาะรูปดังกล่าวคือ 10223, 21181, 22699, 24737, 55459 และ 67607 การค้นพบว่า 10223×231,172,165 + 1 เป็นจำนวนเฉพาะ จึงเท่ากับบอกว่า 10223 ไม่ใช่เลข Sierpiński และช่วยตัดตัวเลือกที่อาจเป็นเลข Sierpiński ที่น้อยกว่า 78557 ให้เหลือเพียง 5 ตัวเท่านั้น

การค้นพบนี้ใช้การประมวลผลแบบกระจาย (distributed computing) คือการอาศัย CPU ของคอมพิวเตอร์หลายเครื่อง มาประมวลผลร่วมกันเป็นเครือข่าย เช่น โครงการ PrimeGrid ที่ช่วยค้นหาจำนวนเฉพาะที่น่าสนใจ หรือโครงการ SETI@home ซึ่งช่วยค้นหาความผิดปกติของสัญญาณนอกโลก เพื่อตรวจจับความเป็นไปได้ของการสื่อสารจากสิ่งมีชีวิตต่างดาว

จำนวนเฉพาะในรูป Sierpiński (k×2n + 1) เป็นหนึ่งในวิธีค้นหาจำนวนเฉพาะขนาดใหญ่ (large prime) จำนวนเฉพาะในรูปอื่นเช่น รูป Mersenne (2n - 1) ซึ่ง 274,207,281-1 จำนวนเฉพาะ Mersenne ตัวที่ 49 เพิ่งได้รับการยืนยันว่าเป็นจำนวนเฉพาะเมื่อวันที่ 7 มกราคม พ.ศ. 2559 ที่ผ่านมา โดยประกอบด้วยเลขโดดกว่า 22 ล้านตัว และกลายเป็นจำนวนเฉพาะที่ใหญ่เป็นอันดับ 1 ใน The Largest Known Primes Database ซึ่งจำนวนเฉพาะขนาดใหญ่เหล่านี้มีบทบาทในเทคโนโลยีเข้ารหัสลับ (encryption technology) ที่เราใช้ในอินเตอร์เน็ตทุกวันนี้

ที่มา ScienceAlert