While computer scientists might expect slightly faster factoring algorithms to exist than the ones we know of - perhaps exp((# bits)^0.25) is plausible - I thin

While computer scientists might expect slightly faster factoring algorithms to exist than the ones we know of - perhaps exp((# bits)^0.25) is plausible - I think the majority of computer scientists, including Aaronson, would be completely shocked if it was possible to factor integers in polynomial time. Factoring isn't a problem like testing primality, or graph isomorphism, where we had algorithms that worked well in practice but not perfectly theoretically for many years before the major breakthroughs. While it wouldn't be quite as mind-boggling to find a fast factoring algorithm as it would be to efficiently solve SAT - factoring almost certainly isn't NP-complete - it definitely seems to fit somewhere into the "hard" side of things from the standpoint of classical complexity. One way to think of it is this: when problems can be solved efficiently, there is generally some sort of nice algebraic structure that makes them easy. Nice, exploitable algebraic structure is extremely rare: if you haven't found hints of it after putting in a fair amount of effort, it probably isn't there at all. Of course, we can't currently rule out the possibility that there are secret ghostly algebraic structures that will render everything easy lurking just beyond our current knowledge, but intuition from studying our best known algorithms and our complete lack of progress on truly hard problems indicates that this isn't the case.