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

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

 

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

 

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

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