การแยกตัวประกอบและการเข้ารหัส


ปัญหาสำคัญอย่างหนึ่งที่นักทฤษฎีด้านวิทยาการคอมพิวเตอร์พยายามหาคำตอบให้ได้ก็คือ ปัญหาการแยกตัวประกอบ นั่นก็คือ มีจำนวนเต็มจำนวนหนึ่งมาให้ เราต้องการเขียนโปรแกรมเพื่อแยกตัวประกอบของจำนวนนั้นให้รวดเร็วที่สุด เช่น หากมีจำนวน 30 มาให้ คำตอบที่เราต้องการก็คือ 30=2*3*5

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

 

คำถามคือ ทำไมนักวิชาการด้านทฤษฎีจึงพยายามหาคำตอบของปัญหานี้ให้ได้ มันสำคัญอย่างไร?

 

เชื่อไหมครับ? หากว่าปัญหานี้ถูกแก้ได้ ระบบเข้ารหัสที่เราใช้กันอยู่ในปัจจุบันนี้ (ที่มีพื้นฐานมาจาก RSA) เกือบทั้งหมดจะถูกถอดรหัสได้ทันที....  ระบบการเข้ารหัสของ RSA ทำงานบนสมมติฐานที่ว่า คอมพิวเตอร์ไม่สามารถแยกตัวประกอบของจำนวนได้อย่างรวดเร็ว หากมีใครสักคนที่ทำได้ RSA ก็จะไม่ปลอดภัยอีกต่อไป  หากแยกตัวประกอบไ้ด้ พวกเราก็ไม่สามารถส่ง e-mail ความลับได้โดยไม่ต้องกลัวถูกอ่านอีกต่อไป ไม่สามารถซื้อของผ่านอินเตอร์เน็ตได้ ฯลฯ

ด้วยเหตุผลที่สำคัญมากดังกล่าว ตลอดสิบกว่าปีที่ผ่านมา ปัญหานี้ยังคงเป็นหนึ่งในปัญหาที่สำคัญที่สุดในสาขาคอมพิวเตอร์มาตลอด เมื่อ 10 ปีก่อน Peter Shor นักวิชาการคอมพิวเตอร์ที่ MIT สามารถออกแบบวิธีการแยกตัวประกอบจำนวนโดยใช้ Quantum computer แต่เนื่องจาก Quantum computer ยังไม่สามารถสร้างได้จริง (ด้วยเหตุผลบางอย่างทางฟิสิกส์) ระบบการเข้ารหัสจึงยังทำงานตามปกติได้  ...

หมายเลขบันทึก: 256654เขียนเมื่อ 21 เมษายน 2009 21:21 น. ()แก้ไขเมื่อ 19 มิถุนายน 2012 20:45 น. ()สัญญาอนุญาต: ครีเอทีฟคอมมอนส์แบบ แสดงที่มา-ไม่ใช้เพื่อการค้า-อนุญาตแบบเดียวกัน


ความเห็น (5)

สวัสดี ครับ คุณปริญญา

เข้ามาเชียร์...ให้เขียนบันทึก สไตล์ นี้ ครับ

ได้ความรู้

ขอบคุณ ครับ

สวัสดีครับ

จะพยายามเขียนครับ ดีใจครับที่มีคนอ่าน ขอบคุณครับ :)

โอ่เนาะ ใช้ประโยชน์จากจุดอ่อน

สวัสดีครับ

ผมเพิ่งสอบ Qualifying Exam ผ่าน

กว่าจะผ่านได้ แทบแย่เหมือนกัน

เพิ่งจะได้กลับเข้ามา Gotoknow หลังจาก 4-5 เดือนที่ผ่าน

ไม่ได้ติดต่อกันนาน หวังว่าคงสบายดีนะครับ

เขียนบันทึกแนวนี้อีกนะครับ จะตามอ่าน

สวัสดีครับภาส

ยินดีด้วยครับ ของผมก็ต้องสอบธันวานี้แล้วเหมือนกัน

ตอนนี้สบายดีครับ เขียนบล็อกน้อย ได้งานมาก ตามกฏของฟิสิกส์ที่ว่า งานเป็นปริมาณที่แปลผกผันกับจำนวนตัวอักษรบนบล็อก :)

พบปัญหาการใช้งานกรุณาแจ้ง LINE ID @gotoknow
ขอแนะนำ ClassStart
ระบบจัดการการเรียนการสอนผ่านอินเทอร์เน็ต
ทั้งเว็บทั้งแอปใช้งานฟรี