Quantum computers factored 15 in 2001 but haven't factored 21 yet, not due to lack of progress but because factoring 21 requires over 100 times more quantum gates than factoring 15. The factoring-15 circuit uses only 21 entangling gates while factoring-21 needs 2,405 gates. This massive difference stems from three key factors: factoring 15 benefits from many multiplications by 1 (which cost nothing), cheaper first multiplication implementation, and the ability to use simple circular shifts for modular multiplication. These advantages don't apply to factoring 21, making it exponentially more expensive and explaining why it remains unfactored despite quantum computing advances.
Sort: