วิธีสร้างจำนวนเฉพาะขนาดใหญ่ | นิตยสารควอนตั้ม

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

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

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

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

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

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

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

ในปี 2009 Terence Tao นักคณิตศาสตร์และผู้ชนะเลิศ Fields ต้องการทำให้ดีขึ้น เขาท้าทายนักคณิตศาสตร์ให้คิดอัลกอริธึมที่กำหนดขึ้นเพื่อค้นหาจำนวนเฉพาะของขนาดที่กำหนดภายในระยะเวลาการคำนวณ

การจำกัดเวลานั้นเรียกว่าเวลาพหุนาม อัลกอริธึมจะแก้ปัญหาในเวลาพหุนาม ถ้าจำนวนขั้นตอนที่ใช้ไม่เกินฟังก์ชันพหุนามของ nขนาดของอินพุต (ฟังก์ชันพหุนามประกอบด้วยพจน์ที่มีตัวแปรยกกำลังจำนวนเต็มบวก เช่น n² หรือ 4n³.) ในบริบทของการสร้างจำนวนเฉพาะ n หมายถึงจำนวนหลักในจำนวนเฉพาะที่ต้องการ การคำนวณนี้ไม่เสียค่าใช้จ่ายมากนัก นักวิทยาการคอมพิวเตอร์อธิบายถึงปัญหาที่สามารถแก้ไขได้ด้วยอัลกอริธึมในเวลาพหุนามอย่างง่ายดาย ในทางตรงกันข้าม ปัญหาที่ยากนั้นต้องใช้เวลาแบบเอ็กซ์โพเนนเชียล ซึ่งหมายความว่าต้องใช้ขั้นตอนจำนวนหนึ่งโดยประมาณด้วยฟังก์ชันเอ็กซ์โปเนนเชียล (ซึ่งรวมถึงคำศัพท์เช่น 2ⁿ).

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

ยังไม่มีใครสามารถรับมือกับความท้าทายของเทาได้ แต่งานใหม่ก็ใกล้เข้ามาแล้ว โดยอาศัยแนวทางที่ Shafi Goldwasser และ Eran Gat นักวิทยาศาสตร์คอมพิวเตอร์จากสถาบันเทคโนโลยีแมสซาชูเซตส์นำมาใช้ในปี 2011 พวกเขาอธิบายอัลกอริธึม "pseudodeterministic" ซึ่งเป็นสูตรทางคณิตศาสตร์สำหรับปัญหาการค้นหา เช่น การค้นหาจำนวนเฉพาะขนาดใหญ่ที่อาจใช้ประโยชน์จากการสุ่ม และยังคงให้คำตอบเดิมทุกครั้งซึ่งมีความเป็นไปได้สูง พวกเขาจะใช้ประสิทธิภาพของบิตสุ่มในสูตร ซึ่งจะยกเลิกการสุ่มในผลลัพธ์ โดยจะปรากฏเป็นค่าที่กำหนด

นักวิจัยได้สำรวจอัลกอริธึมการกำหนดเทียมตั้งแต่นั้นเป็นต้นมา ในปี 2017 Santhanam และ Igor Oliveira จากมหาวิทยาลัย Warwick (ซึ่งมีส่วนร่วมในงานใหม่ด้วย) อธิบาย วิธีการกำหนดแบบหลอกเพื่อสร้างจำนวนเฉพาะที่ใช้การสุ่มและดูเป็นการกำหนดอย่างน่าเชื่อถือ แต่ได้ผลในเวลา "ต่ำกว่าเลขชี้กำลัง" - เร็วกว่าเลขชี้กำลัง แต่ช้ากว่าเวลาพหุนาม จากนั้นในปี 2021 เทลแอนด์ ลี่เจีย เฉินนักวิทยาศาสตร์คอมพิวเตอร์จากมหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์ สำรวจ วิธีใช้ปัญหาหนักเพื่อสร้างตัวสร้างตัวเลขสุ่มเทียม (อัลกอริทึมที่สร้างสตริงตัวเลขซึ่งแยกไม่ออกจากเอาต์พุตแบบสุ่ม) “[เรา] พบความเชื่อมโยงใหม่ระหว่างความแข็งและการสุ่มเทียม” เฉินกล่าว

ในที่สุดชิ้นส่วนต่างๆ ก็มารวมกันในฤดูใบไม้ผลิปี 2023 ระหว่างนั้น bootcamp เกี่ยวกับความซับซ้อนในการคำนวณ ที่สถาบัน Simons สำหรับทฤษฎีคอมพิวเตอร์ที่เบิร์กลีย์ เมื่อนักวิจัยเริ่มทำงานร่วมกันในการแก้ปัญหา โดยรวบรวมผลลัพธ์ในอดีตเข้าด้วยกัน สำหรับงานชิ้นใหม่ Chen กล่าวว่า Hanlin Ren นักวิทยาศาสตร์คอมพิวเตอร์ที่ Oxford และผู้ร่วมเขียน มีแนวคิดเบื้องต้นในการรวมผลลัพธ์ของ Chen-Tell เข้ากับแนวทาง Santhanam-Oliveira ในรูปแบบใหม่ จากนั้นทีมงานทั้งหมดก็ได้พัฒนาแนวคิดอย่างเต็มที่มากขึ้นเพื่อจัดทำรายงานฉบับใหม่

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

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

“คงจะดีไม่น้อยหากกำจัดข้อแม้เล็กๆ น้อยๆ นั้นออกไป” กรอสแมนกล่าว

เป้าหมายสูงสุด Santhanam กล่าวคือค้นหาอัลกอริธึมที่ไม่ต้องใช้การสุ่มเลย แต่ภารกิจนั้นยังคงเปิดอยู่ “ความมุ่งมั่นคือสิ่งที่เราอยากจะใช้” เขากล่าว

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

“มันน่าตื่นเต้นที่ได้ลองคิดว่าการสังเกตการณ์อันยอดเยี่ยมเหล่านี้จะนำไปสู่จุดใดอีก” Tell กล่าว