Number of divisors of an integer of form 4n+1 and 4n+3 Suppose $n$ is a large odd integer. Let $D_1(n)$ be the number of divisors of $n$ of the form $4k+1$ and let $D_3(n)$ be the number of divisors of the form $4k+3$. I would like to compute $(D_1(n),D_3(n))$. 
As Joe Silverman points out, the number of representations of $n$ as a sum of two squares of integers is $4(D_1(n)-D_3(n))$. For example, $D_1(225)=6$ and $D_3(225)=3$, so there are $4(6-3)=12$ lattice points on the circle of radius $\sqrt {225}$ centered at the origin including $(0,15)$ and $(-9,-12)$.

Is there a faster way to find $(D_1(n),D_3(n))$ than factoring $n$?


Original:
Hi, one way to do so is to list all the divisors of the integer and check each if it is of the form $4n+1$ or $4n+3$. 
Is there any faster method to it, especially for large $n$?
 A: A faster way would involve looking at the prime factorization of the integer.
Let n be pq, where q contains all the 1 mod 4 prime factors of n, and q contains all the 3 mod 4 prime factors.  Then the number of factors of n which are 3 mod 4 is just the number of factors of q times the number of 3 mod 4 factors of p, which is close to half the number of factors of p.  I'll let you finish the details, including the case that n is even.
Gerhard "Ask Me About System Design" Paseman, 2011.03.16
A: Not quite what you're asking, but an interesting theorem of Legendre's says that the number of ways of writing an integer $N$ as a sum of two squares is $4D_1(N)-4D_3(N)$, where $D_1(N)$ is the number of positive divisors of $N$ that are congruent to 1 modulo 4 and $D_3(N)$ is the number of positive divisors of $N$ that are congruent to 3 modulo 4. There are undoubtedly also results proved via analytic methods that describe the distribution of $D_1(N)$ and $D_3(N)$. But I'd have to agree with the other posters that computing $D_1(N)$ and $D_3(N)$ for a specific $N$ sounds about as hard as factoring $N$. Indeed, if $N=pq\equiv 1 \pmod{4}$, computing $D_1(N)$ is equivalent to computing the first bit in the factors of $N$, which seems hard.
