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?



Why is integer factoring hard while determining whether an integer is prime easy?
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](https://cstheory.stackexchange.com/questions/1848/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](https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem), which is $\mathsf{NP}$-hard, while graph isomorphism appears to be much easier.


