ในทางคณิตศาสตร์พหุนามที่ไม่มีรากซ้ำซ้อนคือพหุนามเอกตัวแปร (เหนือฟิลด์หรือโดเมนอินทิกรัล ) ที่ไม่มีรากซ้ำซ้อนในฟิลด์ปิดเชิงพีชคณิตที่มีสัมประสิทธิ์ของมัน ในลักษณะเฉพาะ 0 หรือเหนือฟิลด์จำกัดพหุนามเอกตัวแปรจะเป็นพหุนามที่ไม่มีรากซ้ำซ้อนก็ต่อเมื่อมันไม่มีตัวหารเป็นกำลังสองของพหุนามที่ไม่ใช่ค่าคงที่ [ ^{1 ] ใน} การประยุกต์ใช้ในฟิสิกส์และวิศวกรรม พหุนามที่ไม่มีรากซ้ำซ้อนมักเรียกว่าพหุ นามที่ไม่มีรากซ้ำซ้อน

กฎผลคูณบ่งชี้ว่า ถ้าp ² หาร fลงตัวแล้วpจะหารอนุพันธ์ อย่างเป็นทางการ f ′ของf ลงตัว ส่วนกลับก็เป็นจริงเช่นกัน ดังนั้นจะเป็นพหุนามที่ไม่มีตัวประกอบกำลังสองก็ต่อเมื่อเป็นตัวหารร่วมมากที่สุดของพหุนามและอนุพันธ์ของมัน^{[ 2 ]}${\displaystyle f}$${\displaystyle 1}$

การแยกตัวประกอบแบบไม่ขึ้นกับกำลังสองหรือการแยกตัวประกอบแบบไม่ขึ้นกับกำลังสองของพหุนาม คือการแยกตัวประกอบออกเป็นกำลังของพหุนามแบบไม่ขึ้นกับกำลังสอง

${\displaystyle f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{n}^{n}=\prod _{k=1}^{n}a_{k}^{k}\,}$

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

บนฟิลด์ที่มีลักษณะเฉพาะเป็น 0 ผลหารของพหุนามโดยตัวหารร่วมมาก (GCD) กับอนุพันธ์ของพหุนามนั้นคือผลคูณของพหุนามในการแยกตัวประกอบแบบไร้กำลังสองข้างต้น บนฟิลด์สมบูรณ์ที่มีลักษณะเฉพาะp ที่ไม่เป็นศูนย์ ผลหารนี้คือผลคูณของพหุ นาม โดยที่iไม่ใช่พหุคูณของpการคำนวณ GCD เพิ่มเติมและการหารที่แม่นยำช่วยให้สามารถคำนวณการแยกตัวประกอบแบบไร้กำลังสองได้ (ดูการแยกตัวประกอบแบบไร้กำลังสองบนฟิลด์จำกัด ) ในลักษณะเฉพาะเป็นศูนย์ มีอัลกอริทึมที่ดีกว่าที่เป็นที่รู้จัก คือ อัลกอริทึมของ Yun ซึ่งจะอธิบายไว้ด้านล่าง^{[ 1 ]}ความซับซ้อนใน การคำนวณของอัลกอริทึม นี้มีค่าสูงสุดเป็นสองเท่าของการคำนวณ GCD ของพหุนามอินพุตและอนุพันธ์ของพหุนามนั้น กล่าวคือ ถ้าคือเวลาที่จำเป็นในการคำนวณ GCD ของพหุนามสองตัวที่มีดีกรีและผลหารของพหุนามเหล่านี้โดย GCD แล้วจะเป็นขอบเขตบนสำหรับเวลาที่จำเป็นในการคำนวณการแยกตัวประกอบแบบไร้กำลังสองที่สมบูรณ์${\displaystyle f}$${\displaystyle a_{i}}$${\displaystyle a_{i}}$${\displaystyle T_{n}}$${\displaystyle n}$${\displaystyle 2T_{n}}$

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

