ในทฤษฎีจำนวนอัลกอริทึมการหาค่ารากของ Berlekampหรือที่เรียกว่าอัลกอริทึม Berlekamp–Rabinเป็น วิธี การเชิงความน่าจะเป็นในการหาค่ารากของพหุนามเหนือฟิลด์ ที่มีสมาชิก วิธีนี้ถูกค้นพบโดยElwyn Berlekampในปี 1970 ^{[ 1 ]}ในฐานะตัวช่วยสำหรับอัลกอริทึมการแยกตัวประกอบพหุนามเหนือฟิลด์จำกัด ต่อมาอัลกอริทึมนี้ได้รับการปรับปรุงโดยRabinสำหรับฟิลด์จำกัดใดๆ ในปี 1979 ^{[ 2 ]}วิธีนี้ได้รับการค้นพบโดยอิสระก่อน Berlekamp โดยนักวิจัยคนอื่นๆ อีกด้วย^{[ 3 ]}${\displaystyle \mathbb {F} _{p}}$${\displaystyle p}$

วิธีการนี้ได้รับการเสนอโดยElwyn Berlekampในงานของเขาในปี 1970 ^{[ 1 ]}เกี่ยวกับการแยกตัวประกอบพหุนามเหนือฟิลด์จำกัด งานดั้งเดิมของเขาขาดการพิสูจน์ความถูกต้องอย่างเป็นทางการ[ 2 ] และต่อมาได้รับการปรับปรุงและแก้ไขสำหรับฟิลด์จำกัดใดๆ โดย Michael Rabin [ 2 ^{]ในปี} 1986 René ^{Peraltaได้เสนอ}อัลกอริทึมที่คล้ายกัน^{[ 4 ]}สำหรับการค้นหารากที่สองใน[ ^{5 ] ใน}ปี 2000 วิธีการของ Peralta ได้รับการขยายความสำหรับสมการกำลังสาม^{[ 6 ]}${\displaystyle \mathbb {F} _{p}}$

ให้เป็นจำนวนเฉพาะคี่ พิจารณาพหุนาม^{เหนือ}ฟิลด์ของเศษเหลือมอดูล อัลกอริทึมควรค้นหาทั้งหมดในที่ใน[ ^{2 ] [ 7 ]}${\displaystyle p}$${\textstyle f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}}$${\displaystyle \mathbb {F} _{p}\simeq \mathbb {Z} /p\mathbb {Z} }$${\displaystyle p}$${\displaystyle \lambda }$${\displaystyle \mathbb {F} _{p}}$${\textstyle f(\lambda )=0}$${\displaystyle \mathbb {F} _{p}}$

ให้การหารากทั้งหมดของพหุนามนี้เทียบเท่ากับการหาการแยกตัวประกอบของพหุนามนี้ออกเป็นตัวประกอบเชิงเส้น ในการหาการแยกตัวประกอบดังกล่าว เพียงพอที่จะแบ่งพหุนามออกเป็นตัวหารที่ไม่ใช่ตัวหารศูนย์สองตัวใดๆ และแยกตัวประกอบแบบเวียนซ้ำ ในการทำเช่นนี้ ให้พิจารณาพหุนามโดยที่ เป็นสมาชิกบางตัวของถ้าเราสามารถแทนพหุนามนี้เป็นผลคูณได้ในแง่ของพหุนามเริ่มต้น หมายความว่าซึ่งให้การแยกตัวประกอบที่จำเป็นของ^{[ 1 ] [ 7 ]}${\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\cdots (x-\lambda _{n})}$${\textstyle f_{z}(x)=f(x-z)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\cdots (x-\lambda _{n}-z)}$${\displaystyle z}$${\displaystyle \mathbb {F} _{p}}$${\displaystyle f_{z}(x)=p_{0}(x)p_{1}(x)}$${\displaystyle f(x)=p_{0}(x+z)p_{1}(x+z)}$${\displaystyle f(x)}$

เนื่องจากเกณฑ์ของออยเลอร์สำหรับเอกนาม ทุกตัว จะต้องมีคุณสมบัติต่อไปนี้เพียงข้อเดียวเท่านั้น: ^{[ 1 ]}${\displaystyle (x-\lambda )}$

