ในคณิตศาสตร์และพีชคณิตคอมพิวเตอร์การแยกตัวประกอบพหุนามหรือการแยกตัวประกอบพหุนามคือ การแสดงพหุนามที่มีสัมประสิทธิ์อยู่ในฟิลด์ ที่กำหนด หรืออยู่ในจำนวนเต็มในรูปผลคูณของตัวประกอบที่ไม่สามารถแยกย่อยได้อีกซึ่งมีสัมประสิทธิ์อยู่ในโดเมนเดียวกัน การแยกตัวประกอบพหุนามเป็นหนึ่งในองค์ประกอบพื้นฐานของระบบพีชคณิตคอมพิวเตอร์

อัลกอริทึมการแยกตัวประกอบพหุนามตัวแรกได้รับการตีพิมพ์โดยTheodor von Schubertในปี 1793 ^{[ 1 ]} Leopold Kroneckerค้นพบอัลกอริทึมของ Schubert อีกครั้งในปี 1882 และขยายไปสู่พหุนามหลายตัวแปรและสัมประสิทธิ์ในส่วนขยายพีชคณิตแต่ความรู้ส่วนใหญ่ในหัวข้อนี้มีอายุไม่เกินประมาณปี 1965 และระบบพีชคณิตคอมพิวเตอร์ระบบแรก: ^{[ 2 ]}

เมื่ออัลกอริทึมแบบขั้นตอนจำกัดที่รู้จักกันมานานถูกนำไปใช้กับคอมพิวเตอร์เป็นครั้งแรก ปรากฏว่ามันไม่มีประสิทธิภาพอย่างมาก ข้อเท็จจริงที่ว่าพหุนามเอกตัวแปรหรือพหุนามหลายตัวแปรเกือบทุกตัวที่มีดีกรีไม่เกิน 100 และมีสัมประสิทธิ์ขนาดปานกลาง (ไม่เกิน 100 บิต) สามารถแยกตัวประกอบได้ด้วยอัลกอริทึมสมัยใหม่ในเวลาเพียงไม่กี่นาที แสดงให้เห็นว่าปัญหานี้ได้รับการแก้ไขอย่างประสบความสำเร็จเพียงใดในช่วงสิบห้าปีที่ผ่านมา (เอริช คัลโทเฟน, 1982)

อัลกอริทึมและคอมพิวเตอร์สมัยใหม่สามารถแยกตัวประกอบพหุนามเอกตัวแปรที่มีดีกรีมากกว่า 1000 ซึ่งมีสัมประสิทธิ์ที่มีหลักพันได้ อย่างรวดเร็ว ^{[ 3 ]} เพื่อจุดประสงค์นี้ แม้แต่สำหรับการแยกตัวประกอบเหนือจำนวนตรรกยะและฟิลด์จำนวนขั้นตอนพื้นฐานคือการแยกตัวประกอบพหุนามเหนือฟิลด์จำกัด

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

การแยกตัวประกอบขึ้นอยู่กับฟิลด์พื้นฐาน ตัวอย่างเช่นทฤษฎีบทพื้นฐานของพีชคณิตซึ่งกล่าวว่าพหุนามทุกตัวที่มีสัมประสิทธิ์เชิงซ้อนจะมีรากเชิงซ้อน บ่งชี้ว่าพหุนามที่มีสัมประสิทธิ์เป็นจำนวนเต็มสามารถแยกตัวประกอบได้ (ด้วยอัลกอริทึมการหาราก ) เป็นตัวประกอบเชิงเส้นบนฟิลด์เชิงซ้อนC ในทำนอง เดียวกัน บนฟิลด์ของจำนวนจริง ตัวประกอบที่ไม่สามารถแยกตัวประกอบได้จะมีดีกรีไม่เกินสอง ในขณะที่มีพหุนามที่ มี ดีกรีใดๆ ก็ได้ที่ไม่สามารถแยกตัวประกอบได้บนฟิลด์ของจำนวนตรรกยะQ

คำถามเรื่องการแยกตัวประกอบพหุนามจะมีความหมายเฉพาะสำหรับสัมประสิทธิ์ในฟิลด์ที่คำนวณได้ซึ่งองค์ประกอบทุกตัวสามารถแสดงในคอมพิวเตอร์ได้ และมีอัลกอริทึมสำหรับการดำเนินการทางคณิตศาสตร์ อย่างไรก็ตาม นี่ไม่ใช่เงื่อนไขที่เพียงพอ: Fröhlich และ Shepherdson ยกตัวอย่างฟิลด์ดังกล่าวที่ไม่มีอัลกอริทึมการแยกตัวประกอบ^{[ 4 ]}

ฟิลด์ของสัมประสิทธิ์ที่ทราบอัลกอริทึมการแยกตัวประกอบ ได้แก่ฟิลด์ของจำนวนเฉพาะ (นั่นคือ ฟิลด์ของจำนวนตรรกยะและฟิลด์ของจำนวนเต็มมอดูลจำนวนเฉพาะ ) และส่วนขยายฟิลด์ที่สร้างขึ้นอย่างจำกัดสัมประสิทธิ์จำนวนเต็มก็สามารถจัดการได้เช่นกัน วิธีการแบบคลาสสิกของโครเนกเกอร์น่าสนใจเฉพาะในมุมมองทางประวัติศาสตร์เท่านั้น อัลกอริทึมสมัยใหม่ดำเนินการตามลำดับดังนี้:

• การแยกตัวประกอบแบบไร้กำลังสอง
• การแยกตัวประกอบบนฟิลด์จำกัด

และส่วนลด:

