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