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

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

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

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

ฟิลด์จำกัดหรือฟิลด์กาโลอิสคือฟิลด์ที่มี อันดับ จำกัด (จำนวนสมาชิก) อันดับของฟิลด์จำกัดจะเป็นจำนวนเฉพาะหรือกำลังของจำนวนเฉพาะเสมอ สำหรับกำลังของจำนวนเฉพาะq = p ^r แต่ละตัว จะมีฟิลด์จำกัดที่มีสมาชิกq ตัวเพียงหนึ่งเดียวเท่านั้น โดยพิจารณาจากความเหมือนกัน ฟิลด์นี้เขียนแทนด้วยGF ( q ) หรือF _qถ้าpเป็นจำนวนเฉพาะGF ( p ) คือฟิลด์จำนวนเฉพาะที่มีอันดับpมันคือฟิลด์ของชั้นเศษเหลือมอดูล pและ สมาชิก p ตัวของมัน จะเขียนแทนด้วย 0, 1, ..., p −1 ดังนั้นa = bในGF ( p ) จึงมีความหมายเหมือนกับa ≡ b ( mod p )

ให้Fเป็นฟิลด์จำกัด เช่นเดียวกับฟิลด์ทั่วไป พหุนามf ที่ไม่ใช่ค่าคงที่ ในF [ x ] จะเรียกว่าไม่สามารถแยกตัวประกอบได้ในFถ้ามันไม่ใช่ผลคูณของพหุนามสองตัวที่มีดีกรีเป็นบวก พหุนามที่มีดีกรีเป็นบวกที่ไม่สามารถแยกตัวประกอบได้ในFเรียกว่า สามารถแยกตัวประกอบ ได้ ในF

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

ดังนั้น เพื่อคำนวณในฟิลด์จำกัดที่มีอันดับไม่เป็นจำนวนเฉพาะ จำเป็นต้องสร้างพหุนามที่ไม่สามารถแยกตัวประกอบได้ สำหรับเรื่องนี้ วิธีทั่วไปคือการเลือกพหุนามแบบสุ่มและทดสอบว่าไม่สามารถแยกตัวประกอบได้หรือไม่ เพื่อประสิทธิภาพของการคูณในฟิลด์ มักจะค้นหาพหุนามที่มี^{รูปร่าง} x ⁿ + ax + b ^{[ 1} ]

พหุนามที่ไม่สามารถแยกตัวประกอบได้เหนือฟิลด์จำกัดยังมีประโยชน์สำหรับ ตัว สร้าง เลข สุ่มเทียมโดยใช้รีจิสเตอร์เลื่อนป้อนกลับและลอการิทึมแบบไม่ต่อเนื่องเหนือF _{2 ⁿ}

จำนวนพหุนามเอกลักษณ์ ที่ไม่สามารถแยกตัวประกอบได้ ที่มีดีกรี n เหนือF _qคือจำนวนสร้อยคอที่ไม่เป็นคาบซึ่งกำหนดโดยฟังก์ชันการนับสร้อยคอของ Moreau M _q ( n ) ฟังก์ชันสร้อยคอที่เกี่ยวข้องอย่างใกล้ชิดN _q ( n ) นับพหุนามเอกลักษณ์ที่มีดีกรีnซึ่งเป็นพหุนามหลัก (กำลังของพหุนามที่ไม่สามารถแยกตัวประกอบได้) หรือพหุนามที่ไม่สามารถแยกตัวประกอบได้ที่มีดีกรี d ทั้งหมดซึ่งหาร n ลงตัว^{[ 2 ]}

พหุนามP = x ⁴ + 1ไม่สามารถแยกตัวประกอบได้บนQแต่สามารถแยกตัวประกอบได้บนฟิลด์จำกัดใดๆ