• จาก กรณี หลายตัวแปรไปสู่กรณีตัวแปรเดียว
• จากสัมประสิทธิ์ในการขยายเชิงอภิปรัชญาล้วนๆไปสู่กรณีหลายตัวแปรเหนือสนามพื้นฐาน (ดูด้านล่าง )
• จากสัมประสิทธิ์ในส่วนขยายเชิงพีชคณิตไปสู่สัมประสิทธิ์ในฟิลด์พื้นฐาน (ดูด้านล่าง )
• จากสัมประสิทธิ์ตรรกยะไปเป็นสัมประสิทธิ์จำนวนเต็ม (ดูด้านล่าง )
• จากสัมประสิทธิ์จำนวนเต็มไปสู่สัมประสิทธิ์ในฟิลด์จำนวนเฉพาะที่มีpสมาชิก สำหรับค่าp ที่เลือกอย่างเหมาะสม (ดูด้านล่าง )

ในส่วนนี้ เราจะแสดงให้เห็นว่าการแยกตัวประกอบบนQ (จำนวนตรรกยะ) และบนZ (จำนวนเต็ม) นั้นโดยพื้นฐานแล้วเป็นปัญหาเดียวกัน

เนื้อหาของพหุนามp ∈ Z [ X ] ซึ่งเขียนแทนด้วย "cont( p )" นั้น คือตัวหารร่วมมากที่สุดของสัมประสิทธิ์ของพหุนามนั้นโดยไม่คำนึงถึงเครื่องหมายส่วนดั้งเดิมของpคือ primpart( p ) =  p /cont( p ) ซึ่งเป็นพหุนามดั้งเดิมที่มีสัมประสิทธิ์เป็นจำนวนเต็ม สิ่งนี้กำหนดการแยกตัวประกอบของpออกเป็นผลคูณของจำนวนเต็มและพหุนามดั้งเดิม การแยกตัวประกอบนี้มีเอกลักษณ์เฉพาะตัว โดยไม่คำนึงถึงเครื่องหมายของเนื้อหา โดยทั่วไปแล้ว มักเลือกเครื่องหมายของเนื้อหาให้สัมประสิทธิ์นำหน้าของส่วนดั้งเดิมเป็นบวก

ตัวอย่างเช่น,

${\displaystyle -10x^{2}+5x+5=(-5)(2x^{2}-x-1)\,}$

เป็นการแยกตัวประกอบออกเป็นเนื้อหาและส่วนประกอบพื้นฐาน

พหุนาม qทุกตัวที่มีสัมประสิทธิ์เป็นจำนวนตรรกยะสามารถเขียนได้ดังนี้

${\displaystyle q={\frac {p}{c}},}$

โดยที่p ∈ Z [ X ] และc ∈ Z : เพียงแค่เลือกc ให้ เป็นพหุคูณของตัวส่วนทั้งหมดของสัมประสิทธิ์ของq (เช่น ผลคูณของสัมประสิทธิ์เหล่านั้น) และp = cq ก็เพียงพอแล้ว เนื้อหาของq ถูกกำหนดดังนี้:

${\displaystyle {\text{cont}}(q)={\frac {{\text{cont}}(p)}{c}},}$

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

ตัวอย่างเช่น,

${\displaystyle {\frac {x^{5}}{3}}+{\frac {7x^{2}}{2}}+2x+1={\frac {2x^{5}+21x^{2}+12x+6}{6}}}$

เป็นการแยกตัวประกอบออกเป็นเนื้อหาและส่วนประกอบพื้นฐาน

เกาส์พิสูจน์ว่าผลคูณของพหุนามดั้งเดิมสองตัวก็เป็นพหุนามดั้งเดิมเช่นกัน ( ทฤษฎีบทของเกาส์ ) นี่หมายความว่าพหุนามดั้งเดิมจะไม่สามารถแยกตัวประกอบได้ในกลุ่ม จำนวนตรรกยะ ก็ต่อเมื่อไม่สามารถแยกตัวประกอบได้ในกลุ่มจำนวนเต็ม นอกจากนี้ยังหมายความว่าการแยกตัวประกอบในกลุ่มจำนวนตรรกยะของพหุนามที่มีสัมประสิทธิ์เป็นจำนวนตรรกยะจะเหมือนกับการแยกตัวประกอบในกลุ่มจำนวนเต็มของส่วนดั้งเดิมของมัน ในทำนองเดียวกัน การแยกตัวประกอบในกลุ่มจำนวนเต็มของพหุนามที่มีสัมประสิทธิ์เป็นจำนวนเต็มจะเป็นผลคูณของการแยกตัวประกอบของส่วนดั้งเดิมกับการแยกตัวประกอบของส่วนประกอบภายในของมัน

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

ทุกสิ่งที่กล่าวมาข้างต้นยังคงเป็นจริง หาก แทนที่ Zด้วยวงแหวนพหุนามเหนือฟิลด์Fและ แทนที่ Qด้วยฟิลด์ของฟังก์ชันตรรกยะเหนือFในตัวแปรเดียวกัน โดยมีความแตกต่างเพียงอย่างเดียวคือ "จนถึงเครื่องหมาย" จะต้องถูกแทนที่ด้วย "จนถึงการคูณด้วยค่าคงที่ผกผันได้ในF " ซึ่งจะลดการแยกตัวประกอบเหนือส่วนขยาย ฟิลด์ อดิศัยบริสุทธิ์ของFไปเป็นการแยกตัวประกอบของพหุนามหลายตัวแปรเหนือF

ถ้าตัวประกอบสองตัวขึ้นไปของพหุนามเหมือนกัน พหุนามนั้นจะเป็นผลคูณของกำลังสองของตัวประกอบนั้น ตัวประกอบที่เป็นผลคูณนั้นยังเป็นตัวประกอบของอนุพันธ์ ของพหุนามนั้นด้วย (เทียบกับตัวแปรใดๆ ถ้ามีตัวแปรหลายตัว)

