5 ms·
It's worst-case exponential, sure, but it's hard to find that worst-case. It's not that hard. Just generate a boolean circuit for the multiplication of 2 64 b
by tgflynn 10y ago
It's worst-case exponential, sure, but it's hard to find that worst-case.
It's not that hard. Just generate a boolean circuit for the multiplication of 2 64 bit prime numbers and convert the circuit to a 3-SAT formula. I doubt any current SAT solver can solve that problem. If you could do it for 1024 bit primes a lot of cryptography would be toast.
EDIT: To be a bit more clear I mean that the circuit takes two n-bit numbers, multiplies them then compares the result to some known product of 2 primes. So by solving this circuit you factor the known integer.
EDIT2: Doesn't solving MaxSAT exactly imply that you can also solve SAT ? If there's a SAT solver that can handle million variable instances "easily" that's something I'd be really interested in hearing more about.
- mortehu 10y agoThe satisfiability problem doesn't require that you provide the solution, only that you determine whether or not a solution exists. So you'd end up with a primality check, which is known to be in P: https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test
- tgflynn 10y agoIt's not a primality test. A primality test determines whether or not a single given integer is prime. The circuit I described checks that the product of two arbitrary input integers is a specific known integer. By solving the decision problem for each bit independently you can determine all bits of the 2 input integers and hence factor the known target.
- mortehu 10y agoNeat. I wasn't aware of the trick of peeling off a bit at a time.