• บนส่วนขยายสนามใดๆ ของF ₂ , P = ( x + 1) ⁴ .
• ในฟิลด์จำกัดอื่นๆ อย่างน้อยหนึ่งใน −1, 2 และ −2 จะเป็นกำลังสอง เนื่องจากผลคูณของจำนวนที่ไม่ใช่กำลังสองสองจำนวนจะเป็นกำลังสอง ดังนั้นเราจึงมี

1. ถ้าเช่นนั้น${\displaystyle -1=a^{2},}$${\displaystyle P=(x^{2}+a)(x^{2}-a).}$
2. ถ้าเช่นนั้น${\displaystyle 2=b^{2},}$${\displaystyle P=(x^{2}+bx+1)(x^{2}-bx+1).}$
3. ถ้าเช่นนั้น${\displaystyle -2=c^{2},}$${\displaystyle P=(x^{2}+cx-1)(x^{2}-cx-1).}$

อัลกอริทึมการแยกตัวประกอบพหุนามใช้การดำเนินการพื้นฐานของพหุนาม เช่น การคูณ การหาร ตัวหารร่วมมาก การยกกำลังของพหุนามหนึ่งหารด้วยอีกพหุนามหนึ่ง เป็นต้น^การคูณพหุนามสองตัวที่มีดีกรีไม่เกินnสามารถทำได้ด้วย การดำเนินการ O ( n² )ในFq โดยใช้เลขคณิต _แบบ "คลาสสิก" หรือด้วย การดำเนินการ O ( n log( n ) log(log( n ))) ในFqโดยใช้เลขคณิตแบบ "เร็ว" _การหารแบบยุคลิด (การหารที่มีเศษเหลือ) สามารถทำได้ภายในขอบเขตเวลาเดียวกัน ต้นทุนของการหาตัวหารร่วมมากของพหุนามสองตัวที่มีดีกรีไม่เกินnสามารถคำนวณได้จาก การดำเนินการ O ( n² ⁾ในFq โดยใช้วิธีการแบบคลาสสิก _หรือจาก การดำเนินการ O ( n log² ( n ) ^log (log( n ))) ใน_Fqโดยใช้วิธีการแบบเร็ว สำหรับพหุนามh , gที่มีดีกรีไม่เกินnการยกกำลังh ^q mod gสามารถทำได้ด้วยผลคูณพหุนามO (log( q )) โดยใช้วิธี การยกกำลังโดยการยกกำลังสอง^ซึ่งก็คือ_การ ดำเนินการ O ( n² log( q )) ในFqโดยใช้วิธีการแบบคลาสสิก หรือ การดำเนินการ O ( n log( q )log( n ) log(log( n ))) ในFq _โดยใช้วิธีการที่รวดเร็ว

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

อัลกอริทึมจำนวนมากสำหรับการแยกตัวประกอบพหุนามบนฟิลด์จำกัดนั้นประกอบด้วยสามขั้นตอนดังต่อไปนี้:

1. การแยกตัวประกอบแบบไร้กำลังสอง
2. การแยกตัวประกอบระดับที่แตกต่างกัน
3. การแยกตัวประกอบที่มีดีกรีเท่ากัน

ข้อยกเว้นที่สำคัญคืออัลกอริทึมของ Berlekampซึ่งรวมขั้นตอนที่ 2 และ 3 เข้าด้วยกัน

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

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

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

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

อัลกอริทึม : SFF (การแยกตัวประกอบแบบไร้กำลังสอง) อินพุต : พหุนามเอกลักษณ์fในF q [ x ] โดยที่q = p mเอาต์พุต : การแยกตัวประกอบแบบไร้กำลังสองของf R ← 1 # กำหนดให้wเป็นผลคูณ (โดยไม่รวมความซ้ำซ้อน) ของตัวประกอบทั้งหมดของfที่มี # จำนวนครั้งที่ไม่สามารถหารลงตัวด้วยp c ← gcd ( f , f ′) w ← f / c # ขั้นตอนที่ 1: ระบุตัวประกอบทั้งหมดในw i ← 1 ในขณะที่w ≠ 1 ทำy ← gcd ( w , c ) fac ← w / y R ← R · fac i w ← y ; c ← c / y ; i ← i + 1 สิ้นสุด while # ตอนนี้ cคือผลคูณ (รวมความซ้ำซ้อน) ของตัวประกอบที่เหลือของf ขั้นตอนที่ 2: ระบุปัจจัยที่เหลือทั้งหมดโดยใช้การเรียกซ้ำ # โปรดทราบว่าตัวประกอบเหล่านี้เป็นตัวประกอบของfที่มีความซ้ำซ้อนหารลงตัวด้วยp ถ้าc ≠ 1 แล้วc ← c 1/ p R ← R · SFF ( c ) p end ifเอาต์พุต ( R ) 

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

อนุญาต

${\displaystyle f=x^{11}+2x^{9}+2x^{8}+x^{6}+x^{5}+2x^{3}+2x^{2}+1\in \mathbf {F} _{3}[x],}$

โดยพิจารณาจากองค์ประกอบสามอย่างในขอบเขตของสนาม

อัลกอริทึมจะคำนวณก่อน

${\displaystyle c=\gcd(f,f')=x^{9}+2x^{6}+x^{3}+2.}$

เนื่องจากอนุพันธ์ไม่เป็นศูนย์ เราจึงได้w = f / c = x² + 2และเข้าสู่ลูป while หลังจากวนลูปครั้งแรก เราจะได้y = x + 2, z = x + 1 และ R = x + 1 โดยมีการอัปเดต i = 2, w = x + 2 และ c = x⁸ + x⁷ + x⁶ + x² + x + 1 ^การวนลูปครั้งที่สองให้ค่าy = x + 2 , z = 1 , R = x + 1 ^{โดยมี}การอัป^เดตⁱ = 3 , w = x + 2 และ c = x⁷ + 2x⁶ + x + 2 การวนลูปครั้งที่สามก็ไม่ทำให้Rเปลี่ยนแปลงเช่นกันสำหรับการ^วนลูป^{ครั้ง}ที่สี่ เราจะได้y = 1 , z = x + 2 , R = ( x + 1)( x + 2) ^⁴โดยมีการอัปเดตi = 5 , w = 1และc = x⁶ ⁺ 1เนื่องจากw = 1 เราจึงออกจากลูป while เนื่องจากc ≠ 1จึงต้องเป็นกำลังสามสมบูรณ์ รากที่สามของcซึ่งได้จากการแทนที่^x³ ด้วย x คือ x² + 1 และการเรียกใช้ขั้นตอนการตรวจสอบตัวประกอบที่ไม่มีตัวประกอบกำลังสอง ^ซ้ำๆ จะยืนยันว่ามันเป็นตัวประกอบที่ไม่มีตัวประกอบกำลังสอง ดังนั้น การยกกำลังสามและรวมเข้ากับค่าของRในขณะนั้น จะได้การแยกตัวประกอบที่ไม่มีตัวประกอบกำลังสอง

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

อัลกอริทึมนี้จะแยกพหุนามที่ไม่มีตัวประกอบกำลังสองออกเป็นผลคูณของพหุนามที่มีตัวประกอบที่ไม่สามารถแยกตัวประกอบได้อีกทั้งหมดซึ่งมีดีกรีเดียวกัน ให้f ∈ F _q [ x ]ที่มีดีกรีnเป็นพหุนามที่จะแยกตัวประกอบ

อัลกอริทึมการแยกตัวประกอบดีกรีต่างกัน (DDF) อินพุต : พหุนามเอกลักษณ์ที่ไม่มีตัวประกอบกำลังสอง f ∈ F q [ x ] เอาต์พุต : เซตของคู่ทั้งหมด( g , d )โดยที่ fมีตัวประกอบที่ไม่สามารถแยกตัวประกอบได้ที่มีดีกรีd และ g เป็นผลคูณของตัวประกอบที่ไม่สามารถแยกตัวประกอบได้ทั้งหมดของfที่ มีดีกรีdเริ่มต้นในขณะที่ทำซ้ำถ้าg ≠ 1 แล้ว ; สิ้นสุด ถ้าi  := i + 1;สิ้นสุด ในขณะที่ถ้า แล้ว ; ถ้า แล้วส่งคืน{( f , 1)}มิ ฉะนั้น ส่งคืนSสิ้นสุด${\displaystyle i:=1;\qquad S:=\emptyset ,\qquad f^{*}:=f;}$${\displaystyle \deg f^{*}\geq 2i}$${\displaystyle g=\gcd(f^{*},x^{q^{i}}-x)}$${\displaystyle S:=S\cup \{(g,i)\}}$${\displaystyle f^{*}:=f^{*}/g}$${\displaystyle f^{*}\neq 1}$${\displaystyle S:=S\cup \{(f^{*},\deg f^{*})\}}$${\displaystyle S=\emptyset }$

ความถูกต้องของอัลกอริทึมขึ้นอยู่กับปัจจัยดังต่อไปนี้:

บทตั้ง.สำหรับi ≥ 1 พหุนาม

${\displaystyle x^{q^{i}}-x\in \mathbf {F} _{q}[x]}$

คือผลคูณของพหุนามเอกลักษณ์ที่ไม่สามารถแยกตัวประกอบได้ทั้งหมดในF _q [ x ] ซึ่งมีดีกรีหารiลงตัว

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

${\displaystyle g=\gcd \left(f^{*},x^{q^{i}}-x\right)}$

อาจถูกแทนที่ด้วย

${\displaystyle g=\gcd \left(f^{*},\left(x^{q^{i}}-x\mod f^{*}\right)\right).}$

ดังนั้น เราจึงต้องคำนวณ:

${\displaystyle x^{q^{i}}-x\mod f^{*},}$

มีสองวิธี:

วิธีที่ 1.เริ่มจากค่าของ

${\displaystyle x^{q^{i-1}}\mod f^{*}}$

คำนวณในขั้นตอนก่อนหน้าและคำนวณ กำลังที่ q ของมันโมดูลัส f*ใหม่โดยใช้การยกกำลังด้วยวิธีการยกกำลังสอง ซึ่งจำเป็นต้องใช้

${\displaystyle O\left(\log(q)\deg(f)^{2}\right)}$

การดำเนินการทางคณิตศาสตร์ในFq ในแต่ละขั้น _ตอนและด้วยเหตุนี้

${\displaystyle O\left(\log(q)\deg(f)^{3}\right)}$

การดำเนินการทางคณิตศาสตร์สำหรับอัลกอริทึมทั้งหมด

วิธีที่ 2.โดยใช้ข้อเท็จจริงที่ว่า กำลังที่ qเป็นแผนที่เชิงเส้นบนFqเราสามารถคำนวณเมทริกซ์ของมันได้ _ด้วย

${\displaystyle O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)}$

จากนั้นในแต่ละรอบของการวนซ้ำ ให้คำนวณผลคูณของเมทริกซ์กับเวกเตอร์ (ด้วย การดำเนินการ O (deg( f ) ² )) ซึ่งทำให้เกิดจำนวนการดำเนินการทั้งหมดในF _qซึ่งคือ

${\displaystyle O\left(\deg(f)^{2}(\log(q)+\deg(f))\right).}$

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

ในส่วนนี้ เราจะพิจารณาการแยกตัวประกอบของพหุนามเอกนามเอกลักษณ์f ที่ไม่มีตัวประกอบกำลังสองสมบูรณ์ ซึ่ง มีดีกรีnบนฟิลด์จำกัดF _qซึ่งมี ตัวประกอบที่ไม่สามารถแยกตัวประกอบได้อีก r ≥ 2 ตัวที่แตกต่างกัน เป็น คู่ๆโดยแต่ละตัวมีดีกรีd${\displaystyle f_{1},\ldots ,f_{r}}$

เราจะอธิบายอัลกอริทึมของ Cantor และ Zassenhaus (1981) ก่อน แล้วจึงอธิบายอัลกอริทึมอีกแบบที่มีความซับซ้อนดีกว่าเล็กน้อย ทั้งสองเป็นอัลกอริทึมเชิงความน่าจะเป็นซึ่งเวลาในการทำงานขึ้นอยู่กับการเลือกแบบสุ่ม ( อัลกอริทึมลาสเวกัส ) และมีเวลาในการทำงานเฉลี่ยที่ดี ในส่วนถัดไป เราจะอธิบายอัลกอริทึมของ Shoup (1990) ซึ่งเป็นอัลกอริทึมการแยกตัวประกอบที่มีดีกรีเท่ากันเช่นกัน แต่เป็นแบบกำหนดได้ อัลกอริทึมทั้งหมดเหล่านี้ต้องการลำดับคี่qสำหรับฟิลด์ของสัมประสิทธิ์ สำหรับอัลกอริทึมการแยกตัวประกอบเพิ่มเติม โปรดดูหนังสือของ Knuth เช่นThe Art of Computer Programmingเล่ม 2

อัลกอริทึม Cantor –Zassenhaus อินพุต:ฟิลด์จำกัดF qที่มีอันดับคี่q พหุนามเอกลักษณ์ที่ไม่ขึ้นกับกำลังสองfในF q [ x ] ที่มีดีกรีn = rd , ซึ่งมี ตัวประกอบที่ไม่สามารถแยกย่อยได้อีก r ≥ 2 ตัว โดยแต่ละตัวมีดีกรีd ผลลัพธ์:เซตของตัวประกอบที่ไม่สามารถแยกย่อยได้อีกแบบเอกนามของf Factors := { f }; while Size(Factors) < r do , เลือกhในF q [ x ] แบบสุ่ม โดยที่ deg( h ) < n ; สำหรับแต่ละu ใน Factors ที่มี deg( u ) > d ให้ทำถ้า gcd( g , u ) ≠ 1 และ gcd( g , u ) ≠ uแล้ว Factors := Factors ; endif endwhile${\displaystyle g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}}$${\displaystyle \,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}}$ปัจจัย การคืนสินค้า

ความถูกต้องของอัลกอริทึมนี้ขึ้นอยู่กับข้อเท็จจริงที่ว่าวงแหวนF _q [ x ]/ fเป็นผลคูณโดยตรงของฟิลด์F _q [ x ]/ f _iโดยที่f _iทำงานบนตัวประกอบที่ไม่สามารถแยกย่อยได้ของfเนื่องจากฟิลด์เหล่านี้ทั้งหมดมี องค์ประกอบ q ^dดังนั้นส่วนประกอบของgในฟิลด์ใดๆ เหล่านี้จึงเป็นศูนย์ด้วยความน่าจะเป็น

${\displaystyle {\frac {q^{d}-1}{2q^{d}}}\sim {\tfrac {1}{2}}.}$

นี่หมายความว่าพหุนาม gcd( g , u ) คือผลคูณของตัวประกอบของgซึ่งส่วนประกอบของgเป็นศูนย์

ได้มีการแสดงให้เห็นแล้วว่าจำนวนรอบเฉลี่ยของลูป while ของอัลกอริทึมนั้นน้อยกว่า ซึ่ง_{ทำให้}^{จำนวน}การดำเนินการทางคณิตศาสตร์เฉลี่ยในFqเท่ากับ[ ^{3 ]}${\displaystyle 2.5\log _{2}r}$${\displaystyle O(dn^{2}\log(r)\log(q))}$

