Binary hashing is an established approach for fast, approximate image search. It maps a query image to a binary vector so that Hamming distances approximate image similarities. Applying the hash function can be made fast by using a circulant matrix and the fast Fourier transform, but this circulant hash function must be learned optimally from training data. We show that a previously proposed learning algorithm based on optimization in the frequency domain is suboptimal. We show the problem can be solved exactly and efficiently by casting it as a convex maximum margin classification problem on a modified dataset. We confirm experimentally that this allows us to learn hash functions consisting of one or more circulant filters that provide better retrieval performance for the same query runtime as a linear hash function.