126
There's a new way to break RSA that's faster than anything we've seen before (arstechnica.com)
submitted 1 month ago by to c/technology@lemmy.world
36 comments fedilink hide all child comments
you are viewing a single comment's thread
view the rest of the comments
[–] 1 point 1 month ago* (1 child)

Factoring is not in any category because we don't have a proof for it. As it stands, the algorithms we have require exponential time in the worst case, but solutions can be verified in polynomial time, which is NP-complete. I said "at most" for a reason.

Also, every algorithm is verifiable. If there's no better way to do it then re-running the algorithm and that algorithm is exponential, then it's NP-Hard.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 1 child comment
    •
  • [–] 1 point 1 month ago

    Factoring is in a category. Everything computable exists somewhere. We know factoring to be in NP.

    What I was disagreeing with was the "at least" and "at most" characterization of NP completeness. It is a set, not a boundary. The actual diagram of the complexity zoo is much more complicated than concentric circles.

    And for verifiability, I was not referring to it as an existential sort of thing. I was simply saying that I agreed with you in that particular facet, but it isn't sufficient to describe NP completeness. You also need NP-hardness.

  • permalink
  • fedilink
  • source
  • parent