Why is integer factoring hard while determining whether an integer is prime easy?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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).

Answer 5

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.

Answer 6

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.

Answer 7

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).

Answer 8

Determining whether the multiplicative group of ${\bf Z}/n{\bf Z}$ can be generated by a single element is easy (pretty much as easy as determining whether $n$ is prime), finding a single element which generates is hard.

Answer 9

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.