The idea of writing A in binary and forming the 0/1 polynomial such that p(2) = A is nifty. Then if you factor p(x) it into two polynomials with integer coeffi

The idea of writing A in binary and forming the 0/1 polynomial such that p(2) = A is nifty. Then if you factor p(x) it into two polynomials with integer coefficients u(x)v(x) you have u(2) and v(2) are divisors of A, so if none of them are equal to +-1 you have found something. Assuming it is easy to factor the polynomials. Factoring polynomials is somewhat easy, but you have to specify factoring into what. The terminology needs a little clean-up. By the fundamental theorem of algebra we know every polynomial over the reals factors into a product of polynomials of degree no more than 2. So they probably don't mean factoring/primality in general but a definition of factoring in to square-free polynomials. Factoring into square-free polynomials is easy as if q(x)*q(x) divides into p(x) then it also divides into p'(x) (the derivative of p(x) with respect to x) and therefore divides into gcd(p(x), p'(x)). And the gcd() will have integer coefficients and be degree less than p(x) (so not equal to p(x) and degree >= q(x), so if q(x) is non-trivial it forces something nice to happen; even if you don't know what q(x) is).