31
$\begingroup$

In 2002, the discovery of the AKS algorithm proved that it is possible to determine whether an integer is prime in polynomial time deterministically. However, it is still not known whether there is an algorithm for factoring an integer in polynomial time.

To me, this is the most counter-intuitive observation in mathematics. If one can know for certain that a given integer is composite, why is it apparently so difficult to find its factors? Why doesn’t knowing that something exists give one a recipe for determining what that something is?

One way to resolve this problem would be to find a polynomial time algorithm to factor integers. However, if this were possible, it appears that a completely new idea would be needed to do so.

My question is is there an example of a problem similar to integer factorization in which it has been proven that an algorithm can determine the existence of a certain entity in polynomial time but there is no algorithm that computes that entity in polynomial time?

$\endgroup$
14
  • 37
    $\begingroup$ But don't we have abundant trivial examples of this? Every traveling salesman problem provably has an optimal solution, but it is infeasible to find it. Every Boolean expression achieves it's maximal value, but it is infeasible in general to find it. Every integer has a factorization into primes, but it is infeasible to find it. $\endgroup$ Dec 5, 2022 at 13:38
  • 18
    $\begingroup$ As @JoshuaZ's answer suggests, the reason this seems counterintuitive is that we are taught at a young age to test non-primality by searching for factor, which is inefficient to the best of our knowledge. Efficient primality tests rely on other characterizations of primes involving congruences mod n. Because our intuition is formed long before we learn of such things, it seems very counterintuitive that there is another approach. $\endgroup$ Dec 5, 2022 at 14:28
  • 6
    $\begingroup$ A lot of decision problems in P can be converted into construction problems in polynomial time by bisection: you ask a series of questions of the form "Is there a solution $x \le x_0$?" Primality testing vs factoring breaks this paradigm because the question which can be answered in polynomial time is "Is there a solution $1 < x < n$?", so maybe what you're looking for is decision problems with similarly restricted inputs. $\endgroup$ Dec 5, 2022 at 14:41
  • 6
    $\begingroup$ Why, indeed. We don't know that integer factoring is hard at all, so it is quite difficult to say why... We only know that it is hard to show whether it is hard, and we can discuss why the insights used in primality testing don't help. $\endgroup$
    – usul
    Dec 6, 2022 at 0:04
  • 3
    $\begingroup$ @usul Actually, I think Hex is not so dissimilar. There is an interesting decision problem: Is this position a forced win for the player whose turn it is to move? The decision problem is trivial only in the special case of the empty board. The main difference, as I see it, is that factoring is in NP while Hex is PSPACE-complete. $\endgroup$ Dec 6, 2022 at 2:33

8 Answers 8

55
$\begingroup$

What I think you're asking for are examples of search problems that seem to be hard, while a corresponding decision problem is solvable in polynomial time (but not totally trivial). It is true that such problems do not arise in practice very often; typically, an efficient decision procedure can be turned into an efficient search. For example, if you can determine whether or not an arbitrary SAT instance is satisfiable, then you can find satisfying assignments easily, just by taking each variable in turn, trying the two possible settings in turn (TRUE or FALSE), and asking if the smaller instance is satisfiable. Or, for an optimization problem, if you can solve the decision problem ("is there a solution with cost at most $k$?") then you can find the optimum value by performing a binary search on $k$.

You might find examples of what you're looking for on the CS Theory StackExchange: Easy decision problem, hard search problem. But perhaps none of the examples there is as convincing as factorization.

It should be pointed out, however, that "the decision version of factorization" is (arguably) not primality testing, but the following problem:

Given a positive integer $n$ and a bound $k$, does there exist $p$ ($1 < p < k$) such that $p\mid n$?

