cross-correlation one large image and many small images

I have one large NxN image (grey scale), and many small nxn images (n always the same). Both N and n are powers of two. Padding the small images with zeros so as to use Fast Fourier Transform seems to lose the advantage that n is much smaller than N, but I don't know much about FFT, so there may be a standard way round this. Is there an algorithm that takes advantage of the small size of n?

[David Epstein]

Oops! My asymptotic estimate is not sensible, for several reasons. The main flaw is that fft on the large matrix is already $O((N^2).\log(N))$. So I'll edit my question and remove the "hoped-for" asymptotic estimate, which is wildly over-optimistic.