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

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

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

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

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

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

เขียนใน GotoKnow โดย ปริญญา
ใน This blog never has a title

คำสำคัญ (Tags): #เข้ารหัส#แยกตัวประกอบ

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