ในกรณีทั่วไปที่d log( q ) > nความซับซ้อนนี้อาจลดลงเหลือ

${\displaystyle O(n^{2}(\log(r)\log(q)+n))}$

โดยการเลือกhในเคอร์เนลของแผนที่เชิงเส้น

${\displaystyle v\to v^{q}-v{\pmod {f}}}$

และแทนที่คำสั่ง

${\displaystyle g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}}$

โดย

${\displaystyle g:=h^{\frac {q-1}{2}}-1{\pmod {f}}.}$

การพิสูจน์ความถูกต้องนั้นเหมือนกับข้างต้น โดยแทนที่ผลคูณโดยตรงของฟิลด์F _q [ x ]/ f _iด้วยผลคูณโดยตรงของฟิลด์ย่อยที่มีqองค์ประกอบ ความซับซ้อนถูกแยกออกเป็นสำหรับตัวอัลกอริทึมเองสำหรับการคำนวณเมทริกซ์ของแผนที่เชิงเส้น (ซึ่งอาจคำนวณไว้แล้วในการแยกตัวประกอบแบบไม่มีกำลังสอง) และO ( n ³ ) สำหรับการคำนวณเคอร์เนล อาจสังเกตได้ว่าอัลกอริทึมนี้ใช้งานได้แม้ว่าตัวประกอบจะมีดีกรีไม่เท่ากัน (ในกรณีนี้ จำนวนrของตัวประกอบที่จำเป็นสำหรับการหยุดลูป while จะถูกพบว่าเป็นมิติของเคอร์เนล) อย่างไรก็ตาม ความซับซ้อนจะดีขึ้นเล็กน้อยหากทำการแยกตัวประกอบแบบไม่มีกำลังสองก่อนใช้อัลกอริทึมนี้ (เนื่องจากnอาจลดลงด้วยการแยกตัวประกอบแบบไม่มีกำลังสอง ซึ่งจะช่วยลดความซับซ้อนของขั้นตอนที่สำคัญ) ${\displaystyle O(n^{2}\log(r)\log(q))}$${\displaystyle O(n^{2}(\log(q)+n))}$

