> Classical models can only simulate superposition with an exponential amount of information to model each possibility of a sequence of qbits.
This is not true at all when the qubits are only in superposition - not in entanglement. The state of n unentangled qubits is just 2n numbers, compared to the 2^n numbers required to describe an arbitrary entangled state of n qubits. To simulate 2n real numbers, you can encode them in the (amplitude,phase) of n electric fields etc.
Shor's algorithm works because it uses entanglement - as does every quantum algorithm that shows a speedup.
Let me try in a different way. If you don't know whether you are living in a universe whose laws are classical-non-deterministic or quantum, you do a Bell experiment. To to do a Bell experiment in the quantum world you need entangled states - mere superposed states won't do. If you have superposed states, you won't be able to tell the difference between classical and quantum.
To put it yet another way. You design any quantum experiment which may use superposed states, but not entangled states. I will look at your design and design a corresponding classical non-deterministic experiment. Then we will go to our trusted friend Charlie and ask him to run the two experiments for us, and then return the datasets for the two experiments, without telling us which is which. I assure you, there is no algorithm that will allow you to look at the experimental datasets and tell which was from the classical experiment and which from the quantum one.