# Can we count primes in residue classes quickly?

Using combinatorial methods (due to Legendre, Lehmer, Meissel, Lagarias, Miller, Odlyzko, Deléglise, Rivat, and probably others) it's possible to count the number of primes up to $N$ quickly -- in time $O(N^{2/3})$ or even $O(N^{3/5})$. But suppose we wanted to count only the primes $p$ such that $p\equiv x\pmod m$. Is there a way to calculate this quickly, in time comparable to the above?

Of course if $m$ were large it would be faster to count the primes directly, so you can assume that $m$ is small compared to $N$.

Different methods (e.g. analytic) would also be of interest to me, but my understanding is that these are barely practical even at the largest numbers to which $\pi(N)$ has been computed and are therefore not directly of interest to me.

-