This is not necessarily a research question, since I do not know, if someone is working on this or not, but I hope to gain some insight by asking it here:

The idea behind this question is to attach to a natural number in a “natural” way an entropy, such that “multiplication increases entropy”. (Of course one can attach very different entropies to natural numbers such that multiplication reduces entropy, but I will try to give an argument, why this choice is natural.) Let $ n$ be a composite number $ \ge 2$ , $ \phi$ the Euler totient function. Suppose a factorization algorithm $ A$ outputs a number $ X$ , $ 1 \le X \le n-1$ with equal probability $ \frac{1}{n-1-\phi(n)}$ such that $ 1 < \gcd(X,n) < n$ . Then we can view $ X$ as a random variable and attach the entropy to it $ H(X_n):=H(n):= \log_2(n-1-\phi(n))$ .

The motivation behind this definition comes from an analogy to physics: I think that “one-way-functions” correspond to the “arrow of time” in physics. Since “the arrow of time” increases entropy, so should “one-way-functions”, if they exist. Since integer factorization is known to be a candidate for owf, my idea was to attach an entropy which would increase when multiplying two numbers.

It is proved here ( https://math.stackexchange.com/questions/3275096/does-entropy-increase-when-multiplying-two-numbers ) that:

$ H(mn) > H(n) + H(m)$ for all composite numbers $ n \ge 2, m \ge 2$

The entropy of $ n=pq$ , $ p<q<2p$ will be $ H(pq) = \log_2(p+q-1) > \log_2(2p-1) \approx \log_2(2p) = 1+\log_2(p)$ .

At the beginning of the factorization, the entropy of $ X_n$ , $ n=pq$ will be $ \log_2(p+q-1)$ since it is “unclear” which $ X=x$ will be printed. The algorithm must output $ X=x$ as described above. But knowing the value of $ X$ , this will reduce the entropy of $ X$ to $ 0$ . So the algorithm must reduce the entropy from $ \log_2(p+q-1)$ to $ 0$ . From physics it is known, that reducing entropy can be done with work. Hence the algorithm “must do some work” to reduce the entropy.

My question is, which functions do reduce entropy? (So I am thinking about how many function calls will the algorithm at least make to reduce the entropy by the amount described above?)

Thanks for your help!