เช่นเดียวกับอัลกอริทึมในส่วนก่อนหน้า อัลก อริทึมของVictor Shoup เป็นอัลกอริทึมการแยกตัวประกอบที่มีดีกรีเท่ากัน ^{[ 4 ]}ซึ่งแตกต่างจากอัลกอริทึมเหล่านั้นตรงที่เป็นอัลกอริทึมเชิงกำหนดอย่างไรก็ตาม ในทางปฏิบัติแล้ว อัลกอริทึมของ Shoup มีประสิทธิภาพน้อยกว่าอัลกอริทึมในส่วนก่อนหน้า สำหรับอัลกอริทึมของ Shoup อินพุตจะถูกจำกัดไว้ที่พหุนามเหนือฟิลด์เฉพาะ F _p

ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดของอัลกอริทึมของ Shoup มีตัวประกอบ เป็น p แม้จะเป็นแบบเลขชี้กำลัง แต่ความซับซ้อนนี้ดีกว่าอัลกอริทึมเชิงกำหนดก่อนหน้านี้ (อัลกอริทึมของ Berlekamp) ซึ่งมีpเป็นตัวประกอบ อย่างไรก็ตาม มีพหุนามเพียงไม่กี่ตัวเท่านั้นที่เวลาในการคำนวณเป็นแบบเลขชี้กำลัง และความซับซ้อนของเวลาเฉลี่ยของอัลกอริทึมเป็นแบบพหุนามในโดยที่dคือดีกรีของพหุนาม และpคือจำนวนองค์ประกอบของสนามพื้นฐาน ${\displaystyle {\sqrt {p}}.}$${\displaystyle d\log(p),}$

