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

The $\sigma_i(n)$ function is an important arithmetic function and as typical for such functions, it can not be computed efficiently for large input parameters $n$ due to the factorization problem. But in contrast to $\sigma_1(n)$, which does reveal the factorization of $n$ immediately (at least if $n=pq$), $\sigma_0(n)$ does not, or at least not that easy (see Part 2 and Part 1). Additionally, $\sigma_1(n)$ has also the strange property that it can be computed recursively, as i showed in that [post].

However, we know how to compute, or better, how to decide, if $\sigma_0(n)$ is $2$ or not. This is because $\sigma_0(n) = 2$ if and only if $n$ is a prime number. And primality can be checked by the AKS-Algorithm in deterministic polynomial time. If AKS is too slow for you, there much more faster probabilistic polynomial time algorithms. They utilize that a prime number has special properties, e.g., they use Fermat-Little-Theorem. But so called base-$b$ pseudo prime numbers can survive this process and still pretend to be a prime number. Repeating the whole process with different values for $b$ often helps. Only a few pseudo prime numbers still remain for nearly all choices of $b$. These numbers are called carmichael numbers, and in [1] it was proved that there are infinite many such numbers. However, the probability to announce a false-positive for such algorithm is negligible after a few rounds.

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."

Sum of Divisors Function - Euler's recursion

Number theory has many functions that are based on the arithmetical properties of a given input integer $n$. These functions are called number-theoretic functions. Well known examples are, e.g., the Euler's Totient Function and The Möbius Function. Since arithmetical properties often depend in one or the other way on the integer's prime factorization, these functions are usually hard to compute for large integers due to the factorization problem. One of these functions, that heavily depends on that factorization, is the Divisor Function.

Definition [Divisor Function] Given an integer $n$ then the divisor function $\sigma_k(n)$ is defined as $$ \sigma_k(n) := \sum_{d|n}d^k$$