สำหรับพหุนามตัวแปรเดียว ตัวประกอบหลายตัวเทียบเท่ากับรากหลายตัว (บนฟิลด์ส่วนขยายที่เหมาะสม) สำหรับพหุนามตัวแปรเดียวบนจำนวนตรรกยะ (หรือโดยทั่วไปบนฟิลด์ที่มีลักษณะเฉพาะเป็นศูนย์) อัลกอริทึมของ Yunใช้ประโยชน์จากสิ่งนี้เพื่อแยกตัวประกอบพหุนามออกเป็นตัวประกอบที่ไม่เป็นกำลังสองอย่างมีประสิทธิภาพ กล่าวคือ ตัวประกอบที่ไม่ใช่พหุคูณของกำลังสอง โดยดำเนินการคำนวณตัวหารร่วมมากตามลำดับเริ่มต้นด้วย gcd( f ( x ), f '( x )) ในการแยกตัวประกอบพหุนามเริ่มต้น ก็เพียงพอที่จะแยกตัวประกอบที่ไม่เป็นกำลังสองแต่ละตัว การแยกตัวประกอบที่ไม่เป็นกำลังสองจึงเป็นขั้นตอนแรกในอัลกอริทึมการแยกตัวประกอบพหุนามส่วนใหญ่

อัลกอริทึมของ Yun ขยายแนวคิดนี้ไปสู่กรณีหลายตัวแปร โดยพิจารณาพหุนามหลายตัวแปรเป็นพหุนามตัวแปรเดียวบนวงแหวนพหุนาม

ในกรณีของพหุนามบนฟิลด์จำกัด อัลกอริทึมของ Yun จะใช้ได้ก็ต่อเมื่อดีกรีน้อยกว่าค่าลักษณะเฉพาะเท่านั้น เพราะมิฉะนั้น อนุพันธ์ของพหุนามที่ไม่เป็นศูนย์อาจเป็นศูนย์ (บนฟิลด์ที่มี สมาชิก pตัว อนุพันธ์ของพหุนามในx ^pจะเป็นศูนย์เสมอ) อย่างไรก็ตาม การคำนวณหาตัวหารร่วมมาก (GCD) ต่อเนื่องกัน โดยเริ่มจากพหุนามและอนุพันธ์ของมัน จะช่วยให้สามารถคำนวณการแยกตัวประกอบแบบไร้ตัวประกอบกำลังสองได้ ดูที่การแยกตัวประกอบพหุนามบนฟิลด์จำกัด#การแยกตัวประกอบแบบไร้ตัวประกอบกำลังสอง

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

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

สามารถหาตัวประกอบเชิงเส้นทั้งหมดที่มีสัมประสิทธิ์ เป็นจำนวนตรรกยะได้โดยใช้ การทดสอบรากตรรกยะถ้าพหุนามที่จะแยกตัวประกอบคือแล้วตัวประกอบเชิงเส้นที่เป็นไปได้ทั้งหมดจะมีรูปแบบโดยที่เป็นตัวประกอบจำนวนเต็มของและเป็นตัวประกอบจำนวนเต็มของสามารถทดสอบความถูกต้องของชุดตัวประกอบจำนวนเต็มที่เป็นไปได้ทั้งหมดได้ และแต่ละตัวประกอบที่ถูกต้องสามารถแยกตัวประกอบออกมาได้โดยใช้การหารยาวพหุนามถ้าพหุนามเดิมเป็นผลคูณของตัวประกอบอย่างน้อยสองตัวที่มีดีกรี 2 หรือสูงกว่า เทคนิคนี้จะให้การแยกตัวประกอบเพียงบางส่วนเท่านั้น มิฉะนั้นการแยกตัวประกอบจะสมบูรณ์ โดยเฉพาะอย่างยิ่ง ถ้ามีตัวประกอบที่ไม่ใช่เชิงเส้นเพียงตัวเดียว มันจะเป็นพหุนามที่เหลือหลังจากแยกตัวประกอบเชิงเส้นทั้งหมดออกมาแล้ว ในกรณีของพหุนามกำลังสามถ้าพหุนามกำลังสามสามารถแยกตัวประกอบได้ การทดสอบรากตรรกยะจะให้การแยกตัวประกอบที่สมบูรณ์ ไม่ว่าจะเป็นตัวประกอบเชิงเส้นและตัวประกอบกำลังสองที่ไม่สามารถแยกตัวประกอบได้อีก หรือเป็นตัวประกอบเชิงเส้นสามตัว ${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$${\displaystyle b_{1}x-b_{0}}$${\displaystyle b_{1}}$${\displaystyle a_{n}}$${\displaystyle b_{0}}$${\displaystyle a_{0}}$

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

วิธีนี้ใช้ข้อเท็จจริงที่ว่า การประเมินค่าพหุนามจำนวนเต็มที่ค่าเป็นจำนวนเต็มจะต้องได้ผลลัพธ์เป็นจำนวนเต็ม นั่นคือ ถ้าเป็นพหุนามที่มีสัมประสิทธิ์เป็นจำนวนเต็ม แล้วจะเป็นจำนวนเต็มตราบใดที่aเป็นจำนวนเต็ม มีค่าจำนวนเต็มที่เป็นไปได้สำหรับตัวประกอบของa เพียงจำนวนจำกัดเท่านั้น ดังนั้น ถ้าเป็นตัวประกอบของค่าของจะต้องเป็นหนึ่งในตัวประกอบของ${\displaystyle f(x)}$${\displaystyle f(a)}$${\displaystyle g(x)}$${\displaystyle f(x),}$${\displaystyle g(a)}$${\displaystyle f(a).}$

หากเราค้นหาตัวประกอบทั้งหมดที่มีดีกรีd ที่กำหนด เราสามารถพิจารณาค่าaซึ่งให้ความเป็นไปได้จำนวนจำกัดสำหรับทูเปิลแต่ละตัว โดยแต่ละ ทูเปิล จะมีตัวหารจำนวนจำกัดและแต่ละทูเปิลที่มีสมาชิกเป็นตัวหารของนั่นคือทูเปิลในรูปแบบจะสร้างพหุนามที่ไม่ซ้ำกันที่มีดีกรีไม่เกิน d ซึ่งสามารถคำนวณได้โดยการประมาณค่าพหุนาม พหุนามแต่ละตัวเหล่านี้สามารถทดสอบได้ว่าเป็นตัวประกอบโดยการหารพหุนามเนื่องจากมี a จำนวนจำกัดและแต่ละตัว มีตัวหารจำนวนจำกัด ดังนั้น จึงมีทูเปิลดังกล่าวจำนวนจำกัด ดังนั้น การค้นหาอย่างละเอียดจะช่วยให้พบตัวประกอบทั้งหมดที่มีดีกรีไม่เกินd${\displaystyle d+1}$${\displaystyle a_{0},\ldots ,a_{d}}$${\displaystyle (f(a_{0}),\ldots ,f(a_{d})).}$${\displaystyle f(a_{i})}$${\displaystyle b_{i,0},\ldots ,b_{i,k_{i}}}$${\displaystyle (d+1)}$${\displaystyle i^{\text{th}}}$${\displaystyle f(a_{i})}$${\displaystyle (b_{0,j_{1}},\ldots ,b_{d,j_{d}})}$${\displaystyle d}$${\displaystyle a_{i}}$${\displaystyle f(a_{i})}$

ตัวอย่างเช่น ลองพิจารณาดู

${\displaystyle f(x)=x^{5}+x^{4}+x^{2}+x+2}$.

ถ้าพหุนามนี้สามารถแยกตัวประกอบได้บนZแล้ว อย่างน้อยหนึ่งตัวประกอบของมันจะต้องมีดีกรีสองหรือน้อยกว่า ดังนั้นจึงถูกกำหนดอย่างไม่ซ้ำกันด้วยค่าสามค่าดังนั้น เราจึงคำนวณค่าสามค่า คือ , และถ้าค่าใดค่าหนึ่งเป็น 0 เราจะได้ตัวประกอบเชิงเส้น ถ้าค่าไม่ใช่ศูนย์ เราสามารถแสดงรายการการแยกตัวประกอบที่เป็นไปได้สำหรับแต่ละค่าได้ ตอนนี้ 2 สามารถแยกตัวประกอบได้เพียง เป็น เท่านั้น ${\displaystyle p(x)}$${\displaystyle p(x)}$${\displaystyle f(0)=2}$${\displaystyle f(1)=6}$${\displaystyle f(-1)=2}$

1×2, 2×1, (−1)×(−2) หรือ (−2)×(−1)

ดังนั้น หากมีตัวประกอบพหุนามจำนวนเต็มดีกรีสองอยู่ ตัวประกอบนั้นจะต้องมีค่าใดค่าหนึ่งต่อไปนี้

p (0) = 1, 2, −1 หรือ −2

และเช่นเดียวกันสำหรับp (−1) มีการแยกตัวประกอบของ 6 อยู่แปดแบบ (แบบละสี่แบบสำหรับ 1×6 และ 2×3) ทำให้มีสามตัวเลขที่เป็นไปได้ทั้งหมด 4×4×8 = 128 แบบ ( p (0), p (1), p (−1)) ซึ่งครึ่งหนึ่งสามารถตัดทิ้งได้เนื่องจากเป็นค่าลบของอีกครึ่งหนึ่ง ดังนั้น เราต้องตรวจสอบพหุนามจำนวนเต็ม 64 ตัวอย่างชัดเจนว่าเป็นตัวประกอบที่เป็นไปได้ของการทดสอบอย่างละเอียดถี่ถ้วนเผยให้เห็นว่า ${\displaystyle p(x)=ax^{2}+bx+c}$${\displaystyle f(x)}$

${\displaystyle p(x)=x^{2}+x+1}$

สร้างจากปัจจัย ( g (0), g (1), g (−1)) = (1,3,1 ) ${\displaystyle f(x)}$

การหารf ( x ) ด้วยp ( x ) จะได้ตัวประกอบอีกตัวหนึ่งดังนั้นตอนนี้เราสามารถทดสอบแบบเวียนซ้ำเพื่อหาตัวประกอบของp ( x ) และq ( x ) ในกรณีนี้โดยใช้การทดสอบรากตรรกยะ ปรากฏว่าทั้งสองตัวประกอบไม่สามารถแยกตัวประกอบได้ ดังนั้นการแยกตัวประกอบที่ไม่สามารถแยกตัวประกอบได้ของf ( x ) คือ: ^{[ 5 ]}${\displaystyle q(x)=x^{3}-x+2}$${\displaystyle f(x)=p(x)q(x)}$

${\displaystyle f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2).}$

ถ้าเป็นพหุนามตัวแปรเดียวเหนือจำนวนเต็ม ซึ่งถือว่าไม่มีเนื้อหาและไม่มีตัวประกอบกำลังสองเราจะเริ่มต้นด้วยการคำนวณขอบเขตที่ทำให้สัมประสิทธิ์ ของ ตัวประกอบใด ๆมีค่าสัมบูรณ์ที่จำกัดโดย ด้วยวิธีนี้ ถ้าเป็นจำนวนเต็มที่มากกว่าและถ้าเป็นที่ทราบค่าโมดูลัสแล้วสามารถสร้างใหม่ได้จากภาพโมดูลัสของมัน ${\displaystyle f(x)}$${\displaystyle B}$${\displaystyle g(x)}$${\displaystyle B}$${\displaystyle m}$${\displaystyle 2B}$${\displaystyle g(x)}$${\displaystyle m}$${\displaystyle g(x)}$${\displaystyle m}$

อัลกอริทึม ของZassenhausดำเนินการดังนี้ ขั้นแรก เลือกจำนวนเฉพาะที่ทำให้ภาพของยังคงเป็นจำนวนที่ไม่มีตัวประกอบกำลังสองและมีดีกรีเท่ากับการเลือกแบบสุ่มมักจะตรงตามเงื่อนไขเหล่านี้เสมอ เนื่องจากมีเพียงจำนวนเฉพาะจำนวนจำกัดเท่านั้นที่ไม่ตรงตามเงื่อนไขเหล่านี้ ได้แก่ ตัวหารเฉพาะของผลคูณของดิสคริมิแนนต์และสัมประสิทธิ์นำของพหุนาม จาก นั้นแยกตัวประกอบ ซึ่งจะสร้างพหุนามจำนวนเต็มที่มีผลคูณตรงกับ ต่อไป ใช้การยกกำลังของ Henselซึ่งจะอัปเดตในลักษณะที่ผลคูณของพวกมันตรงกับ โดยที่มีขนาดใหญ่พอที่เกิน: ดังนั้นแต่ละ จึงสอดคล้องกับพหุนามจำนวนเต็มที่กำหนดไว้อย่างดี มอดูลพหุนามจะมีตัวประกอบ (ไม่เกินหน่วย) คือ ผลคูณของเซตย่อยทั้งหมดของ ตัวประกอบเหล่านี้มอดูลไม่จำเป็นต้องสอดคล้องกับตัวประกอบ "จริง" ของในแต่เราสามารถทดสอบได้ง่ายๆ โดยการหารใน ด้วยวิธีนี้ สามารถหาตัวประกอบจริงที่ไม่สามารถแยกตัวประกอบได้ทั้งหมดโดยการตรวจสอบกรณีอย่างมากที่สุด ลดลงเหลือกรณีโดยการข้ามส่วนเติมเต็ม หากสามารถลดรูปได้ จำนวนกรณีจะลดลงไปอีกโดยการลบกรณีที่ปรากฏในปัจจัยที่เป็นจริงที่พบแล้วออกไป อัลกอริทึมของ Zassenhaus ประมวลผลแต่ละกรณี (แต่ละเซตย่อย) อย่างรวดเร็ว อย่างไรก็ตาม ในกรณีที่เลวร้ายที่สุด มันจะพิจารณากรณีจำนวนมหาศาลแบบเลขชี้กำลัง ${\displaystyle p}$${\displaystyle f(x){\bmod {p}}}$${\displaystyle f(x)}$${\displaystyle f(x){\bmod {p}}}$${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$${\displaystyle f(x){\bmod {p}}}$${\displaystyle f_{i}(x)}$${\displaystyle f(x){\bmod {p}}^{a}}$${\displaystyle a}$${\displaystyle p^{a}}$${\displaystyle 2B}$${\displaystyle f_{i}(x)}$${\displaystyle p^{a}}$${\displaystyle f(x)}$${\displaystyle 2^{r}}$${\displaystyle \{f_{1}(x),\ldots ,f_{r}(x)\}{\bmod {p}}^{a}}$${\displaystyle p^{a}}$${\displaystyle f(x)}$${\displaystyle \mathbb {Z} [x]}$${\displaystyle \mathbb {Z} [x]}$${\displaystyle 2^{r}}$${\displaystyle 2^{r-1}}$${\displaystyle f(x)}$${\displaystyle f_{i}(x)}$

อัลกอริทึม เวลาพหุนามแรกสำหรับการแยกตัวประกอบพหุนามเชิงตรรกะถูกค้นพบโดย Lenstra, Lenstra และ Lovász และเป็นการประยุกต์ใช้ อัลกอริทึม การลดฐานแลตติซ Lenstra–Lenstra–Lovász (LLL) ^{[ 6 ]}

อัลกอริทึมการแยกตัวประกอบ LLL เวอร์ชันที่ง่ายขึ้นมีดังนี้: คำนวณรากเชิงซ้อน (หรือp -adic) α ของพหุนามด้วยความแม่นยำสูง จากนั้นใช้อัลกอริทึมการลดฐานแลตติส Lenstra–Lenstra–Lovászเพื่อหาความสัมพันธ์เชิงเส้น โดยประมาณ ระหว่าง 1, α , α ² , α ³ , . . . โดยมีสัมประสิทธิ์เป็นจำนวนเต็ม ซึ่งอาจเป็นความสัมพันธ์เชิงเส้นที่แน่นอนและตัวประกอบพหุนามของα ก็ได้ เราสามารถกำหนดขอบเขตของความแม่นยำที่รับประกันได้ว่าวิธีนี้จะสร้างตัวประกอบหรือการพิสูจน์ความไม่สามารถลดทอนได้ แม้ว่าวิธีนี้จะเสร็จสิ้นในเวลาพหุนาม แต่ก็ไม่ได้ใช้ในทางปฏิบัติเนื่องจากแลตติสมีมิติสูงและมีจำนวนรายการมาก ทำให้การคำนวณช้าลง ${\displaystyle f(x)}$${\displaystyle f(x)}$

ความซับซ้อนแบบเลขชี้กำลังในอัลกอริทึม Zassenhaus มาจากปัญหาเชิงการจัดเรียง: วิธีการเลือกเซตย่อยที่ถูกต้องของการใช้งานการแยกตัวประกอบที่ทันสมัยทำงานในลักษณะที่คล้ายกับ Zassenhaus ยกเว้นว่าปัญหาเชิงการจัดเรียงจะถูกแปลงเป็นปัญหาแลตติส จากนั้นจึงแก้ไขโดย LLL ^{[ 7 ]}ในแนวทางนี้ LLL ไม่ได้ใช้ในการคำนวณสัมประสิทธิ์ของตัวประกอบ แต่ใช้ในการคำนวณเวกเตอร์ที่มีรายการใน {0,1} ที่เข้ารหัสเซตย่อยของที่สอดคล้องกับตัวประกอบที่แท้จริงที่ไม่สามารถแยกย่อยได้ ${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$${\displaystyle r}$${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$

เราสามารถแยกตัวประกอบพหุนามโดยที่ฟิลด์เป็นส่วนขยายจำกัดของก่อนอื่น โดยใช้การแยกตัวประกอบแบบไม่มีตัวประกอบกำลังสองเราอาจสมมติว่าพหุนาม ไม่มีตัวประกอบกำลังสอง ต่อไป เรากำหนดวงแหวนผลหารดีกรี; นี่ไม่ใช่ฟิลด์เว้นแต่จะไม่สามารถแยกตัวประกอบได้ แต่เป็นวงแหวนลดรูปเนื่องจากไม่มีตัวประกอบกำลังสอง อันที่จริง ถ้า${\displaystyle p(x)\in K[x]}$${\displaystyle K}$${\displaystyle \mathbb {Q} }$${\displaystyle L=K[x]/p(x)}$${\displaystyle n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]}$${\displaystyle p(x)}$${\displaystyle p(x)}$

${\displaystyle p(x)=\prod _{i=1}^{m}p_{i}(x)}$

คือการแยกตัวประกอบที่ต้องการของp ( x ) วงแหวนจะแยกออกเป็นฟิลด์ที่ไม่ซ้ำกันดังนี้:

${\displaystyle L=K[x]/p(x)\cong \prod _{i=1}^{m}K[x]/p_{i}(x).}$

เราจะหาการแยกส่วนนี้โดยไม่ทราบการแยกตัวประกอบ ก่อนอื่น เราเขียนLอย่างชัดเจนในรูปพีชคณิตเหนือ: เราเลือกองค์ประกอบแบบสุ่มซึ่งสร้างเหนือด้วยความน่าจะเป็นสูงโดยทฤษฎีบทองค์ประกอบดั้งเดิมถ้าเป็นเช่นนั้น เราสามารถคำนวณพหุนามขั้นต่ำของเหนือได้โดยการพบความสัมพันธ์เชิงเส้นระหว่าง 1, α , . . . , α ⁿโดยใช้อัลกอริทึมการแยกตัวประกอบสำหรับพหุนามตรรกยะ เราแยกตัวประกอบเป็นตัวที่ไม่สามารถแยกได้ใน: ${\displaystyle \mathbb {Q} }$${\displaystyle \alpha \in L}$${\displaystyle L}$${\displaystyle \mathbb {Q} }$${\displaystyle q(y)\in \mathbb {Q} [y]}$${\displaystyle \alpha }$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {Q} [y]}$

${\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y).}$

ดังนั้นเราจึงได้ว่า:

${\displaystyle L\cong \mathbb {Q} [y]/q(y)\cong \prod _{i=1}^{n}\mathbb {Q} [y]/q_{i}(y),}$

โดยที่สอดคล้องกับซึ่งจะต้องสมมาตรกับการแยกส่วนก่อนหน้าของ ${\displaystyle \alpha }$${\displaystyle y\leftrightarrow (y,y,\ldots ,y)}$${\displaystyle L}$

ตัวสร้างของLคือxพร้อมกับตัวสร้างของเหนือ; เมื่อเขียนสิ่งเหล่านี้เป็นพหุนามในเราสามารถกำหนดการฝังตัวของและลงในแต่ละส่วนประกอบได้ โดยการหาพหุนามขั้นต่ำของในเราคำนวณและแยกตัวประกอบเหนือ${\displaystyle K}$${\displaystyle \mathbb {Q} }$${\displaystyle \alpha }$${\displaystyle x}$${\displaystyle K}$${\displaystyle \mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)}$${\displaystyle x}$${\displaystyle \mathbb {Q} [y]/q_{i}(y)}$${\displaystyle p_{i}(x)}$${\displaystyle p(x)}$${\displaystyle K.}$