ให้g = g ₁ ... g _kเป็นการแยกตัวประกอบที่ต้องการ โดยที่g _iเป็นพหุนามเอกลักษณ์ที่ไม่สามารถแยกตัวประกอบได้ที่แตกต่างกันและมีดีกรีdให้n = deg( g ) = kdเราพิจารณาวงแหวนR = F _q [ x ]/ g และใช้ xแทนภาพของxในRวงแหวนRเป็นผลคูณโดยตรงของฟิลด์R _i = F _q [ x ]/ g _iและเราใช้p _i แทน โฮโมมอร์ฟิซึมธรรมชาติจากRไป ยัง R _iกลุ่มกาโลอิสของR _iเหนือF _qเป็นกลุ่มวัฏจักรที่มีอันดับdสร้างขึ้นโดย ออโตมอร์ฟิซึมของฟิลด์u → u ^pดังนั้น รากของg _iในR _iคือ

${\displaystyle p_{i}(x),p_{i}(x^{q}),p_{i}\left(x^{q^{2}}\right),\ldots ,p_{i}\left(x^{q^{d-1}}\right).}$

เช่นเดียวกับในอัลกอริธึมก่อนหน้านี้ อัลกอริธึมนี้ใช้ ซับอัลเจบราBของRเดียวกันกับอัลกอริธึมของเบอร์เลแคมป์ซึ่งบางครั้งเรียกว่า "ซับอัลเจบราของเบอร์เลแคมป์" และกำหนดไว้ดังนี้

${\displaystyle {\begin{aligned}B&=\left\{\alpha \in R\ :\ p_{1}(\alpha ),\cdots ,p_{k}(\alpha )\in \mathbf {F} _{q}\right\}\\&=\{u\in R\ :\ u^{q}=u\}\end{aligned}}}$

เซตย่อยSของBเรียกว่าเซตแยกถ้าสำหรับทุก 1 ≤  i  <  j  ≤  kจะมีs  ∈  S อยู่ เช่นนั้นในอัลกอริทึมก่อนหน้านี้ เซตแยกถูกสร้างขึ้นโดยการสุ่มเลือกสมาชิกของSในอัลกอริทึมของ Shoup เซตแยกถูกสร้างขึ้นในลักษณะต่อไปนี้ ให้sในR [ Y ] เป็นเช่นนั้น ${\displaystyle p_{i}(s)\neq p_{j}(s)}$

${\displaystyle {\begin{aligned}s&=(Y-x)\left(Y-x^{q}\right)\cdots \left(Y-x^{q^{d-1}}\right)\\&=s_{0}+\cdots +s_{d-1}Y^{d-1}+Y^{d}\end{aligned}}}$

ดังนั้นจึงเป็นเซตแยก เพราะสำหรับi = 1, ..., k (พหุนามเอกลักษณ์สองตัวมีรากเดียวกัน) เนื่องจากg _iแตกต่างกันเป็นคู่ๆ ดังนั้นสำหรับทุกคู่ของดัชนีที่แตกต่างกัน ( i , j ) อย่างน้อยหนึ่งสัมประสิทธิ์s _hจะเป็นไปตามเงื่อนไข${\displaystyle \{s_{0},\dots ,s_{d-1}\}}$${\displaystyle p_{i}(s)=g_{i}}$${\displaystyle p_{i}(s_{h})\neq p_{j}(s_{h}).}$

เมื่อมีเซตแยกแล้ว อัลกอริทึมของ Shoup จะดำเนินการเช่นเดียวกับอัลกอริทึมสุดท้ายของส่วนก่อนหน้า โดยแทนที่คำสั่ง "เลือกh แบบสุ่ม ในเคอร์เนลของแผนที่เชิงเส้น" ด้วย "เลือกh + iโดยที่hอยู่ในSและiอยู่ใน {1, ..., k −1}" ${\displaystyle v\to v^{q}-v{\pmod {f}}}$

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

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

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

