Introduction:

What follows is an information-theoretic lower-bound on the Computational Complexity of integer factorisation that is experimentally verifiable using automated program synthesis. This analysis implies that the RSA function is a one-way function and therefore \(\text{P} \neq \text{NP}\).

The average information gained from integer factorisation:

From the Prime Number Theorem, we may deduce that the average distance between consecutive primes \(P\) and \(Q\) is on the order of \(\sim \log P\), and according to the Cramér random model the probability of observing a prime in \([P+1,Q]\) is on the order of \(\sim \frac{1}{\log P}\) so the information gained from observing a prime in \([P+1, P + \log P]\) is on the order of:

\begin{equation} H(Q| Q \sim P + \log P) \approx - \sum_{i=1}^{\log P} \frac{1}{\log P} \log \big(\frac{1}{\log P}\big) = \log \log P \approx \log \log N \end{equation}

and given that almost all integers are incompressible, for large \(N\):

\begin{equation} N = P \cdot Q \implies K_U(N) \sim \log N = \log P + \log Q \end{equation}

where \(P\) uniquely determines \(Q\) and vice versa so the information gained from observing \(P\) is on the order of \(\sim \log N\).

It follows that, by an application of the AM-GM inequality, the average information gained from observing a prime in \([1,P]\) or \([P+1, P + \log P]\) is on the order of:

\begin{equation} \sqrt{\log N \cdot \log \log N} \leq \frac{\log N + \log \log N}{2} \end{equation}

This allows us to bound the search space \(\mathcal{L}\)(for \(P\) and \(Q\)) by:

\begin{equation} \mathcal{L} \geq \sqrt{\log N \cdot \log \log N} \end{equation}

which has units of bits, or the logarithm of distinct states(i.e. integers) considered by the search algorithm(i.e. integer factorisation).

The typical probability \(q\) of collapsing the entropy \(\mathcal{L}\):

Now, if we define the typical probability \(q \in (0,1)\) of collapsing the entropy \(\mathcal{L}\)(i.e. finding \(P\) or \(Q\)), we have \(q \approx e^{-\mathcal{L}}\) so the optimal number of mathematical operations will typically be on the order of:

\begin{equation} \frac{1}{q} \geq e^{\sqrt{\log N \cdot \log \log N}} \end{equation}

which may be viewed as a lower-bound on the typical number of states(i.e. integers) considered by an optimal integer factorisation algorithm running on a classical computer.

Discussion:

Due to a natural correspondence between integer factorisation and unbounded Koopman operators, a rigorous experimental investigation of this lower-bound is reducible to neural program synthesis for approximating the eigenfunctions of a suitable Koopman operator. In fact, I have proposed a challenge in neural program synthesis for precisely this purpose, Koopman Open, which begins on the 13th of September 2021.

References:

  1. Aidan Rocke (https://mathoverflow.net/users/56328/aidan-rocke), information-theoretic derivation of the prime number theorem, URL (version: 2021-02-20): https://mathoverflow.net/q/384109

  2. A. N. Kolmogorov Three approaches to the quantitative definition of information. Problems of Information and Transmission, 1(1):1–7, 1965

  3. G. J. Chaitin On the length of programs for computing finite binary sequences: Statistical considerations. Journal of the ACM, 16(1):145–159, 1969.

  4. R. J. Solomonoff A formal theory of inductive inference: Parts 1 and 2. Information and Control, 7:1–22 and 224–254, 1964.

  5. E. Kowalski. Arithmetic Randonnée: An introduction to probabilistic number theory. 2021.

  6. E.T. Jaynes. Information Theory and Statistical Mechanics I. The Physical Review. 1957.

  7. E.T. Jaynes. Information Theory and Statistical Mechanics II. The Physical Review. 1957.

  8. John A. Wheeler, 1990, “Information, physics, quantum: The search for links” in W. Zurek (ed.) Complexity, Entropy, and the Physics of Information. Redwood City, CA: Addison-Wesley.

  9. Lenstra, H. W.; Pomerance, Carl (July 1992). “A Rigorous Time Bound for Factoring Integers” (PDF). Journal of the American Mathematical Society.

  10. Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. Springer. 2001.