Use the coefficient norm ||f||_1, the sum of absolute coefficients. The parity formula gives ||p_ell||_1<=2^ell binom(2ell-1,ell-1)<=2^(3ell). In successive monic divisions by Y^2-Y, each leading-term elimination increases the combined quotient/remainder norm by at most a constant factor three. There are O(ell^2) eliminations, hence every coefficient in the linear remainders e_j has magnitude at most 2^{O(ell^2)} and polynomial bit length. There are polynomially many stored coefficients and arithmetic operations. Large integer values do not mean exponentially many bits; the bit length is logarithmic in their magnitude.