In this paper we present an improved algorithm for counting points on elliptic curves over finite fields. It is mainly based on Satoh-Skjernaa-Taguchi algorithm [SST01], and uses a Gaussian Normal Basis (GNB) of small type t ≤ 4. In practice, about 42% (36% for prime N) of fields in cryptographic context (i.e., for p = 2 and 160 < N < 600) have such bases. They can be lifted from $$ \mathbb{F}_{p^N } $$ to ℤp N in a natural way. From the specific properties of GNBs, efficient multiplication and the Frobenius substitution are available. Thus a fast norm computation algorithm is derived, which runs in O(N 2μ log N) with O(N 2) space, where the time complexity of multiplying two n-bit objects is O(n μ). As a result, for all small characteristic p, we reduced the time complexity of the SST-algorithm from O(N 2μ+0.5) to $$ O(N^{2\mu + \frac{1} {{\mu + 1}}} ) $$ and the space complexity still fits in O(N 2). Our approach is expected to be applicable to the AGM since the exhibited improvement is not restricted to only [SST01].