คำถามสุ่มจาก SQUAAD:
เมื่อใดที่พบว่าจำนวนเฉพาะสามารถนำไปใช้กับการสร้างอัลกอริธึมการเข้ารหัสคีย์สาธารณะได้
ตอบ:
ทศวรรษ 1970
ประโยคที่ได้รับ :
- แต่วิสัยทัศน์นี้ถูกทำลายในปี 1970 เมื่อมีการประกาศต่อสาธารณะว่าตัวเลขที่สำคัญสามารถนำมาใช้เป็นพื้นฐานสำหรับการสร้างอัลกอริทึมการเข้ารหัสคีย์สาธารณะ
- Primes ถูกใช้ในงานประจำหลายอย่างในเทคโนโลยีสารสนเทศ เช่น การเข้ารหัสคีย์สาธารณะ ซึ่งใช้ประโยชน์จากคุณสมบัติต่างๆ เช่น ความยากลำบากในการแยกตัวประกอบจำนวนมากเป็นปัจจัยเฉพาะ
- อัลกอริธึมมีประสิทธิภาพมากกว่าแผนกทดลองมากถูกคิดค้นขึ้นเพื่อทดสอบความเป็นอันดับหนึ่งของตัวเลขจำนวนมาก
- อัลกอริธึมการเข้ารหัสคีย์สาธารณะหลายตัว เช่น RSA และการแลกเปลี่ยนคีย์ Diffie–Hellman อิงตามจำนวนเฉพาะจำนวนมาก (เช่น ไพรม์ 512 บิตมักใช้สำหรับ RSA และไพรม์ 1024 บิตเป็นเรื่องปกติสำหรับ Diffie–Hellman) .
- หมายเลขเฉพาะยังใช้สำหรับตารางแฮชและเครื่องสร้างหมายเลขสุ่มปลอม
- พบจำนวนเฉพาะเหล่านี้บางส่วนโดยใช้การคำนวณแบบกระจาย
- ทฤษฎีจำนวนโดยทั่วๆ ไป และการศึกษาจำนวนเฉพาะโดยเฉพาะ ถูกมองว่าเป็นตัวอย่างตามบัญญัติของคณิตศาสตร์ล้วนๆ มาช้านาน โดยไม่มีการนำไปใช้นอกเหนือความสนใจของตนเองในการศึกษาหัวข้อนั้นๆ ยกเว้นการใช้เลขเฉพาะ ฟันเฟืองกระจายการสึกหรออย่างสม่ำเสมอ
- อัลกอริธึมที่กำหนดขึ้นได้เป็นวิธีที่จะบอกได้ว่าจำนวนที่กำหนดเป็นจำนวนเฉพาะหรือไม่
- วลี "อัลกอริธึมที่เป็นไปได้ทั้งหมด" ไม่ใช่แค่อัลกอริธึมที่รู้จักในปัจจุบันเท่านั้น แต่ยังรวมถึงอัลกอริธึมที่อาจค้นพบได้ในอนาคต
- ตัวอย่างเช่น การแบ่งทดลองเป็นอัลกอริธึมที่กำหนดขึ้นเอง เพราะหากดำเนินการอย่างถูกต้อง การแบ่งจะระบุจำนวนเฉพาะเป็นจำนวนเฉพาะและจำนวนประกอบเป็นจำนวนรวมเสมอ
- วลีที่เป็นปัญหาการตัดสินใจคือปัญหาในการตัดสินใจว่าข้อมูลที่ป้อนมีตัวประกอบน้อยกว่า k หรือไม่ ไม่ทราบอัลกอริธึมการแยกตัวประกอบจำนวนเต็มที่มีประสิทธิภาพ และข้อเท็จจริงนี้เป็นพื้นฐานของระบบการเข้ารหัสที่ทันสมัยหลายระบบ เช่น อัลกอริธึม RSA
- ก่อนที่การวิจัยจริงจะเน้นไปที่ความซับซ้อนของปัญหาอัลกอริธึมอย่างชัดเจน นักวิจัยหลายคนได้วางรากฐานจำนวนมากขึ้น
- หลักการระดับท้องถิ่นและระดับโลกนี้เน้นย้ำถึงความสำคัญของจำนวนเฉพาะกับทฤษฎีจำนวนอีกครั้ง
- โดยปกติแล้ว อัลกอริธึมความน่าจะเป็นจะเร็วกว่า แต่อย่าเพิ่งพิสูจน์ว่าจำนวนนั้นเป็นจำนวนเฉพาะ
- อย่างไรก็ตาม อัลกอริธึมควอนตัมที่รู้จักกันดีที่สุดสำหรับปัญหานี้ อัลกอริทึมของ Shor ทำงานในเวลาพหุนาม
- ตะแกรงของ Eratosthenes ซึ่งมีสาเหตุมาจาก Eratosthenes เป็นวิธีการง่ายๆ ในการคำนวณจำนวนเฉพาะ แม้ว่าจำนวนเฉพาะขนาดใหญ่ที่พบในปัจจุบันด้วยคอมพิวเตอร์จะไม่ถูกสร้างด้วยวิธีนี้
- ปัญหาจะถือว่าเป็นเรื่องยากโดยเนื้อแท้หากการแก้ปัญหาต้องใช้ทรัพยากรจำนวนมาก ไม่ว่าจะใช้อัลกอริทึมแบบใดก็ตาม
- อัลกอริธึมที่ใช้บิตสุ่มเรียกว่าอัลกอริธึมแบบสุ่ม
- เชื่อกันว่าหากปัญหาสามารถแก้ไขได้ด้วยอัลกอริธึม มีเครื่องทัวริงที่ช่วยแก้ปัญหาได้
- แม้ว่าตัวเลขคาร์ไมเคิลจะหายากกว่าจำนวนเฉพาะอย่างมาก ดังนั้น การทดสอบนี้จึงมีประโยชน์สำหรับการใช้งานจริง
- ตัวอย่างเช่น รายการจำนวนเฉพาะของ Derrick Norman Lehmer มากถึง 10,006,721 พิมพ์ซ้ำในช่วงปลายปี 1956 โดยเริ่มต้นด้วย 1 เป็นจำนวนเฉพาะตัวแรก
- วิทยานิพนธ์ของ Cobham กล่าวว่าปัญหาสามารถแก้ไขได้ด้วยทรัพยากรจำนวนที่เป็นไปได้หากยอมรับอัลกอริทึมเวลาพหุนาม
- ยูคลิดยังแสดงวิธีสร้างจำนวนสมบูรณ์จากจำนวนเฉพาะของเมอร์เซนอีกด้วย
- ณ เดือนมกราคม 2016[อัปเดต] จำนวนเฉพาะที่ใหญ่ที่สุดที่รู้จักมีทศนิยม 22,338,618 หลัก
- คำถามดังกล่าวกระตุ้นให้เกิดการพัฒนาสาขาต่างๆ ของทฤษฎีจำนวน โดยเน้นที่การวิเคราะห์หรือลักษณะเชิงพีชคณิตของตัวเลข