1
$\begingroup$

Suppose we want to build a primality testing algorithm for the numbers limited to the set $A =\{1, ..., 2^n\}$ and $n$ is reasonably large. The prime-number theorem tells us that there are approximately $\frac{2^n}{n \ln 2 }$ prime numbers within the set. Now, if we had a permutation $\sigma : A \to A$ which has the property that $\sigma(a) > \sigma(b)$ whenever $a$ is composite a $b$ is prime, we could decide whether a number $k \le 2^n$ is prime, by looking at $\sigma(k) < \frac{2^n}{n \ln 2 }$. Obviously, there would be a small amount of numbers for which this would not work because the prime number theorem only works asymptotically, but overall it could be very reliable.

The question is, how do we obtain a $\sigma$ with the required property? Now since we defined $A$ to have $2^n$ elements, it's natural to represent any number from the set by $n$ binary digits. Since $\sigma$ is a permutation, it can be implemented as a reversible computation. That means, we can represent this computation as a circuit with $n$ wires and some number of Toffoli gates. Denote $t(n)$ the minimal number of Toffoli gates required to implement a $\sigma$ with the required property.

What is $t(n)$? Is it bounded by a polynomial? I don't know. But at least for small values of $n$, $t(n)$ could could be found on a computer by brute-force. Hopefully, we could see a pattern and make a conjecture about it's growth. Obviously, there could be other variants of this problem, for example if we instead have different $A$ or some other universal gates, we could get differet values for $t(n)$ but I would not anticipate it to be much different. I thought this approach could provide some insight into the famous problem of primality testing, but first I'd like to learn whether such an approach has been already studied or if there are some simple arguments why $t(n)$ cannot be polynomial. Any references please?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Deterministically computing this $\sigma$ in polynomial time almost gives an infinite P-printable set of primes (it might not, if all polynomially computable locations only hold fairly small primes, but that seems extremely unlikely), which is an open problem (see this CS theory answer) $\endgroup$
    – Daniel Weber
    Commented Mar 16 at 19:07
  • 1
    $\begingroup$ Also, via binary searching + polynomial time primality testing, this lets one compute $\pi(2^n)$ in time polynomial in $n$, which is also open as far as I know (and I think it's considered quite unlikely) $\endgroup$
    – Daniel Weber
    Commented Mar 16 at 19:14
  • 1
    $\begingroup$ I would expect finding a $\sigma$ sigma with this property to be difficult. However, assuming I do somehow slowly compute it once, I can store it and use if forever. If $t(n)$ is small, this would have implications on primality testing in applied settings: I would simply load the $\sigma$ program and execute it to test primality cheaply. $\endgroup$
    – user1747134
    Commented Mar 16 at 19:19

0

Reset to default

You must log in to answer this question.