We describe a novel FFAST (Fast Fourier Aliasing-based Sparse Transform) approach to estimating the spectra of sparse signals, based on a novel sub-sampling paradigm guided by the Chinese Remainder Theorem, and a coding-theoretic signal recovery framework based on sparse-graph codes. For concreteness, we focus our work here on how to efficiently compute the large, sparse Discrete Fourier Transform of a signal from its time-domain samples. In the setting where the spectrum of an n-length signal is exactly k-sparse, our FFAST algorithm has a sample complexity of less than 4k, and a computational complexity of O(k log n). We then show how to robustify our FFAST framework to the noisy setting of estimating a k-sparse spectrum in the presence of noise, with a sample complexity of O(k log n).