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

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

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

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

จากทฤษฎีบทมูลฐานของเลขคณิต จำนวนเต็มบวกทุกตัวจะมีการแยกตัวประกอบเฉพาะที่แตกต่างกัน

ความยากและความซับซ้อน

แก้

ถ้าจำนวน b บิตเป็นผลคูณของจำนวนเฉพาะ 2 ตัวที่มีขนาดใกล้เคียงกันแล้ว จะไม่มีขั้นตอนวิธีใดๆ ที่สามารถแยกตัวประกอบมันได้ภายในเวลาแบบพหุนาม (polynomial time) กล่าวคือ ไม่สามารถแยกตัวประกอบได้ภายใน O (bk) เมื่อ k คือค่าคงที่ค่าหนึ่ง ปัจจุบันมีขั้นตอนวิธีหลายขั้นตอนที่เร็วกว่า O ((1+ε) b) เมื่อ ε คือจำนวนบวก กล่าวคือ มีประสิทธิภาพเชิงเวลาแบบใต้เลขชี้กำลัง (sub-exponential)

ขั้นตอนวิธีที่มีเวลาการทำงานเชิงเส้นกำกับที่ดีที่สุดคือ การกรองตัวเลขในขอบเขตแบบธรรมดา (general number field sieve (GNFS)) สำหรับจำนวน b บิตจะมีความซับซ้อนเป็น

 

สำหรับคอมพิวเตอร์ทั่วไป การกรองตัวเลขในขอบเขตแบบธรรมดา (GNFS) คือขั้นตอนวิธีที่ดีที่สุดสำหรับจำนวนขนาดใหญ่มากๆ (เลข 100 หลักขึ้นไป) แต่สำหรับควอนตัมคอมพิวเตอร์ ปีเตอร์ ชอร์ ได้ค้นพบขั้นตอนวิธีที่สามารถแก้ปัญหาได้ในเวลาแบบพหุนามในปี พ.ศ. 2537 ขั้นตอนวิธีของชอร์ใช้เวลาการทำงานเพียงแค่ O (b3) และใช้ปริภูมิ O (b) สำหรับจำนวน b บิต

เวลาการทำงานที่คาดหวัง

แก้

ขั้นตอนวิธีการแยกตัวประกอบเป็นขั้นตอนวิธีเชิงความน่าจะเป็น หรือ ขั้นตอนวิธีแบบสุ่ม เวลาการทำงานที่คาดหวังของมันจึงไม่เกิน  

ขั้นตอนวิธีการแยกตัวประกอบต่างๆ

แก้

วัตถุประสงค์เฉพาะ

แก้

เวลาการทำงานขึ้นอยู่กับคุณสมบัติของจำนวนที่จะแยกตัวประกอบ ตัวอย่างเช่น ขั้นตอนวิธีทดลองการหาร ถูกจัดเข้าหมวดวัตถุประสงค์เฉพาะ เพราะว่าเวลาการทำงานเป็นสัดส่วนตามขนาดของตัวประกอบที่เล็กที่สุด

วัตถุประสงค์ทั่วไป

แก้

เวลาการทำงานขึ้นอยู่กับขนาดของจำนวนเต็มที่จะทำการแยกตัวประกอบเพียงลำพัง

ขั้นตอนวิธีที่มีชื่อเสียงอื่นๆ

แก้

อ้างอิง

แก้
  • โดนัลด์ คนูธ. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp. 379–417.
  • Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective (1st ed.). Springer. ISBN 0-387-94777-9. Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313.

แหล่งข้อมูลอื่น

แก้