2
$\begingroup$

Say one only seeks to identify whether a given polynomial over $\mathbb{Z}[x]$ is reducible, then what are the best ways known to solve this?

$(1)$ If the polynomial is reducible, the algorithm should correctly say yes.

$(2)$ If the polynomial is not reducible, the algorithm should correctly say no.

I want to avoid LLL.

The absolute value of the degree $i$th coefficient of the polynomial is at most some fixed $B_i>0$ where $d$ is the degree. I would like to certify whether the polynomial is reducible or not with two sided error $\epsilon$ in running time $$O(\big[d\log_2\big(\prod_{i=0}^dB_i\big)^{\frac{1}{d}}\big]^{c+\frac{1}{\epsilon}})=O(\big[\log_2\big(\prod_{i=0}^dB_i\big)^{}\big]^{c+\frac{1}{\epsilon}})$$ for some fixed $c>0$.

Improve this question
$\endgroup$
3
  • $\begingroup$ I think you should clarify the question. Miller-Rabin outputs "composite" or "probable prime", composite is certain, probable prime is not. The actual probability depends on how you perform the test. The stupid algorithm I suggested in a comment to Igor's answer also returns "composite" (rarely) or "probable prime" often but this time with good probability given that most polynomials with integer coeffs are irreducible. If you want a better answer, you need to be more specific. How is the input given? What running time do you want? and so on. $\endgroup$
    – Felipe Voloch
    Commented Nov 17, 2014 at 1:08
  • $\begingroup$ I will update to clarify. $\endgroup$
    – Turbo
    Commented Nov 17, 2014 at 1:50
  • $\begingroup$ What do you mean by "with two-sided error $\epsilon$"? I first assumed it was a probability of error, but you specify that you want a deterministic yes/no result in the description. $\endgroup$
    – Federico Poloni
    Commented Nov 23, 2015 at 8:31

1 Answer 1

Reset to default
3
$\begingroup$

It seems that there is no better way to check irreducibility than factoring, and the best way to do that is Mark van Hoeij's algorithm, which combines modular techniques with LLL, and is extremely efficient in practice. This is implemented in every CAS other than Mathematica, as far as I know.

@article {MR2891235,
    AUTHOR = {van Hoeij, Mark and Novocin, Andrew},
    TITLE = {Gradual sub-lattice reduction and a new complexity for
              factoring polynomials},
   JOURNAL = {Algorithmica},
   FJOURNAL = {Algorithmica. An International Journal in Computer Science},
   VOLUME = {63},
   YEAR = {2012},
   NUMBER = {3},
   PAGES = {616--633},
   ISSN = {0178-4617},
   CODEN = {ALGOEJ},
   MRCLASS = {68Q25 (11H06 94A60)},
  MRNUMBER = {2891235},
MRREVIEWER = {Vadlamudi China Venkaiah},
   DOI = {10.1007/s00453-011-9500-y},
   URL = {http://dx.doi.org/10.1007/s00453-011-9500-y},

}

Improve this answer
$\endgroup$
7
  • $\begingroup$ It seems that Compositeness over integers has a Miller-Rabin test though? Shouldn't we have one for every $\Bbb Z[x]$ as well? Where does it say there is no better way? Is it in the paper? $\endgroup$
    – Turbo
    Commented Nov 17, 2014 at 0:15
  • 1
    $\begingroup$ It does not say anywhere that there is no better way (there might, in fact, be), but no one I have ever talked to knows of one (including van Hoeij, who is THE expert). You are welcome to try to come up with one :) $\endgroup$
    – Igor Rivin
    Commented Nov 17, 2014 at 0:17
  • $\begingroup$ @Turbo If you want a probabilistic test, just compute the gcd of the coefficients and output "irreducible" if the result is 1. It works with probability 1. $\endgroup$
    – Felipe Voloch
    Commented Nov 17, 2014 at 0:18
  • $\begingroup$ @FelipeVoloch I am looking for a certificate for "reducible". $\endgroup$
    – Turbo
    Commented Nov 17, 2014 at 0:22
  • $\begingroup$ @FelipeVoloch It works with probability 1 asymptotically in height and degree, but I assume the OP is actually interested in actual polynomials, and has some bounds on height and degree in mind (and the convergence to 1 is not that fast in either metric). $\endgroup$
    – Igor Rivin
    Commented Nov 17, 2014 at 0:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .