what is the most difficult computational problem whose answer is currently unknown, whose answer definitely exists, and whose answer (if found) could be checked by a typical modern computer today? here is a weak proposal, a very large integer discrete logarithm problem:
5^x = 2 (mod 2618163402417*2^1290001-1)
the modulus is the currently largest known safe prime, derived from the currently largest known Sophie Germain prime. the generator 5 was computed previously. the target 2 is the smallest nontrivial target. creating a more difficult problem of this type requires finding a larger safe prime.
checking a putative answer takes about 7 hours on a modern computer.
this problem has the additional nice feature that it is compact. (though slightly more compact is possible: the next largest factorial is 86268! .)
in general, we are almost certainly looking for a problem in complexity class NP: an answer can be checked in polynomial time. additionally, in contrast to typical complexity theory, we do care about details like the polynomial exponent and constant factor because they affect whether an answer can be checked in practice.
other possibilities:
RSA. although it would not be too difficult to compose a RSA-type factorization challenge larger than the integer discrete logarithm problem given above (previously, million-bit RSA, which is slightly smaller than the 1.3 million bit discrete logarithm problem above), this approach has the flaw that the solution is known to the problem-creator at the time of creation, so maybe the problem could be solved quickly by convincing the problem-creator to reveal the solution (rubber-hose cryptanalysis). (what if the problem creator did not look at the prime factors? does the falling tree make a sound? was 2^4253-1 ever the largest known Mersenne prime?)
instead of RSA, consider asking for the complete prime factorization of a large random number. the difficulty of verifying a prime factorization is not the multiplication but the primality testing. the currently largest known Mersenne prime, 2^82,589,933-1 ~= 2^2^26.3 , represents approximately the largest number we can currently practically test primality (with a probabilitic test). call this bound PRIMEMAX.
prime factorization of all numbers between (say) PRIMEMAX-100 and PRIMEMAX-1. there are almost certainly some numbers in that range whose factorizations are more difficult than the integer discrete logarithm puzzle given above. to check a putative solution, we may need to test primality of up to 100 numbers of size slightly smaller than PRIMEMAX: difficult but still doable.
in addition to factorization, the problem could also ask for RPPFN to require more work (how much more?) by the solver. with very bad luck (from the POV of the problem creator), all 100 numbers in a range might be easy to factor, but RPPFN will probably require some difficult factorizations further down its trees (actually lattice). but RPPFN also considerably increases the difficulty of primality-checking an answer (by how much?). although an RPPFN solution provides the outline of the all the necessary proofs of primality (via factorizations of p-1), checking them all will still be arduous.
it is curious that setting up a difficult integer discrete log problem requires quite a bit of work (finding a strong prime), but setting up a (probably) more difficult factorization problem requires simply picking some large random numbers.
another possibility is a very large elliptic curve discrete logarithm problem. i don't understand ECC well enough to select a strong curve, the ECC analogue of a safe prime. if SafeCurves is to be believed, neither do a lot of "experts" in the field.
Shor's algorithm solves all of the above problems quickly on a quantum computer.
another possibility is to scale up a cryptographic hash function to large output, probably also to large internal state, and ask for a preimage of the all-zeros hash. designing such large secure hash function still needs to be done, and doing cryptography right is hard. is there a way to guarantee that an answer exists?
prime constellations of arbitrary width are believed to exist (generalization of the Twin Prime Conjecture). using the first Hardy-Littlewood conjecture, pick a problem size whose answer can probably be checked with a typical computer. (see Chris K. Caldwell, An Amazing Prime Heuristic for more details.)
nothing proposed above is NP-complete. can we design such a problem? maybe a collection of random satisfiability problems. but some satisfiability problems do not have solutions.
mathematical formal proofs can (sometimes) be checked quickly, as can counterexamples (disproofs), usually. however, there exists the awkward area in between of statements which are true but cannot be proved (Goedel Incompleteness), so asking for a proof or disproof of a statement is a problem whose answer does not always exist. there are also statements whose shortest proof has been meta-proved be impractically large.
maybe graph minor theorem and polynomial-time recognizability.
No comments :
Post a Comment