@a_non_monotonic_function@lemmy.world
2026-09-25 22:30 UTC
We can actually make stronger claims about factoring. We know for certain do that it is not in NP hard, so you are correct there
And I’m not exactly a security expert, but moving away from RSA at this point makes sense. Early assumptions about the difficulty of factoring large semi-primes certainly hasn’t panned out (in particular in light of the growing risk of quantum computers.)
Replies (1)
-
@solrize@lemmy.ml 2026-09-26 03:23
We know for certain do that it is not in NP hard It’s likely to be NP-intermediate (outside of P, but not NP-hard), but it is not known. (@Kairos@lemmy.today) Factoring is at most NP-complete because we have a polynomial time verification for it. That means it’s in NP. These terms mean very precise things and it’s easy to get confused, but at the end of the day the new paper didn’t find a faster way to factor.