การแยกตัวประกอบจำนวนเต็ม

26 ก.พ.

ในทฤษฎีจำนวน การแยกตัวประกอบจำนวนเต็ม (อังกฤษ: integer factorization) หรือ การแยกตัวประกอบเฉพาะ (อังกฤษ: prime factorization) คือการแบ่งย่อยจำนวนประกอบออกเป็นตัวหารไม่ชัด (ตัวหารที่ไม่ใช่ 1 กับ ตัวมันเอง) หลายๆ ตัว ซึ่งเมื่อคูณตัวหารไม่ชัดเหล่านั้นเข้าด้วยกันจะได้ผลลัพธ์ดังเดิม

เมื่อจำนวนมีขนาดใหญ่มาก ไม่มีขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มใดๆ ที่มีประสิทธิภาพเพียงพอ ในปี 2009 ความพยายามในการแยกตัวประกอบของเลข 232 หลัก ได้สำเร็จลง จากการใช้เครื่องจักรมากกว่า 100 เครื่องภายในระยะเวลา 2 ปี ความยากของปัญหาแหละนี้คือหัวใจของขั้นตอนวิธีบางอย่างในวิทยาการเข้ารหัสลับ เช่น RSA

จำนวนที่มีความยาวเท่ากัน ใช่ว่าจะแยกตัวประกอบด้วยความยากเท่ากัน กรณีที่ยากที่สุดของปัญหาเหล่านี้ (สำหรับกลวิธีที่รู้กันในปัจจุบัน) คือจำนวนครึ่งเฉพาะ (semiprime) ซึ่งก็คือจำนวนที่เป็นผลคูณของจำนวนเฉพาะ 2 ตัว

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

%d bloggers like this: