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.