Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Ehhhhhhh. I'm not sure I'm aware of anything in number theory that would substantially change if a fast factoring algorithm were discovered, outside of its applications to cryptography. It'd be very likely that a fast factoring algorithm exposed some unusual structure about the natural numbers, I guess?


I was exaggerating for effect, but yeah. The existence of a polynomial time prime factoring suggests the existence of a useful predictive pattern in the distribution of primes. That would break the Twin Prime Conjecture and possibly refute Riemann. Undermining those starts tearing the foundations apart. I’m almost certain that won’t have just happened.


We already know there is plenty of structure in the distribution of primes, so I don't see why finding some that can be exploited by a clever algorithm makes that much of a difference to foundational concerns. In fact, I'm pretty sure that even a proof of P=NP, which obviously subsumes fast factoring, wouldn't have any intrinsically interesting non-algorithmic consequences for proofs in number theory that don't directly assume factoring is hard (but this could just be ignorance on my part); all the supposedly absurd consequences people point to like the PH collapsing are more or less restricted to computer science.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: