Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the algorithm to find the roots of a polynomial over integer? I observe that one can find the roots within few seconds in Sage even when all coefficients of are very large. I have asked in http://cstheory.stackexchange.com/questions/18406/roots-of-a-polynomial but still do not get answer.

share|improve this question
1  
Hint: Rational Roots Theorem. Note that this only directly applies to polynomials with rational coefficients. It can be extended rather to polynomials with rational coefficients easily. –  Gamma Function Jul 18 '13 at 17:25
    
@JacobMayle:‌ The rational root theorem is one trick that helps bound the search space, but is it the only thing?‌ Is that as far as efficiency goes? –  ShreevatsaR Jul 18 '13 at 17:26

1 Answer 1

up vote 4 down vote accepted

Use the rational root test: if you have a polynomial $$a_0 + a_1x + \ldots + a_nx^n$$ with integer coefficients, all integer roots are of the form $\pm c$, where $c\vert a_0$.

Finding all roots therefore just amounts to factoring $a_0$ and some (very cheap) polynomial evaluations.

There are several techniques for proving a polynomial is irreducible over $\mathbb{Z}$ (Eisenstein's criteria, Perron's criteria) and these can rule out integer roots in special cases. But unless I were looking at polynomials with truly huge coefficients, the general algorithm I would implement would simply try all of the plausible roots.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.