โดยทั่วไป พหุนามส่วนใหญ่ไม่มีรากที่สอง อย่างไรก็ตาม การใช้งานบางอย่าง เช่น หน้าที่ของวิศวกรไฟฟ้าในการหาค่าพารามิเตอร์ Y จากอิมพีแดนซ์จุดขับของเครือข่ายสองพอร์ต^{[ 8 ]}จะใช้พหุนามกำลังสองที่ต้องแยกตัวประกอบเป็นพหุนามรากที่สองที่เหมือนกันสองตัว อัลกอริทึมด้านล่างจะแยกตัวประกอบพหุนามกำลังสองออกเป็นรากพหุนามที่เหมือนกันสองตัวโดยใช้ตัวอย่างจากMathematics Stack Exchange ^{[ 9 ] [ 10 ]}${\displaystyle {\sqrt {x^{6}-6x^{5}+17x^{4}-36x^{3}+52x^{2}+48x+36}}}$${\displaystyle R=X^{3}-3x^{2}+4x-6}$

${\displaystyle {\begin{aligned}&{\begin{array}{|l|l|l|}\hline Q&R&R(2Q+R)\\\hline \\0&x^{3}&x^{6}\\\hline \\x^{3}&-3x^{2}&6x^{5}-9x^{4}\\\hline \\x^{3}-3x^{2}&4x&8x^{4}-24x^{3}+16x^{2}\\\hline \\x^{3}-3x^{2}+4x&-6&-12x^{3}+36x^{2}-48x+36\\\hline \end{array}}&{\begin{array}{|c|c|c|c|c|c|c|c|}\hline R&x^{3}&&-3x^{2}&&4x&&-6\\\hline 1&x^{6}&-6x^{5}&17x^{4}&-36x^{3}&52x^{2}&48x&36\\&x^{6}&&&&&&\\\hline 2&&-6x^{5}&17x^{4}&&&&\\&&-6x^{5}&9x^{4}&&&&\\\hline 3&&&8x^{4}&-36x^{3}&52x^{2}&&\\&&&8x^{4}&-24x^{3}&16x^{2}&&\\\hline 4&&&&-12x^{3}&36x^{2}&-48x&36\\&&&&-12x^{3}&36x^{2}&-48x&36\\\hline \end{array}}\end{aligned}}}$

