Given an elliptic curve E over a field of positive characteristic p, we
consider how to efficiently determine whether E is ordinary or supersingular.
We analyze the complexity of several existing algorithms and then present a new
approach that exploits structural differences between ordinary and
supersingular isogeny graphs. This yields a simple algorithm that, given E and
a suitable non-residue in F_p^2, determines the supersingularity of E in O(n^3
log^2 n) time and O(n) space, where n=O(log p). Both these complexity bounds
are significant improvements over existing methods, as we demonstrate with some
practical computations.