Berlekamp–Rabin algorithm: Difference between revisions

Revision as of 15:57, 19 December 2023

Revision as of 15:58, 19 December 2023

Line 6:

== Statement of problem==

Let <math>p</math> be an odd prime number. Consider the polynomial <math display="inline">f(x) = a_0 + a_1 x + \cdots + a_n x^n</math> over the field <math>\mathbb F_p\simeq \mathbb Z/p\mathbb Z</math> of remainders modulo <math>p</math>. The algorithm should find all <math>\lambda</math> in <math>\mathbb F_p</math> such that <math display="inline">f(\lambda)= 0</math> in <math>\mathbb F_p</math>.<ref name=":1" /><ref name=":2">{{cite book| author = Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone | url = https://www.springer.com/gp/book/9780792392828 | title = Applications of Finite Fields |date = 1993 |publisher= Springer US | series = The Springer International Series in Engineering and Computer Science | isbn = 9780792392828}}</ref>

== Algorithm ==