ขั้นตอน:

ขั้นตอนที่ 1: คำนวณรากที่สองของพจน์นำหน้าและวางรากที่สองนั้น ไว้ในแถวแรกของพหุนามคำตอบ R และวางพจน์นั้นไว้ในแถวที่ 1 ใต้พหุนามที่จะแยกตัวประกอบ ดังแสดงในภาพ ${\displaystyle x^{6}}$${\displaystyle x^{3}}$${\displaystyle x^{6}}$

ขั้นตอนที่ 2:ลบพจน์ที่เพิ่งวางใหม่จากพหุนามที่จะแยกตัวประกอบ แล้วนำพจน์สองพจน์ถัดไปลงมาไว้ในแถวที่ 2 ${\displaystyle x^{6}}$

ขั้นตอนที่ 3 : คูณค่าปัจจุบันของพหุนาม R ที่เป็นคำตอบด้วย 2 จากนั้นเพิ่มพจน์ใหม่ Q โดยที่ R(2Q+R) จะทำให้พจน์นำของแถวที่ 2 กลับเป็นค่าลบ และวางค่าลบของ R(2Q+R) ไว้ในช่องด้านล่างของแถวที่ 2

ขั้นตอนที่ 4:ลบตัวเลขสองตัวในแถวที่ 2 นำผลลัพธ์ไปใส่ในแถวที่ 3 และนำพจน์สองตัวถัดไปจากแถวที่ 1 มาใส่ในแถวที่ 3

