Factorisation patterns of division polynomials

Abstract

The choice of an elliptic curve for the implementa- tion of an elliptic curve cryptosystem requires count- ing the number of points on such a curve over a fi- nite field. An improvement of Schoof’s algorithm for counting the number of rational points on an ellip- tic curve defined over a finite field takes advantage of some factor of the division polynomials. In this paper, we study the possible factorisations of such division polynomials.