ส่วนนี้อธิบายอัลกอริทึมของ Yun สำหรับการแยกตัวประกอบแบบไร้กำลังสองของพหุนามเอกตัวแปรเหนือฟิลด์ที่ มีลักษณะ เฉพาะ0 ^{[ 1 ]}โดยดำเนินการตามลำดับของ การคำนวณ GCDและการหารที่แม่นยำ

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

ถ้า

${\displaystyle f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{k}^{k}}$

หากเป็นการแยกตัวประกอบที่ต้องการ เราจึงได้ดังนี้

${\displaystyle a_{0}=a_{2}^{1}a_{3}^{2}\cdots a_{k}^{k-1},}$

${\displaystyle f/a_{0}=a_{1}a_{2}a_{3}\cdots a_{k}}$

และ

${\displaystyle f'/a_{0}=\sum _{i=1}^{k}ia_{i}'a_{1}\cdots a_{i-1}a_{i+1}\cdots a_{k}.}$

ถ้าเรากำหนดและเราจะได้ว่า${\displaystyle b_{1}=f/a_{0}}$${\displaystyle c_{1}=f'/a_{0}}$${\displaystyle d_{1}=c_{1}-b_{1}'}$

${\displaystyle \gcd(b_{1},d_{1})=a_{1},}$

${\displaystyle b_{2}=b_{1}/a_{1}=a_{2}a_{3}\cdots a_{n},}$

และ

${\displaystyle c_{2}=d_{1}/a_{1}=\sum _{i=2}^{k}(i-1)a_{i}'a_{2}\cdots a_{i-1}a_{i+1}\cdots a_{k}.}$

ทำซ้ำกระบวนการนี้ไปเรื่อยๆ จนกว่า เราจะพบทั้งหมด${\displaystyle b_{k+1}=1}$${\displaystyle a_{i}.}$

สิ่งนี้ได้รับการกำหนดเป็นอัลกอริทึมอย่างเป็นทางการดังต่อไปนี้:

${\displaystyle a_{0}:=\gcd(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;}$ ทำซ้ำ จนกว่า จะได้ผลลัพธ์ ${\displaystyle a_{i}:=\gcd(b_{i},d_{i});\quad b_{i+1}:=b_{i}/a_{i};\quad c_{i+1}:=d_{i}/a_{i};\quad i:=i+1;\quad d_{i}:=c_{i}-b_{i}';}$${\displaystyle b_{i}=1;}$${\displaystyle a_{1},\ldots ,a_{i-1}.}$

ระดับของและน้อยกว่าระดับของ อยู่หนึ่งระดับเนื่องจากเป็นผลคูณของ ผลรวมของระดับของคือระดับของเนื่องจากความซับซ้อนของการคำนวณ GCD และการหารเพิ่มขึ้นมากกว่าเชิงเส้นตามระดับ จึงสรุปได้ว่าเวลาทำงานทั้งหมดของลูป "ทำซ้ำ" น้อยกว่าเวลาทำงานของบรรทัดแรกของอัลกอริทึม และเวลาทำงานทั้งหมดของอัลกอริทึมของ Yun มีค่าสูงสุดไม่เกินสองเท่าของเวลาที่จำเป็นในการคำนวณ GCD ของและและผลหารของและด้วย GCD ของพวกมัน${\displaystyle c_{i}}$${\displaystyle d_{i}}$${\displaystyle b_{i}.}$${\displaystyle f}$${\displaystyle b_{i},}$${\displaystyle b_{i}}$${\displaystyle f.}$${\displaystyle f}$${\displaystyle f'}$${\displaystyle f}$${\displaystyle f'}$

โดยทั่วไป พหุนามไม่มีรากที่สองของ พหุนาม กล่าวให้แม่นยำยิ่งขึ้น พหุนามส่วนใหญ่ไม่สามารถเขียนให้อยู่ในรูปกำลังสองของพหุนามอื่นได้

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

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