ขั้นตอนที่ 5:ทำซ้ำขั้นตอนนี้สำหรับแถวและคอลัมน์ที่เหลือทั้งหมดจนเสร็จสมบูรณ์

เมื่อเสร็จสมบูรณ์แล้ว พหุนาม R ที่เป็นคำตอบจะปรากฏในคอลัมน์ R ในตารางด้านซ้าย และแถว R ในตารางด้านขวา

อัลกอริทึมการหาค่ารากที่สองของพหุนามข้างต้นสามารถสรุปและวางนัยทั่วไปเป็นไวยากรณ์ทางคณิตศาสตร์มาตรฐานเพื่อใช้ในการหาค่ารากที่สองจากพหุนามกำลังสองขนาดใดก็ได้ และสามารถแปลงเป็นภาษาคอมพิวเตอร์ ได้อย่างง่ายดาย เพื่อใช้ในการคำนวณอย่างรวดเร็ว หากพจน์ที่มีอันดับสูงสุดของพหุนามกำลังสองไม่ใช่ 1 พหุนามจะต้องได้รับการประมวลผลเบื้องต้นโดยการหารด้วยค่าของพจน์ที่มีอันดับสูงสุดก่อน จากนั้นตัวประกอบพหุนามที่แยกออกมาจะต้องได้รับการประมวลผลเพิ่มเติมโดยการคูณด้วยค่ารากที่สองของค่าเดียวกัน สรุปทางคณิตศาสตร์ทั่วไปได้ดังนี้:

