The title and the article are severely misleading. One can easily try the method described in the article and find that empirically, it doesn't work for large n

The title and the article are severely misleading. One can easily try the method described in the article and find that empirically, it doesn't work for large numbers. That implies that no one is seriously taking such a naive approach. You don't need a mathematical proof either way to know this. But even so, the paper doesn't show that all polynomials are irreducible. It doesn't even show most are, just ones of a very special form (with 0 and 1 coefficients, randomly chosen in a certain way). Therefore, the paper doesn't rule out other kinds of polynomials, even if this were a serious approach. Furthermore, even if the paper showed that all kinds of polynomials were almost always irreducible, that wouldn't rule out the existence of a very clever algorithm for writing the integers as values of polynomials that aren't irreducible. Consider the following analogy: there are exceedingly many possible prime factors of 6000 digit numbers; far too many to practically test them all one after the other. I can produce a mathematical proof that shows that I'll never test primality of a 6000 digit number by trying all possible prime factors in order. But that doesn't prevent the existence of algorithms that can quite quickly tell you whether the number is prime or composite (such algorithms actually exist). Just because something looks hard or it can be proven that some naive approach is computationally infeasible, doesn't mean there isn't a very clever algorithm that makes it easy. The authors of the actual math paper really asked for any unwanted attention they get from this news article, though. They actually give the integer factorisation problem as a motivation in their paper!