What if $\sigma_0(n)$ could be computed efficiently?

What would be the consequences if the sum of divisors function with $k=0$ could be computed efficiently, that is polynomial in $\log (n)$ if $n$ is the input to $\sigma_0(n)$? Note that if $n=p_1^{e_1}p_2^{e_2}...p_m^{e_m}$ then $$\sigma_0(n) = \sum_{d|n} d^0 =  \sum_{d|n} 1 = (e_1+1)(e_n+1)...(e_m+1)$$ For square-free numbers $n$, this is always a power of $2$, hence $\log_2(\sigma_0(n))$ gives the number of prime factors in this case. Furthermore, the famous AKS-algorithm gives a deterministic polynomial time algorithm, that decides if $\sigma_0(n) = 2$ or not, i.e. $n$ is prime or composite.

For the general case, Terence Tao gave an heuristic argument that generally this should be as hard as factoring a number:

"There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors  problem is believed to have comparable difficulty to factoring itself."

Tao argues that such a prime factor counting algorithm would probably also work over other number fields, i.e., the gaussian integers. For example, assume that we already know that $n$ has two prime factors, i.e. $n=pq$ when factored over the integers. Now assume you apply your magic algorithm that returns the number of prime factors of $n$ over $\mathbb{Z}[i]$: Based on the result, one could conclude non-trivial information about the primes $p$ and $q$. That is, because the result will be either:

1. Two prime factors $\rightarrow$ both primes $p$, $q$ (so one over the integer) are of the form $3+4k$
2. Three prime factors $\rightarrow$ one prime of $p,q$ is of the form $3+4k$ and the other of the form $1+4k$
3. Four prime factors $\rightarrow$ both primes $p$ and $q$ are of the form $1+4k$

The reason is, that gaussian primes are elements $a+bi$ whereof either

• a or b is zero and the other is a prime of the form $3+4k$
• both a non-zero and $a^2+b^2$ is a prime of the form $1+4k$.

E.g. assume $n = pq$ and $p \equiv 1\pmod{4}$ and $q = \equiv 3\pmod{4}$. If you factor $n$ over $\mathbb{Z}[i]$ you get three primes $\pi_1 = q$ (or associates) and $\pi_2 = (u+vi)$ and $\pi_3 = (u-vi)$ such that $p_2\pi_3 = u^2-uvi+uvi-v^2i^2=u^2+v^2 = p$. I.e. the factorization of $41\cdot 43$ over the gaussian integers is $$41\cdot 43 = 43\cdot(-4-5i)\cdot(-4+5i)$$
If one repeats the procedure with different number fields, at the end one could use the chinese remainder theorem to reconstruct $p$ and $q$.
However, the assumption that any algorithm that counts the number of prime factors of $n$ over the integers efficiently, will work over other number fields is not guaranteed to be true. Perhaps the algorithm needs the ordering property of $\mathbb{Z}$ to work successfully, which does not exists over $\mathbb{Z}[i]$.

So, we restrict our attention to an algorithm that only counts the number of prime factors of an integer $n$ over the integers efficiently. Otherwise, since it could help to factorize integers, it seems too powerful and such an algorithm probably does not exist. Can such an algorithm nevertheless improve on open problems or help to make things more efficient?

I think, one of its major contribution would be to help which factoring algorithm to choose given a target integer $n$ to minimize the overall complexity. Some algorithms have a running-time that is based on the smallest prime factor of $n$. So if the algorithms detects $4$ prime factors, then the smallest factor must be less than $n^{1/4}$, and probably one should pick the ECM method to search for this factor. If it happens that $n$ has only two factors and then perhaps choosing a general purpose algorithm like the general number field sieve seems to be more appropriate.

However, this yield seems a little thin to me, in respect of an algorithm that manages to return non-trivial information about a prime-factorization. Are there any other improvements that such an algorithm will cause?