Diophantine equations of the form $xy = n$

I am looking for a general way to estimate the number of possible solutions to solve the diophantine equation of the form $xy = n$, where $n$ is a positive integer.

Note that $n$ can be an unusually large number (thousands of digits long), and I am hoping to find a quick algorithm that can be run in reasonable time in a standard machine.

• This is more or less equivalent to factoring $n$; in any case it is at least as hard as deciding if $n$ is prime, and this was only very recently proven to be doable in polynomial time (en.wikipedia.org/wiki/AKS_primality_test). What do you need to do this for? Do you care more about upper or lower bounds? Jan 20, 2012 at 4:45
• I care about the upper bound (Big O complexity). Basically one of the programs I am working on reduces to this.
– Hari
Jan 20, 2012 at 4:59
• Okay, but how bad of an upper bound are you willing to settle for? Getting precise information for fixed $n$ requires knowing a lot about the prime factorization of $n$. Jan 20, 2012 at 6:12

With equality at a number $n$ near $3.309 \cdot 10^{135},$ $$d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left( 1 + \frac{1}{\log \log n} + \frac{4.762350121177...}{\left(\log \log n \right)^2} \right)}$$
The number giving equality is $$2^{11} \cdot 3^6 \cdot 5^4 \cdot 7^3 \cdot 11^2 \cdot 13^2 \cdot 17^2 \cdot 19^2 \cdot 23^2 \cdot 29 \cdot 31 \cdots 293$$ with about $\; 3.677 \cdot 10^{21} \;$ divisors.
Once you have a divisor, call that $x,$ then you just have $y=n/x.$