Is factoring polynomials as hard as factoring integers? There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard?
One thing I originally thought was that if we could factor polynomials easily, then we could factor $n$ by finding a polynomial $p(x)$ with $p(m)=n$ for some $m$, then "easily factorizing" $p$ to get $p(x)=q(x)\cdot r(x)$. Then $q(m)\cdot r(m)$ would be a factorization of $n$. But we wouldn't get any information if one of these happened to be 1.
Does anyone have a solution or a reference for this problem? (I searched online, but all I could find was how to do factorization like in high school problems.)

The problem is multifold:


*

*irreducibility, as the other answers showed, is a stumbling block at the best of times.

*Polynomial factoring (by faster methods), isn't the only way we could factor an integer, but it's probably the most cost effective to implement.

*We can use polynomial remainder theorem, it can work with things like $(x-(x-7))$ aka 7. But, that and other modular arithmetic tricks, is how we get to most divisibility tricks to begin with.

*$(n-1)^2+1$ integers always have a subset with a sum divisible by n (via pigeonhole principle). But, does going through potentially all 10,295,472 combinations of 7 from  a set of 37 digits, repeatedly until you are left with 30 non-zero digits ( not necessarily clumped together) in the entire number , sound appealing to find out if a large number is divisible by 7 ? Welcome to the subset sum problem, applied to multisets. 

*Most of the above facts seem useful ( plus a few more), until you consider implementing them. If you don't have enough digits, you can't implement them. Once you do, good luck going down lots of dead ends potentially.


example:
142859374923636582974652016665013284472978368643690531468097543
okay if I summed things right it's a multiple of 3 (bad choice of digits, casted out multiples of 3 using digit sum rule).
multiple of 5 test via the 4th point:
14285937492363658 has a subset of digits that's a multiple of 5, we can get rid of the whole thing it sums to a multiple of 5,
29746520166650132 Also sums to a multiple of 5 ...
84472978368643690 Also sums to a multiple of 5 ... ( what I get for not using a random number)
531468097543 Also sums to a multiple of 5 but isn't 17 digits.
Of course the digit sum trick plus pigeonhole principle aren't useful as the base being divisible by 5 is enough, just to check the last digit. in base's that have remainder 1 on division  by 5 the number would have shrunk to 12 digits or less. It would change which digits mattered in different bases.