ให้p ₁ , ..., p _kเป็นตัวหารเฉพาะทั้งหมดของnและให้สำหรับ 1 ≤ i ≤ kพหุนามfในF _q [ x ] ที่มีดีกรีnไม่สามารถแยกตัวประกอบได้ในF _q [ x ] ก็ต่อเมื่อสำหรับ 1 ≤  i  ≤  kและfหารในความเป็นจริง ถ้าfมีตัวประกอบที่มีดีกรีไม่หารn ลงตัว แสดงว่าfไม่หาร; ถ้าfมีตัวประกอบที่มีดีกรีหารn ลงตัว แสดงว่าตัวประกอบนั้นหารอย่างน้อยหนึ่งตัวของ${\displaystyle n/p_{i}=n_{i}}$${\displaystyle \gcd \left(f,x^{q^{n_{i}}}-x\right)=1}$${\displaystyle x^{q^{n}}-x}$${\displaystyle x^{q^{n}}-x}$${\displaystyle x^{q^{n_{i}}}-x.}$

อัลกอริ ทึม การทดสอบความไม่สามารถแยกตัวประกอบของ Rabin อินพุต : พหุนามเอกลักษณ์fในF q [ x ] ที่มีดีกรีn โดยที่ p 1 , ..., p k เป็นตัวหารเฉพาะที่แตกต่างกันทั้งหมดของ n เอาต์พุต: " f ไม่สามารถแยกตัวประกอบได้"หรือ " fสามารถแยกตัวประกอบได้"สำหรับj = 1 ถึงk ทำซ้ำ ; สำหรับi = 1 ถึงk ทำซ้ำ ; g  := gcd( f , h ); ถ้าg ≠ 1 ให้คืนค่า " fสามารถลดรูปได้" และหยุด ; สิ้นสุดลูป ; ถ้าg = 0 ให้คืนค่า " fไม่สามารถลดรูปได้" มิฉะนั้นให้คืนค่า " f สามารถลดรูป ได้ " ${\displaystyle n_{j}=n/p_{j}}$${\displaystyle h:=x^{q^{n_{i}}}-x{\bmod {f}}}$${\displaystyle g:=x^{q^{n}}-x{\bmod {f}}}$

แนวคิดพื้นฐานของอัลกอริธึมนี้คือการคำนวณโดยเริ่มจากค่าที่เล็กที่สุดโดยการยกกำลังสองซ้ำๆ หรือใช้การแปลงแบบ Frobenius และจาก _นั้นจึงหาค่า gcd ที่สอดคล้องกัน การใช้เลขคณิตพหุนามพื้นฐาน การคำนวณเมทริกซ์ของการแปลงแบบ Frobenius ต้องใช้การดำเนินการในFqการคำนวณของ ${\displaystyle x^{q^{n_{i}}}{\bmod {f}}}$${\displaystyle n_{1},\ldots ,n_{k}}$${\displaystyle O(n^{2}(n+\log q))}$

${\displaystyle x^{q^{n_{i}}}-x{\pmod {f}}}$

จำเป็นต้องมีการดำเนินการเพิ่มเติม และตัวอัลกอริทึมเองก็ต้องการ การดำเนินการเช่น _กัน ทำให้มี การดำเนินการทั้งหมดใน Fqโดยใช้การคำนวณเลขคณิตเร็ว (ความซับซ้อนสำหรับการคูณและการหาร และสำหรับการคำนวณ GCD) การคำนวณโดยการยกกำลังสองซ้ำๆ คือและตัวอัลกอริทึมเองคือ_{ทำให้} มีการดำเนินการ ทั้งหมดในFq${\displaystyle O(n^{3})}$${\displaystyle O(kn^{2})}$${\displaystyle O(n^{2}(n+\log q))}$${\displaystyle O(n\log n)}$${\displaystyle O(n(\log n)^{2})}$${\displaystyle x^{q^{n_{i}}}-x{\bmod {f}}}$${\displaystyle O(n^{2}\log n\log q)}$${\displaystyle O(kn(\log n)^{2})}$${\displaystyle O(n^{2}\log n\log q)}$

• อัลกอริทึมของเบอร์เลแคมป์
• อัลกอริทึมแคนเตอร์-ซาสเซนเฮาส์
• การแยกตัวประกอบพหุนาม