The basic Schoof algorithm provides an efficient method for computing the trace of an endomorphism \(\phi \) of an elliptic curve E. It collects small primes \(\ell \) whose product exceeds \(4\sqrt{\deg (\phi )}\) , and computes the trace of \(\phi \) modulo each \(\ell \) by working over the \(\ell \) -torsion subgroup of E. For a supersingular elliptic curve E defined over \(\mathbb {F}_{p^2}\) , it is efficient to randomly sample a point on E of order \(\ell \) , provided that \(\ell \) divides the order of the group of \(\mathbb {F}_{p^{2e}}\) -rational points on E for some small extension degree e. In this paper, we incorporate the random sampling method as a subroutine within Schoof’s algorithm and analyze its heuristic complexity. Furthermore, we combine the random sampling method with additional techniques, such as the use of kernel polynomials, to further accelerate Schoof’s algorithm on supersingular elliptic curves. We demonstrate the effectiveness of our hybrid approach through experimental results.