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

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

O ( exp ⁡ ( ( 64 9 b ) 1 3 ( log ⁡ b ) 2 3 ) ) . {\displaystyle O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}b\right)^{1 \over 3}(\log b)^{2 \over 3}\right)\right).}

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