On the Computational Complexity of Heisenberg Uncertainty

In the following analysis, we model integer factorisation as an asymmetric information game where the expected time complexity is determined via entropy coding.

Introduction:

Alice and Bob are both experts in Computational Number Theory that enjoy a good game of integer factorisation. In this game, Alice typically prepares the integer factorisation problem by sampling two large primes from the interval \([1,N] \subset \mathbb{N}\) in such a way that the computational complexity of the problem is maximised.

On the other hand, Bob uses Maximum Entropy inference to determine the expected running time of an algorithm that efficiently factorises the product of two large primes. Thus, we may model integer factorisation as an asymmetric information game.

Integer factorisation as Entropy Coding:

While the game is repeated infinitely many times, Alice determines that each game has the same combinatorial structure. Without loss of generality, the problem may be formulated as follows:

An Uncertainty Principle for factoring semi-primes:

Given Bob’s symmetric ignorance of \(P\) and \(Q\), regardless of the number of times this game is played his information-theoretic uncertainty of \(P\) and \(Q\) denoted by \(\Delta_P\) and \(\Delta_Q\) must satisfy:

\[\begin{equation} \langle \Delta_P \cdot \Delta_Q \rangle = H(P) \cdot H(Q|P) = H(Q) \cdot H(P|Q) \tag{1} \end{equation}\]

The magnitudes of these entropies may be verified if we consider that, if \(P\) and \(Q\) were distinguishable, their entropies may be determined using the Asymptotic Equipartition Theorem.

In the case of \(P\) which Alice samples from \(\textrm{Geom}(\frac{1}{p})\), the average information gained from observing a prime in the interval \([1,N]\) is given by:

\[\begin{equation} \langle \Delta_P \rangle = \frac{\mathbb{E}[K_U(X_N)]}{\pi(N)} \sim \ln N \tag{2} \end{equation}\]

On the other hand, Alice samples the second prime \(Q\) from the interval \(|P-Q| \sim \ln N\) using the density:

\[\begin{equation} \forall X \sim U([1,N]), P(X \in \mathbb{P}) = \prod_{p \leq \sqrt{N}} \big(1-\frac{1}{p}\big) \tag{3} \end{equation}\]

so its average entropy is given by:

\[\begin{equation} \langle \Delta_Q \rangle = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n -\ln P(X \in \mathbb{P}) \sim \sum_{p \leq \sqrt{N}} \frac{1}{p} \sim \ln \ln N \tag{4} \end{equation}\]

However, as \(P\) and \(Q\) are a priori indistinguishable relative to Bob they are equiprobable with expected code length: \(\frac{1}{2} \langle \Delta_P \rangle + \frac{1}{2} \langle \Delta_Q \rangle \geq \sqrt{\langle \Delta_P \rangle \cdot \langle \Delta_Q \rangle}\) where indistinguishability implies that there is no way to know whether \(P\) and \(Q\) are correlated so it is fair to assume that they are independently and identically sampled:

\[\begin{equation} \langle \Delta_P \rangle \cdot \langle \Delta_Q \rangle = \langle \Delta_P \cdot \Delta_Q \rangle = \ln N \cdot \ln \ln N \tag{5} \end{equation}\]

Hence, from Bob’s perspective the expected code lengths for \(P\) and \(Q\) are equivalent:

\[\begin{equation} \langle \Delta_P \rangle = \langle \Delta_Q \rangle = \sqrt{\ln N \cdot \ln \ln N} \tag{6} \end{equation}\]

The expected time complexity of integer factorisation:

Finally, using the Asymptotic Equipartition Theorem we may deduce that the order of magnitude of the typical set is given by:

\[\begin{equation} e^{\langle \Delta_P \rangle} = e^{\sqrt{\ln N \cdot \ln \ln N}} \tag{7} \end{equation}\]

and as the candidate solutions are a priori equiprobable, the correct solution may only be found by performing exhaustive search on the set of \(\sim \sqrt{\ln N \cdot \ln \ln N}\) options.