การแยกตัวประกอบของพหุนามบนเขตข้อมูลจำกัด สามารถแก้ไขได้ในเวลาพหุนามที่เป็นไปได้ด้วยอัลกอริทึมแบบสุ่ม (ซึ่งง่ายกว่าการแยกตัวประกอบของจำนวนเต็ม) สำหรับสนามกราวด์คงที่เช่น $\mathbb F_2$สิ่งนี้สามารถกำหนดได้ โดยธรรมชาติแล้วสิ่งนี้ทำให้สามารถทดสอบการลดทอนได้ในเวลาใกล้เคียงกัน
หากเราสนใจแค่การทดสอบแบบใช่/ไม่ใช่แบบลดทอนได้ จะมีวิธีประหยัดเล็กน้อยและอัลกอริทึมดังต่อไปนี้ โปรดทราบว่าเราสามารถคำนวณ $X^{2^k}-X\mod{f(X)}$ กับ $k$ ซ้ำกำลังสองและการลบและดังนั้นการคำนวณ $\mathrm{GCD}(X^{2^k}-X,f(X))$ สามารถทำได้ในเวลาพหุนามใน $k$ และระดับของ $ฉ(X)$.
ขั้นตอนที่ 1 เราคำนวณ $\mathrm{GCD}(X^{2^d}-X,f(X))$ ที่ไหน $d=\mathrm{deg}f$. หากไม่เป็นเช่นนั้น $ฉ(X)$ แล้ว $f$ ไม่สามารถลดทอนได้เนื่องจากมีรากซ้ำหรือมีรากอยู่ภายนอก $\mathbb F_{2^d}$. ถ้ามันเป็น $ฉ(X)$ เราดำเนินการขั้นตอนที่ 2
ขั้นตอนที่ 2 สำหรับแต่ละนายก $p|d$ เราปล่อยให้ $d'=d/p$ และคำนวณ $\mathrm{GCD}(X^{2^{d'}}-X,f(X))$. ถ้านี่ไม่ใช่ 1 แล้ว $ฉ(X)$ มีรากอยู่ในฟิลด์ย่อย $\mathbb F_{2^{d'}}$ และ $ฉ(X)$ ไม่สามารถลดหย่อนได้
ถ้าขั้นตอนที่ 2 ผ่านทั้งหมด $p|d$ จากนั้นรากทั้งหมดก็อยู่ในนั้น $\mathbb F_{2^d}$แต่ไม่ได้อยู่ในฟิลด์ย่อยเพื่อที่ว่า $ฉ(X)$ ลดไม่ได้