A fast algorithm for this decision problem would indeed yield a fast algorithm for factoring. So arguably, what's special about factoring is that there is "a" decision problem (primality testing) that looks very close to "the" decision problem for factoring, but which seemingly cannot be parlayed into a solution to "the" decision problem. Stated this way, it's perhaps less surprising that there appears to be a computational gap between the two decision problems. An analogy here might be subgraph isomorphism, which is $\mathsf{NP}$-hard, while graph isomorphism appears to be much easier.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer. The Hamiltonian cycle in degree three graphs example is exactly what I was looking for. $\endgroup$ Dec 15, 2022 at 16:04
  • 1
    $\begingroup$ @CraigFeinstein In that case, you may also be interested in other problems in the complexity class PPA or PPAD. $\endgroup$ Dec 15, 2022 at 16:14
  • $\begingroup$ @TimothyChow What is the decision version for primality (which here (as you say) looks very close to decision version for factoring)? $\endgroup$
    – Turbo
    Jan 5, 2023 at 11:33
  • 1
    $\begingroup$ @Turbo Simply replace $k$ with $n$ in the decision version of factorization. $\endgroup$ Jan 5, 2023 at 13:19
27
$\begingroup$

In the particular case of primality testing, primality testing is easier than factoring mainly because $p$ is prime if and only if $\mathbb{Z}/p\mathbb{Z}$ forms a field. This has a lot of consequences, including that there are primitive roots, and that Fermat's Little Theorem and some generalizations hold. AKS, as well as Miller-Rabin both use variants of Fermat's little theorem or applications thereof. For example, AKS relies on the result that if $n>2$, and $(a,n)=1$, then $n$ is prime if and only if $(X+a)^n \equiv X^n+a$ (mod $n$) in the ring $(\mathbb{Z}/n\mathbb{Z})[X]$. What is going on here then shouldn't be counterintuitive. All primes have $\mathbb{Z}/n\mathbb{Z}$ look very similar. But for composites, the behavior of $\mathbb{Z}/n\mathbb{Z}$ is much harder to understand.

If there is something surprising here, it might be that the problem of factorization of semiprimes, $n=pq$ is about as tough apparently as factorization of generic numbers with a few prime factors, since one might expect that if $n=pq$, then the behavior would still be easier to control. But we actually expect that it is tough enough in this case that we've based some cryptographic systems (e.g. RSA) on this being hard.

$\endgroup$
21
$\begingroup$

Let me give a slightly different example. The Baumslag-Gersten group is a one-relator group with the presentation $\langle a, b \mid [a, a^b] = a\rangle$. This has a Dehn function which grows faster than any finite tower of exponentials -- that is, there are short words which are equal to the identity element, but for which it nevertheless takes a ridiculously long time to find a sequence of applications of the relation (and/or the trivial relations) which proves this.

