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

ในทฤษฎีจำนวน **การแยกตัวประกอบจำนวนเต็ม** () หรือ **การแยกตัวประกอบเฉพาะ** () คือการแบ่งย่อยจำนวนประกอบออกเป็นตัวหารไม่ชัด (ตัวหารที่ไม่ใช่ 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 บิตจะมีความซับซ้อนเป็น

:: O\left (\exp\left (\left (\begin{matrix}\frac{64}{9}\end{matrix} b\right) ^{1\over3} (\log b) ^{2\over3}\right) \right)

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

## เวลาการทำงานที่คาดหวัง
ขั้นตอนวิธีการแยกตัวประกอบเป็นขั้นตอนวิธีเชิงความน่าจะเป็น หรือ ขั้นตอนวิธีแบบสุ่ม เวลาการทำงานที่คาดหวังของมันจึงไม่เกิน L_n\left[1/2,1+o (1) \right]

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

* การหารเชิงทดลอง
* ขั้นตอนวิธีโรห์ของพอลลาร์ด
* ขั้นตอนวิธีพีลบหนึ่งของพอลลาร์ด

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

* ตะแกรงกำลังสอง
* การกรองตัวเลขในขอบเขตแบบธรรมดา

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

## อ้างอิง
* โดนัลด์ คนูธ. *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.&nbsp;379–417.
*  Chapter 5: Exponential Factoring Algorithms, pp.&nbsp;191–226. Chapter 6: Subexponential Factoring Algorithms, pp.&nbsp;227–284. Section 7.4: Elliptic curve method, pp.&nbsp;301–313.

## แหล่งข้อมูลอื่น
* A collection of links to factoring programs 
* Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", *Computing and Combinatorics"*, 2000, pp.&nbsp;3-22. download
* Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160 (2) : 781-793 (2004). August 2005 version PDF
* [ftp://ftp.computing.dcu.ie/pub/crypto/factor.exe] is a public-domain integer factorization program for Windows. It claims to handle 80-digit numbers. See also the web site for this program MIRACL 
* The RSA Challenge Numbers  - a factoring challenge, no longer active.
* Eric W. Weisstein, “RSA-640 Factored” ''MathWorld Headline News'', November 8, 2005
* Qsieve, a suite of programs for integer factorization. It contains several factorization methods like Elliptic Curve Method and MPQS.
* Source code by Paolo Ardoino , Three known algorithms and C source code.
* Factorization Source Code: by Paul Herman & Ami Fischman, C++ source code for many factorization algorithms including Pollard Rho & Shor's.
* a database containing factorizations, complete and incomplete, of over 80 million numbers.

หมวดหมู่:ขั้นตอนวิธีการแยกตัวประกอบจำนวนเต็ม