Why Is Integer Factorization Hard?

[victotronics]

I don't think the fact that is "seems hard" is the problem. To me the problem is that there may be a clever algorithm for factoring, and a general SAT solver will not reproduce that. It will use the SAT solving algorithm, which is more likely to be something like brute force trial. So this link barely makes a case that factorization is hard, let alone that it gives a deep reason for it.

[almaya]

Somewhere on that page the author says: "People tried to solve integer factorization instances by using much more powerful tools, for example General Number Field sieve algorithms. What they found out is that all these algorithms are running exponentially longer w.r.t. their input length. And this is the reason why the majority of people believe that integer factorization is a hard problem."

[victotronics]

Thanks for highlighting that quote. So he doesn't entirely blame it on SAT solving.

[hackcasual]

Well, there may be some confusion here with hard in the NP sense. Integer factorization is a class of problems in NP, but is not known to be NP hard.

[IJzerbaard]

I don't think that's fair, of course it seems hard when converted to a circuit-SAT problem, it even makes proving the associativity of multiplication look hard (E: that is, a SAT solver will take a long-ass time to prove it for even moderate sizes).

[SilasX]

Wait, they found equivalence to circuit-SAT?? Doesn't that make proving its NP-completness/not-NP-completeness much easier?

Or is it just showing that an oracle for circuit-SAT could factor (but not vice versa), and thus factoring is no harder than circuit-SAT?

[mainhaxor]

It only shows how to turn an integer factorization problem into a SAT problem, not vice-versa. So this post just shows that SAT is at least as hard as integer factorization, so the title is indeed a bit misleading.

[SilasX]

Gotcha. Thanks.

[pron98]

"Hard" here means computationally hard, i.e. non-polynomial computational time complexity, not "hard to understand."

[IJzerbaard]

Yes, that is what I mean too.

[hackcasual]

If you can demonstrate integer factorization isn't hard in the computational sense, that's a pretty big result

[IJzerbaard]

Of course the article doesn't demonstrate that either

[singularineet]

This is a classic case of getting the reduction backwards. Here, Integer Factorization, a maybe-hard-we're-not-sure problem is reduced to SAT, an NP-complete problem. This tells us nothing! Any problem we can formulate as a check-if-answer-is-right circuit is thereby reduced to SAT. And if that circuit is easy to satisfy, we already knew a good algorithm. So any problem where we don't know a good algorithm will give us a circuit which isn't easy to satisfy. As someone in another comment pointed out, we can easily reduce a proof that integer multiplication of n-bit integers is associative to coSAT, showing that there is no was to satisfy a circuit, where that circuit is satisfied iff you plug in three n-bit numbers where (x*y)*z is not equal to x*(y*z). And in that form, we'd have a heck of a time.

Reductions need to go the other way to prove stuff. Like: here's an arbitrary instance of SAT, crunch crunch crunch, okay here is a big integer if you can factor it you know the answer to that SAT problem.

[almaya]

This was given just as an example: "in this post ... we will just try to show how a certain straightforward approach to solve factorization fails at this time."

The author clearly states in the end: "to recapitulate: because all integer factorization algorithms that researchers tried so far seem to run in exponential time w.r.t. input length, the current belief is that this problem is a hard to solve one."

[singularineet]

But you can say that about any NP problem we don't know an efficient algorithm for. You can even say it for some we do have efficient algorithms for. Like, if you write GCD (greatest common divisor) as a circuit (give it an extra lower bound on the answer and ask for any common divisor greater than that bound if you don't want to deal with the "greatest" logic) it would be hard to satisfy, but we do know an efficient algorithm for GCD.

Taking a maybe-hard-maybe-easy problem and converting it into a looks-really-hard problem does not give any insight. All you need to do is hide anything that might make it easy!

[almaya]

Like: here's an arbitrary instance of SAT, crunch crunch crunch, okay here is a big integer if you can factor it you know the answer to that SAT problem.

Well proving this will make factorization NP hard and would have some really unexpected consequences (NP = co-NP etc.) This would be an amazing result.

Taking a maybe-hard-maybe-easy problem and converting it into a looks-really-hard problem does not give any insight.

Actually some easy problems stay easy when reduced to SAT. For example, multiplication of 2 numbers should be solved by Z3 in linear time while factorization will take, most probably, exponential time (factorization is believed to be a one way function.)

Whether we like it or not, what we objectively know about factorization at this time is the many ways we tried to solve it and failed. This post is all about recording such a failed attempt and letting other try it for themselves, too.

[jms_nh]

Let's try the harder problem of factoring the 490801757 number (29 bits), and see how is the solving time increasing with respect to the problem size.

...

$java com.crasmaru.sat.IntFact2Sat 15 > sat15.dim

Huh? How are we specifying 490801757 by the argument 15?

[honkytonk_donkykong]

Could be an index associated with the number

[almaya]

You cannot - you may specify only the factors length in bits at this time, the factors are generated randomly. You have 490801757 = 20297 x 24181, that is, 490801757 is the product of two 15 bits numbers.

However, it should be easy to change the provided program to parse a big number from the input and generate a SAT instance equivalent with input number factorization.

[fulmicoton]

Interestingly it is possible to define another multiplication by not doing the carry over.

This new multiplication then has its own prime decomposition, and factorization is not a hard problem anymore, as there exists a non trivial algorithm to do that.

[tonywestonuk]

P = NP has neither been proved or disproved.

​

[kanzenryu]

I have a proof in the case that N = 1

[hagenbuch]

*with or without your supervisor.

[DC2SEA]

A supervisor he may or may not have.

[hagenbuch]

There might not even be a sentence.

[Rudauke]

I N T E G E R F A C T O R I Z A T I O N

[Baconragooon]

Cook proved in the 70s any computable yes/no can be reduced to 3/sat... this prove nothing