${\displaystyle {\begin{aligned}n&={\text{order of the squared polynomial being factored}}\\m&={\text{order of the extracted square root polynomial}}=n/2\\S&{\text{ is the squared polynomial, indexed in powers of x, and normalized to the highest order term value of 1}}\\R&{\text{ is the square root polynomial, indexed in powers of x, and with the highest order term initialized to 1}}\\T&{\text{ and }}D{\text{ are vectors of length n, with all entries initialized to 0}}\\\\&\sum _{i=1}^{m}{{\Bigg [}{\Big (}\sum _{k=i}^{0}}D_{n-i-k}={\begin{cases}S_{n-i-k},&{\text{if }}k\geq i-1\\D_{n-i-k}-T_{n-i-k},&{\text{if }}k<i-1\end{cases}}{\Big )}{\text{ ;}}\quad R_{m-i}={\frac {D_{n-i}}{2}}{\text{ ;}}\quad T_{n-i}=D_{n-i}{\text{ ;}}\quad {\Big (}\sum _{k=1}^{i}{T_{n-i-k}={\begin{cases}R_{m-k}D_{n-i},&{\text{if }}k<i\\R_{m-k}R_{m-i},&{\text{if }}k\geq i\end{cases}}{\Big )}{\Bigg ]}}\end{aligned}}}$.

โปรดทราบว่าเมื่อคำนวณค่าสำหรับ แล้วพหุนาม R ก็เสร็จสมบูรณ์ และการคำนวณต่อไปนี้อาจถูกละเลยได้ เนื่องจากผลลัพธ์จะไม่ถูกนำมาใช้หลังจากนั้น แต่หากดำเนินการ ผลลัพธ์อาจใช้เป็นตัวตรวจสอบความถูกต้องเพื่อให้แน่ใจว่าพหุนาม S เป็นพหุนามกำลังสอง และอัลกอริทึมทำงานอย่างถูกต้องโดยการตรวจสอบให้แน่ใจว่าค่าสุดท้ายของเวกเตอร์ T และ D เหมือนกัน ดังที่เห็นในตาราง ${\displaystyle R_{m-i}}$${\displaystyle i=m}$${\displaystyle T_{n-i}}$${\displaystyle T_{n-i-k}}$

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

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

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

ให้เป็นพหุนามที่มีสัมประสิทธิ์เชิงซ้อนและมีตัวประกอบที่ไม่สามารถแยกตัวประกอบได้ ${\displaystyle p}$

${\displaystyle p=\alpha p_{1}^{m_{1}}\cdots p_{k}^{m_{k}}}$

โดยที่และตัวประกอบเป็นพหุนามที่ไม่สามารถแยกตัวประกอบได้ซึ่งมีสัมประสิทธิ์เป็นจำนวนเชิงซ้อน สมมติว่าถูกประมาณค่าด้วยพหุนามที่มีสัมประสิทธิ์ใกล้เคียงกับของการแยกตัวประกอบที่แน่นอนของ นั้นไม่มีประโยชน์ เนื่องจากโดยทั่วไปแล้วไม่สามารถแยกตัวประกอบได้ มีคำจำกัดความที่เป็นไปได้หลายประการสำหรับสิ่งที่เรียกว่าการแยกตัวประกอบเชิงตัวเลขของ${\displaystyle \alpha \in C}$${\displaystyle p_{1},\ldots ,p_{k}}$${\displaystyle p}$${\displaystyle {\tilde {p}}}$${\displaystyle p}$${\displaystyle {\tilde {p}}}$${\displaystyle {\tilde {p}}.}$

