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? (Part 2)

In the first post regarding this topic, i sketched why an algorithm that counts the number of prime factors of an integer could lead to an algorithm that actually could factorize that integer. The application of such an algorithm to different number fields would lead to non-trivial information about the prime factors due to the definition of prime numbers in $\mathbb{Q}(\sqrt{d})$. The hope is, that this information would eventually allow us to reconstruct the entire prime numbers.

In this post i will show some basic facts about different number field and what information they leak about prime factors of $n$ if $\sigma_0(n)$ is known.

Brainteasers

Brainteasers become more and more popular in these days. You hear them from friends, in bars, read them on blogs and they are even used in job interviews to puzzle the candidates. Some of them are easy and some of them are tricky and some of them are really hard.

A common teaser for example is:

"A melon weights 1200gr and contains 99% water. Suppose that after one week the amount of water has reduced to 98%. What is the new weight of the melon?"

[Spoiler Start: White-on-White / Mark with the mouse]
It is 600gr! Just observe that the $1200$gr is made up of  $99\%$ water and $1\%$ melon-meat. That are $1188$gr water $12$gr melon-meat. After one week the weight of the melon reduces the $x$gr, whereof $y$gr are water and still $12$gr melon-meat. And it is known that the $y$gr water are now $98\%$, hence the $12$gr melon-meat must be $2\%$. But if $2\%$ are $12$gr, then $100\%$ are $600$gr.
[Spoiler End]