We obtain nontrivial estimates of quadratic character sums of division polynomials $\Psi_n(P)$, $n=1,2, \dots$, evaluated at a given point $P$ on an elliptic curve over a finite field of $q$ elements. Our bounds are nontrivial if the order of $P$ is at least $q^{1/2 + \varepsilon}$ for some fixed $\varepsilon > 0$. This work is motivated by an open question about statistical indistinguishability of some cryptographically relevant sequences that was recently brought up by K. Lauter and the second author.

We obtain new results about the number of trinomials $t^n + at + b$ with integer coefficients in a box $(a,b) \in [C, C+A] \times [D, D+B]$ that are irreducible modulo a prime $p$. As a by-product we show that for any $p$ there are irreducible polynomials of height at most $p^{1/2+o(1)}$, improving on the previous estimate of $p^{2/3+o(1)}$ obtained by the author in 1989.