  We develop a novel sampling theorem for functions defined on the
three-dimensional rotation group SO(3) by connecting the rotation group to the
three-torus through a periodic extension. Our sampling theorem requires $4L^3$
samples to capture all of the information content of a signal band-limited at
$L$, reducing the number of required samples by a factor of two compared to
other equiangular sampling theorems. We present fast algorithms to compute the
associated Fourier transform on the rotation group, the so-called Wigner
transform, which scale as $O(L^4)$, compared to the naive scaling of $O(L^6)$.
For the common case of a low directional band-limit $N$, complexity is reduced
to $O(N L^3)$. Our fast algorithms will be of direct use in speeding up the
computation of directional wavelet transforms on the sphere. We make our SO3
code implementing these algorithms publicly available.
