3 ms·
If you would have looked at two more Wikipedia articles you would have known the following: Integer factorization is likely not an NP-complete problem at all.
by DCKing 12y ago
If you would have looked at two more Wikipedia articles you would have known the following:
Integer factorization is likely not an NP-complete problem at all. It is suspected (but not proven) not to be in the class of NP-complete problems. There is no reason to believe that an NP-complete problem solver can factorize integers in polynomial time.
Contrary to this machine it has been shown that quantum computers can solve the integer factorization problem in polynomial time through Shor's algorithm. But quantum computers are not known to be able to solve NP-complete problems in polynomial time.
Even quantum computers are far off factoring the RSA numbers because of the practicalities of the real world. The current world record Shor's algorithm computation is finding that 15 = 3 x 5.
- teraflop 12y ago> There is no reason to believe that an NP-complete problem solver can factorize integers in polynomial time. You're misunderstanding the relationship between NP and NP-complete. Integer factorization is in NP, which by definition means that anything that can solve NP-complete problems efficiently can also solve factorization. The question that's currently unresolved is whether factorization is easier than NP-complete, not harder.
- DCKing 12y agoAh, my apologies. It's been some time since my courses on this.
- deleted 12y ago[deleted]
- tux3 12y ago>Even quantum computers are far off factoring the RSA numbers because of the practicalities of the real world. The current world record Shor's algorithm computation is finding that 15 = 3 x 5. I happen to have read the Wikipedia page on Shor's algorithm not an hour ago, and apparently they factored 143 without Shor two years ago. We're not quite there just yet, but 143 is getting a bit less laughable than 3x5.
- DCKing 12y agoThe practical record for Shor's algorithm is definitely 3x5 = 15. A different style of quantum computer factorized 143 using another method, which seems to have also have theoretical complications in addition to practical ones. It is definitely possible to factor some larger numbers than using "just Shor" but from what I understand, these methods are just "hacks" in the sense that they are not a good way to factorize in the general case. Maybe someone can correct me on this.