Factorisation patterns of division polynomials (Q1764332)

Let \(E: y^2=x^3+ax+b\) be an elliptic curve over a finite field \({\mathbb F}_q\) of characteristic greater than 3. The zeros on \(E\) of the \(l\)th division polynomial are precisely the \(l\)-torsion points. Factors of the division polynomials of \(E\) were used by Elkies in his improvement of Schoof's algorithm for counting the number of rational points on \(E\). Let \(l\) be an odd prime, different from the characteristic of \({\mathbb F}_q\). By studying the action of Frobenius on torsion subgroups, the author is able to determine the degrees of all irreducible factors of the \(l\)th division polynomial of \(E\) and the number of factors of each possible degree in terms of the degree of the minimal extension of \({\mathbb F}_q\) over which a nonzero \(l\)-torsion point of \(E\) is defined. In the erratum the statement of Proposition 2 is corrected due to a flaw in the proof.