1. เอกนามจะมี ค่าเท่ากับถ้า${\displaystyle x}$${\displaystyle \lambda =0}$
2. เอกนามหารลงตัวถ้า เป็นเศษเหลือกำลังสองมอดูล${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$${\displaystyle \lambda }$${\displaystyle p}$
3. เอกนามหารลงตัวก็ต่อเมื่อ เป็นพหุนามกำลังสองที่ไม่เหลือเศษมอดูล${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$${\displaystyle \lambda }$${\displaystyle p}$

ดังนั้น หากไม่สามารถหารลงตัวด้วยซึ่งสามารถตรวจสอบแยกต่างหากได้ ก็^จะเท่ากับผลคูณของตัวหารร่วมมากที่สุดกับ^{[ 7} ]${\displaystyle f_{z}(x)}$${\displaystyle x}$${\displaystyle f_{z}(x)}$${\displaystyle \gcd(f_{z}(x);g_{0}(x))}$${\displaystyle \gcd(f_{z}(x);g_{1}(x))}$

คุณสมบัติข้างต้นนำไปสู่อัลกอริทึมต่อไปนี้: ^{[ 1 ]}

1. คำนวณค่าสัมประสิทธิ์ของ อย่างชัดเจน${\displaystyle f_{z}(x)=f(x-z)}$
2. คำนวณเศษเหลือจากการหารเอาเศษด้วยกำลังสองของพหุนามปัจจุบัน แล้วนำเศษเหลือนั้นมาหารด้วยเศษเหลือ${\textstyle x,x^{2},x^{2^{2}},x^{2^{3}},x^{2^{4}},\ldots ,x^{2^{\lfloor \log _{2}p\rfloor }}}$${\displaystyle f_{z}(x)}$${\displaystyle f_{z}(x)}$
3. โดยใช้การยกกำลังโดยการยกกำลังสองและพหุนามที่คำนวณได้ในขั้นตอนก่อนหน้า ให้คำนวณเศษเหลือของการหารเอาเศษ${\textstyle x^{(p-1)/2}}$${\textstyle f_{z}(x)}$
4. ถ้าหากมีการระบุการแยกตัวประกอบที่ไม่ธรรมดาของ ไว้ด้านล่างแล้ว${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)}}}$${\displaystyle \gcd }$${\displaystyle f_{z}(x)}$
5. มิฉะนั้น รากทั้งหมดของจะเป็นได้ทั้งเศษเหลือหรือไม่ใช่เศษเหลือพร้อมกัน และจะต้องเลือกอย่างอื่น${\displaystyle f_{z}(x)}$${\displaystyle z}$

ถ้าหารลงตัวด้วยพหุนามดั้งเดิมที่ ไม่เป็นเชิงเส้นบางตัว เหนือแล้วเมื่อคำนวณด้วยและจะได้การแยกตัวประกอบที่ไม่ธรรมดาของดังนั้นอัลกอริทึมนี้จึงช่วยให้สามารถหารากทั้งหมดของพหุนามใดๆ เหนือได้ ${\displaystyle f(x)}$${\displaystyle g(x)}$${\displaystyle \mathbb {F} _{p}}$${\displaystyle \gcd }$${\displaystyle g_{0}(x)}$${\displaystyle g_{1}(x)}$${\displaystyle f_{z}(x)/g_{z}(x)}$${\displaystyle \mathbb {F} _{p}}$

พิจารณาสมการที่มีองค์ประกอบและเป็นรากของสมการ การแก้สมการนี้เทียบเท่ากับการแยกตัวประกอบของพหุนามเหนือในกรณีเฉพาะนี้ การคำนวณเพียง ก็เพียงพอแล้วสำหรับพหุนามนี้ คุณสมบัติใดคุณสมบัติหนึ่งต่อไปนี้จะเป็นจริง: ${\textstyle x^{2}\equiv a{\pmod {p}}}$${\displaystyle \beta }$${\displaystyle -\beta }$${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$${\displaystyle \mathbb {F} _{p}}$${\displaystyle \gcd(f_{z}(x);g_{0}(x))}$

1. GCD เท่ากับซึ่งหมายความว่าและต่างก็เป็นค่าที่ไม่ใช่เศษเหลือแบบกำลังสอง${\displaystyle 1}$${\displaystyle z+\beta }$${\displaystyle z-\beta }$
2. GCD เท่ากับซึ่งหมายความว่าทั้งสองจำนวนเป็นเศษเหลือกำลังสอง${\displaystyle f_{z}(x)}$
3. GCD เท่ากับซึ่งหมายความว่ามีเพียงหนึ่งในจำนวนเหล่านี้เท่านั้นที่เป็นเศษเหลือกำลังสอง${\displaystyle (x-t)}$

ในกรณีที่สาม GCD จะเท่ากับ หรือซึ่งทำให้สามารถเขียนคำตอบได้เป็น^{[ 1 ]}${\displaystyle (x-z-\beta )}$${\displaystyle (x-z+\beta )}$${\textstyle \beta =(t-z){\pmod {p}}}$

สมมติว่าเราต้องการแก้สมการเพื่อการนี้เราต้องแยกตัวประกอบพิจารณาค่าที่เป็นไปได้บางค่าของ: ${\textstyle x^{2}\equiv 5{\pmod {11}}}$${\displaystyle f(x)=x^{2}-5=(x-\beta )(x+\beta )}$${\displaystyle z}$

1. ให้. จากนั้นดังนั้น. ทั้งสองจำนวนเป็นจำนวนที่ไม่ใช่เศษกำลังสอง ดังนั้นเราจึงต้องเลือกจำนวนอื่น${\displaystyle z=3}$${\displaystyle f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4}$${\displaystyle \gcd(x^{2}-6x+4;x^{5}-1)=1}$${\displaystyle 3\pm \beta }$${\displaystyle z}$

1. ให้. จากนั้นดังนั้น. จากนี้จึงสรุปได้ว่า ดังนั้นและ.${\displaystyle z=2}$${\displaystyle f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1}$${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}}$${\textstyle x-9=x-2-\beta }$${\displaystyle \beta \equiv 7{\pmod {11}}}$${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$

จากการ ตรวจ สอบด้วยตนเองพบว่า เป็นเช่นนั้นจริง ๆและ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11}}}$${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11}}}$