On the other hand, Myasnikov, Ushakov & Won [1] proved that the word problem of this group has word problem decidable in quadratic time. In other words, given a word $w$, one can say "yep, $w$ is equal to the identity" or "no, it is not" in time quadratic in $|w|$; and yet, in the former case, one has not exhibited* a sequence of transformations verifying this (and, indeed, one cannot -- it's just far too long to do this in quadratic time), even though one exists!

Thus, this example satisfies your requirement "... an algorithm can determine the existence of a certain entity in polynomial time but there is no algorithm that computes that entity in polynomial time?"

${}$

*In truth, one can "parameterize" such a sequence in quadratic time by compressing certain steps (indeed this is how the word problem is solved), and for this reason the example is perhaps not entirely satisfactory...

[1] Myasnikov, Alexei; Ushakov, Alexander; Won, Dong Wook, The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable., J. Algebra 345, No. 1, 324-342 (2011). ZBL1248.20038.

$\endgroup$
12
$\begingroup$

One can also compare it with decision problem vs. counting problem. A curious example are the Littlewood-Richardson coefficients (indexed by three integer partitions). There is a polynomial time algorithm to determine if such a coefficient is non-zero or not, computing the actual value is much harder (proved to be #P-complete by Narayanan).

$\endgroup$
1
  • 11
    $\begingroup$ A much simpler example are perfect matchings in bipartite graphs: one can decide in polynomial time if such a matching exists, but counting them is #P-complete (this is the same as computing the permanent of $\{0,1\}$-matrices). $\endgroup$ Dec 6, 2022 at 9:48
10
$\begingroup$

If one can know for certain that a given integer is composite, why is it apparently so difficult to find its factors? Why doesn’t knowing that something exists give one a recipe for determining what that something is?

The reason this is possible is that there are further properties of prime numbers (theorems about prime numbers), so if your number doesn't fit such a property then it can't be prime without having to know how the number isn't prime in an explicit way.

Example. If $p$ is prime then $a^{p-1} \equiv 1 \bmod p$ for all $a$ from 1 to $p-1$, so if $n \geq 2$ and we can get $a^{n-1} \not\equiv 1 \bmod n$ for even one $a$ from $1$ to $n-1$ then $n$ isn't prime, and this isn't because we found a nontrivial factorization of $n$: we showed $n$ doesn't satisfy a property that all prime numbers satisy, which goes beyond the mere definition of prime numbers. For example, taking $n = 17399$, $2^{n-1} = 2^{17398} \equiv 16518 \not\equiv 1 \bmod n$, so $n$ is not prime and the reason we know this is not due to how $n$ factors. So we don't learn from this a way to factor $n$. Of course $n$ is small enough that a computer reveals $n = 127 \cdot 137$ immediately, but for very large numbers there can be a huge gap in time between knowing $n$ is not prime and knowing a nontrivial factor. Consider $n = 2^{2^{14}}+1$, the $14$th Fermat number. It has 4933 digits and was proved to be composite in 1961 by Hurwitz and Selfridge, but a nontrivial factor of this number was first found nearly 50 years later, in 2010.

This kind of phenomenon (properties that go beyond the initial definition of a concept) is not at all limited to primes vs. composites.

Example. Consider the property of having unique factorization. In $\mathbf Z$ and the polynomials $\mathbf R[x]$ there is unique factorization. Rings with unique factorization all satisfy a number of properties that are not just about the definition, so a ring that doesn't satisfy such a property fails to have unique factorization and it isn't because we must know an explicit counterexample to the unique factorization property directly. For instance, all rings with unique factorization are integrally closed, and $\mathbf Z[\sqrt{5}]$ is not integrally closed (the number $(1+\sqrt{5})/2$ in the fraction field is a root of the monic polynomial $x^2 - x - 1$ with coefficients in $\mathbf Z[\sqrt{5}]$ without being in $\mathbf Z[\sqrt{5}]$), so $\mathbf Z[\sqrt{5}]$ doesn't have unique factorization and the reason we know this is not from finding an explicit counterexample in $\mathbf Z[\sqrt{5}]$ to unique factorization.

More generally, for every $d \in \mathbf Z$ that is not a perfect square and satisies $d \equiv 1 \bmod 4$, $\mathbf Z[\sqrt{d}]$ is not integrally closed because $(1+\sqrt{d})/2$ is a root of $x^2 - x - (d-1)/4$, and thus it does not have unique factorization, and I did not need to contradict the unique factorization property explicitly to show these rings don't have unique factorization: I showed they all fail to satisy a property (being integrally closed) that is common to all rings with unique factorization.

$\endgroup$
5
$\begingroup$

It is like cooking. A recipe can be easy to follow, but figuring it out from the resulting meal can be hard (cf. secret recipe).

$\endgroup$
2
  • 1
    $\begingroup$ So in this analogy, testing if a number is prime is just telling if the recipe has more than one ingredient, and factoring is determining all the ingredients and their proportions? $\endgroup$
    – JoshuaZ
    Dec 6, 2022 at 22:54
  • 2
    $\begingroup$ @JoshuaZ I meant that prime testing was like picking the required ingredients from the store or the fridge: we recognize milk, egg, flour etc. easily. In contrast, factoring is like figuring out what went into a meal, which is a harder task (e.g. what makes Coca Cola). $\endgroup$
    – GH from MO
    Dec 6, 2022 at 22:59
5
$\begingroup$

There's exists a polynomial-time algorithm to factor integers, Shor's algorithm, which runs in $O[N^2 \log[N] \log\log[N]]$ time, where $N$ is the number of digits of the integer you want to factor.

I think that using a non-deterministic Turing machine you can also factor integers in polynomial time.

Regarding your question, I suspect this may be somehow related to exponential growth: in a (say, binary) tree, the number of paths growths exponentially as you add more levels, so the difficultly of finding the "correct path" seems to grow exponentially (assuming there's no structure to exploit), but verifying that any given path is the "correct one" is linear (in the height of the tree). (But verifying all paths is again exponential. Think of "verifying some path" a single piece of a puzzle, and of "verifying all paths" as the entire puzzle.)

Something similar happens in the infinite (think of the Stern-Brocot tree): the set of all finite paths in an infinite binary tree is (isomorphic to) the rationals ${\bf Q}$, but the set of all infinite paths is (isomorphic to) the irrationals, so your cardinality has grown exponentially, from $\aleph_0$ to $2^{\aleph_0}$.

For integers, as you add digits, the number of integers grows exponentially too.

$\endgroup$
-2
$\begingroup$

For the most common real world use cases for prime factorization and primality testing on the internet (RSA public key cryptography) primality testing in cryptographic key generation is probabilistic instead of perfect. This way integers may be generated that are very, very large in a reasonable time and with a vanishingly small probability of being composite for key generation in a reasonable time.

In the meant time factorization of the resulting key must use algorithms that are guaranteed to work. This increases the multiplier between key generation cost and cracking the system.

This is on top of the difference that exists using correct methods for both operations.

Note on edit: I was wrong on many of the details and this has been changed to only reflect the last remaining point.

$\endgroup$
7
  • 3
    $\begingroup$ The question concerns the deterministic primality testing algorithm, not probabilistic ones. $\endgroup$ Dec 7, 2022 at 0:36
  • 3
    $\begingroup$ This is incorrect. First, primality checking need not be probabilistic for the range used in practical RSA keys. For example, APR can handle primes for RSA keys in the range used. We often use probabilistic tests in practice, since you can run Miller-Rabin or whatever your preferred test to make the error percentage tiny. Your last claim is also wrong. Testing that p or q is prime, is not the same difficulty as far as we can tell of finding p and q given n=pq. If one could show that it would be a massive breakthrough and certainly not "by definition." $\endgroup$
    – JoshuaZ
    Dec 7, 2022 at 0:38
  • 1
    $\begingroup$ @JoshuaZ so I've confused sieving n for sieving p or q? I think it might still only average some fixed multiple though if neither p nor q are particularly small. Given the polynomial order of the problem. Like, if the sieve was order N^2 then the cost to factor a number 2N long would only be 4 times as much. $\endgroup$
    – davolfman
    Dec 7, 2022 at 0:50
  • 2
    $\begingroup$ @davolfman If you mean Eratosthenes sieve, that's very inefficient in general, and doesn't even benefit that much from fast primality checking. Let's say you could check if a number of any size was prime in a picosecond. Then to use naive sieving to sieve a number with only around 10^72 or so digits would take more time than the universe has been around for, and a number around 10^300 would take more time than the functional heat death of the universe. But I can get even just Wolfram Alpha to factor a number around 10^80 in a few seconds, so we're doing something different. $\endgroup$
    – JoshuaZ
    Dec 7, 2022 at 1:02
  • 1
    $\begingroup$ @davolfman A naive sieve takes around $sqrt(N)$ time to factor $N$. Nut the point is that modern systems aren't doing naive sieving. We have a lot of other algorithms, including the general number field sieve, which is only a sieve in a very broad sense en.wikipedia.org/wiki/General_number_field_sieve Notice also that the run time for it is an $L_n$-type, which is not either of the cost types you have above. Most importantly, methods like it do not just check all the prime divisors up to a specific point, so they would not benefit from faster or even constant time prime checking. $\endgroup$
    – JoshuaZ
    Dec 7, 2022 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.