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