I've just been reading up on Shor's algorithm, and I find it both fascinating and baffling. I don't understand much about it, other than that it can factor semiprimes in polynomial time.
Could someone explain how it works in layman's terms and why it is reliant on quantum computing?
Keep in mind that while I understand quantum computing basics (i.e., it uses photons instead of electrons, and bits are replaced with qubits that can be 0, 1, or a superposition of both), I don't know anything in-depth about it. I know it's supposedly super-fast compared to classical computing mechanisms.