ถ้าทราบค่าและ 's การแยกตัวประกอบโดยประมาณประกอบด้วยการหาพหุนามที่ใกล้เคียงกับ พหุนามที่แยกตัวประกอบได้ดังข้างต้น หากไม่ทราบแผนการแยกตัวประกอบ การระบุค่าจึงกลายเป็นสิ่งจำเป็น ตัวอย่างเช่น จำนวนตัวประกอบที่ไม่สามารถแยกตัวประกอบได้ของพหุนามคือค่าศูนย์ของเมทริกซ์ Ruppert ^{[ 11 ]}ดังนั้น ความซ้ำซ้อนสามารถระบุได้โดย การ แยกตัวประกอบแบบไร้กำลังสองผ่านการคำนวณ GCD เชิงตัวเลขและการเปิดเผยอันดับบนเมทริกซ์ Ruppert ${\displaystyle k}$${\displaystyle m_{i}}$${\displaystyle {\tilde {p}}}$${\displaystyle m_{1},\ldots ,m_{k}}$${\displaystyle m_{1},\ldots ,m_{k}}$

มีการพัฒนาและนำอัลกอริธึมหลายตัวมาใช้ในการแยกตัวประกอบเชิงตัวเลข ซึ่งเป็นหัวข้อการวิจัยที่กำลังดำเนินอยู่^{[ 12 ] [ 13 ]}

• การแยกตัวประกอบ § พหุนามสำหรับวิธีการเชิงอนุมานเบื้องต้นและสูตรที่ชัดเจน
• พหุนามสวินเนอร์ตัน-ไดเออร์ (Swinnerton-Dyer polynomials)คือตระกูลของพหุนามที่มีเวลาการทำงานกรณีเลวร้ายที่สุดสำหรับวิธีของซัสเซนเฮาส์ (Zassenhaus method)

• โฟรห์ลิช, อ. ; Shepherson, JC (1955), "เกี่ยวกับการแยกตัวประกอบของพหุนามในจำนวนขั้นตอนที่จำกัด", Mathematische Zeitschrift , 62 (1): 331– 334, doi : 10.1007/BF01180640 , ISSN  0025-5874 , S2CID  119955899
• Trager, BM (1976). "การแยกตัวประกอบเชิงพีชคณิตและการอินทิเกรตฟังก์ชันตรรกยะ". รายงานการประชุมสัมมนาวิชาการ ACM ครั้งที่สามว่าด้วยการคำนวณเชิงสัญลักษณ์และพีชคณิต - SYMSAC '76หน้า  219–226 . doi : 10.1145/800205.806338 . ISBN 9781450377904S2CID 16567619​ ​
• Bernard Beauzamy, Per Enflo , Paul Wang (ตุลาคม 1994). "การประมาณเชิงปริมาณสำหรับพหุนามในตัวแปรเดียวหรือหลายตัวแปร: จากการวิเคราะห์และทฤษฎีจำนวนไปสู่การคำนวณเชิงสัญลักษณ์และแบบขนานขนาดใหญ่" Mathematics Magazine . 67 (4): 243– 257. doi : 10.2307/2690843 . JSTOR  2690843 .{{cite journal}}: CS1 maint: multiple names: authors list (link)(เหมาะสำหรับผู้อ่านที่มีความรู้คณิตศาสตร์ระดับปริญญาตรี)
• โคเฮน, อองรี (1993). หลักสูตรทฤษฎีจำนวนพีชคณิตเชิงคำนวณ . ตำราเรียนคณิตศาสตร์ระดับบัณฑิตศึกษา เล่มที่ 138. เบอร์ลิน, นิวยอร์ก: สปริงเกอร์-เวอร์แลก . ISBN 978-3-540-55640-4. MR  1228206 .
• Kaltofen, Erich (1982), "การแยกตัวประกอบของพหุนาม" ใน B. Buchberger; อาร์. ลูส; G. Collins (บรรณาธิการ), พีชคณิตคอมพิวเตอร์ , Springer Verlag, หน้า  95– 113, CiteSeerX  10.1.1.39.7916
• Knuth, Donald E (1997). "4.6.2 การแยกตัวประกอบของพหุนาม" อัลกอริทึมเชิงตัวเลข ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์เล่ม 2 (ฉบับที่สาม). เรดดิง รัฐแมสซาชูเซตส์: Addison-Wesley. หน้า  439–461 , 678–691 . ISBN 978-0-201-89684-8.
• Van der Waerden , พีชคณิต (1970), ทรานส์. บลัม และชูเลนเบอร์เกอร์, เฟรเดอริก อุงการ์.

• Kaltofen, Erich (1990), "การแยกตัวประกอบพหุนาม 1982-1986", ใน DV Chudnovsky; RD Jenks (บรรณาธิการ), คอมพิวเตอร์ในคณิตศาสตร์ , บันทึกการบรรยายในคณิตศาสตร์บริสุทธิ์และประยุกต์, เล่มที่ 125, Marcel Dekker, Inc., CiteSeerX  10.1.1.68.7461
• Kaltofen, Erich (1992), "การแยกตัวประกอบพหุนาม 1987–1991" (PDF) , รายงานการประชุม Latin '92 , Springer Lect. Notes Comput. Sci., เล่มที่ 583, Springer , สืบค้นเมื่อ14 ตุลาคม 2012
• Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009). "Schemes for deterministic polynomial factoring". Proceedings of the 2009 international symposium on Symbolic and algebraic computation . pp.  191– 198. arXiv : 0804.1974 . doi : 10.1145/1576702.1576730 . ISBN 9781605586090S2CID 15895636​ ​