อัลกอริทึมจะค้นหาการแยกตัวประกอบของในทุกกรณี ยกเว้นกรณีที่ตัวเลขทั้งหมดเป็นเศษกำลังสองหรือไม่ใช่เศษกำลังสองพร้อมกัน ตามทฤษฎีไซโคลโทมี [ ^{8 ] ความ}น่าจะเป็นของเหตุการณ์ดังกล่าวสำหรับกรณีที่เป็นเศษกำลังสองหรือไม่ใช่เศษกำลังสองพร้อมกัน (นั่นคือ เมื่อจะล้มเหลว) อาจประมาณได้เป็น โดยที่ คือจำนวนค่าที่แตกต่างกันใน[ ^{1 ] ด้วย}วิธีนี้ แม้แต่กรณีที่เลวร้ายที่สุดของและความน่าจะเป็นของข้อผิดพลาดอาจประมาณได้เป็นและสำหรับกรณีรากที่สองแบบโมดูลาร์ ความน่าจะเป็นของข้อผิดพลาดจะมีค่าสูงสุดเพียง ${\displaystyle f_{z}(x)}$${\displaystyle z+\lambda _{1},z+\lambda _{2},\ldots ,z+\lambda _{n}}$${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$${\displaystyle z=0}$${\displaystyle 2^{-k}}$${\displaystyle k}$${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$${\displaystyle k=1}$${\displaystyle f(x)=(x-\lambda )^{n}}$${\displaystyle 1/2}$${\displaystyle 1/4}$

ให้พหุนามมีดีกรีn เราจะหาความซับซ้อนของอัลกอริทึมได้ดังนี้: ${\displaystyle n}$

1. เนื่องจากทฤษฎีบททวินาม เราจึงสามารถเปลี่ยนจากไปเป็น ได้ เมื่อเวลาผ่านไป${\textstyle (x-z)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{k-i}x^{i}}$${\displaystyle f(x)}$${\displaystyle f(x-z)}$${\displaystyle O(n^{2})}$
2. การคูณพหุนามและการหาเศษเหลือจากการหารพหุนามหนึ่งด้วยพหุนามอีกพหุนามหนึ่ง สามารถทำได้ในเวลาดังนั้นการคำนวณจึงทำได้ในเวลา${\textstyle O(n^{2})}$${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$${\textstyle O(n^{2}\log p)}$
3. การยกกำลังเลขฐานสองใช้งานได้ใน.${\displaystyle O(n^{2}\log p)}$
4. การหาผลคูณของพหุนามสองตัวโดยใช้อัลกอริทึมยุคลิดนั้นใช้ได้ผลใน.${\displaystyle \gcd }$${\displaystyle O(n^{2})}$

ดังนั้นขั้นตอนทั้งหมดจึงสามารถทำได้ใน. โดยใช้การแปลงฟูริเยร์แบบเร็วและอัลกอริทึม Half-GCD ^{[ 9 ]}ความซับซ้อนของอัลกอริทึมอาจได้รับการปรับปรุงเป็น. สำหรับกรณีรากที่สองแบบโมดูลาร์ ระดับคือดังนั้นความซับซ้อนทั้งหมดของอัลกอริทึมในกรณีดังกล่าวจึงถูกจำกัดโดยต่อการวนซ้ำ^{[ 7 ]}${\displaystyle O(n^{2}\log p)}$${\displaystyle O(n\log n\log pn)}$${\displaystyle n=2}$${\displaystyle O(\log p)}$