Shoring up your knowledge
Understanding Shor’s algorithm can be difficult because examples with manageable-size numbers are hard to find. For instance, a minimal circuit that factors 15 with 11 as its coprime may involve five qubits. Wielding five qubits at once means multiplying 32 × 32 matrices by one another. Each matrix contains 1024 complex numbers. That’s too many numbers for one example in a book.
You can overcome the conceptual difficulties using summations and linear algebra, and I encourage you to study more about these approaches. In the meantime, this section describes some aspects of Shor’s algorithm that previous sections glossed over.
At some future date, when we have quantum computers that can crack real RSA encryption problems, those computers will probably have thousands of qubits. Alice will start with a public key, n, that has 2048 bits. To attack that key with Shor’s algorithm, Eve’s circuit will implement an N ×...
