  Primordial magnetic fields (PMF) can create polarization $B$-modes in the
cosmic microwave background (CMB) through Faraday rotation (FR), leading to
non-trivial 2-point and 4-point correlators of the CMB temperature and
polarization. We discuss the detectability of primordial magnetic fields using
different correlators and evaluate their relative merits. We have fully
accounted for the contamination by weak lensing, which contributes to the
variance, but whose contribution to the 4-point correlations is orthogonal to
that of FR. We show that a Planck-like experiment can detect scale-invariant
PMF of nG strength using the FR diagnostic at 90GHz, while realistic future
experiments at the same frequency can detect 10^{-10} G. Utilizing multiple
frequencies will improve on these prospects, making FR of CMB a powerful probe
of scale-invariant PMF.
