AlgorithmThe algorithm finds factorization of <math>f_z(x)</math> in all cases except for ones when all numbers <math>z+\lambda_1, z+\lambda_2, \ldots, z+\lambda_n</math> are quadratic residues or non-residues simultaneously. According to [[theory of cyclotomy]],<ref>{{cite book| author = Marshall Hall | chapter = | chapter-url = | format = | url = https://books.google.com/books?hl=en&lr=&id=__JCiiCfu2EC&oi=fnd&pg=PA1&dq=Combinatorial+Theory+hall&ots=WeNDZ7uCSM&sig=a6JwSPPen2C2EysEnkSTXpUNaxM&redir_esc=y#v=onepage&q=Combinatorial%20Theory%20hall&f=false | title = Combinatorial Theory | orig-year = | agency = | edition = |___location= |date = 1998 |publisher= John Wiley & Sons |at= |volume= |issue = | pages = | page = | series = | isbn = 9780471315186| ref = }}</ref> the probability of such an event for the case when <math>\lambda_1, \ldots, \lambda_n</math> are all residues or non-residues simultaneously (that is, when <math>z=0</math> would fail) may be estimated as <math>2^{-k}</math> where <math>k</math> is the number of dinstinct values in <math>\lambda_1, \ldots, \lambda_n</math>.<ref name=":0" /> In this way even for the worst case of <math>k=1</math> and <math>f(x)=(x-\lambda)^n</math>, the probability of error may be estimated as <math>1/2</math> and for modular square root case error probability is at most <math>1/4</math>.
