A comprehensive implementation and exploration of Shor's groundbreaking quantum factorization algorithm
About • Features • Installation • Usage • Theory • Examples • Contributing
Shor's Algorithm, developed by Peter Shor in 1994, represents one of the most revolutionary breakthroughs in quantum computing. This algorithm demonstrates the exponential advantage quantum computers hold over classical computers for the integer factorization problem—a foundation of modern cryptography like RSA encryption.
This workshop provides:
- 📚 Complete theoretical foundation of modular arithmetic and period-finding
- 💻 Hands-on implementation in Python with detailed examples
- 🎯 Solved exercises demonstrating the algorithm's power
- 📊 Visual representations of modular exponentiation functions
- 🔬 Step-by-step breakdown of the quantum circuit approach
- ✅ Modular Arithmetic Fundamentals: Learn the mathematical foundations
- ✅ Period Finding Algorithm: Efficient recursive implementation
- ✅ Factor Extraction: Complete Euclidean GCD implementation
- ✅ Interactive Visualizations: matplotlib-based plotting of periodic functions
- ✅ Real-world Examples: Factor numbers like 15, 247, and 371
- ✅ Comprehensive Exercises: With detailed solutions and explanations
- ✅ Quantum Circuit Overview: Understanding the quantum advantage
- Python 3.8 or higher
- pip package manager
- Jupyter Notebook/Lab
-
Clone the repository
git clone https://github.com/AnderssonProgramming/shor-algorithm-py.git cd shor-algorithm-py -
Install dependencies
pip install -r Requirements.txt
-
Launch Jupyter Notebook
jupyter notebook Shors_Algorithm_Workshop.ipynb
Open Shors_Algorithm_Workshop.ipynb in Jupyter and execute cells sequentially. The notebook is structured as follows:
- Introduction - Historical context and significance
- Modular Arithmetic - Basic operations and congruence
- Modular Exponentiation - Computing powers efficiently
- Period Finding - The heart of Shor's algorithm
- Factor Extraction - Converting periods to factors
- Quantum Algorithm - Understanding the quantum circuit
- Exercises - Hands-on problems with complete solutions
N = 15
a = 2
# Compute and visualize the function f(x) = a^x mod N
computeAndDrawPowersAModuloN(a, N)N = 247
a = 2
# Find the period
period = findPeriod(a, N)
# Extract factors using GCD
factor1 = gcd((a ** (period // 2)) + 1, N)
factor2 = gcd((a ** (period // 2)) - 1, N)
print(f"Factors of {N}: {factor1} and {factor2}")Shor's algorithm exploits the periodic nature of modular exponentiation:
Given: An integer N to factor and a coprime integer a < N
Find: The period r such that a^r ≡ 1 (mod N)
Extract Factors:
- If r is even and a^(r/2) ≢ -1 (mod N), then:
- Factor₁ = GCD(a^(r/2) + 1, N)
- Factor₂ = GCD(a^(r/2) - 1, N)
Classical algorithms require exponential time to find the period. Shor's quantum algorithm uses:
- Quantum Fourier Transform (QFT) - Finds periodicity in superposition
- Quantum parallelism - Evaluates function for multiple inputs simultaneously
- Interference - Amplifies periodic patterns
Time Complexity:
- Classical: O(exp(∛(log N)))
- Quantum: O((log N)² (log log N) (log log log N))
N = 15, a = 2
Period r = 4
Factors: GCD(2² + 1, 15) = 5 and GCD(2² - 1, 15) = 3
Result: 15 = 3 × 5 ✓N = 247, a = 2
Period r = 30
Factors: GCD(2¹⁵ + 1, 247) = 13 and GCD(2¹⁵ - 1, 247) = 19
Result: 247 = 13 × 19 ✓N = 371, a = 24
Period r = 39
Factors: GCD(24^(39/2) + 1, 371) = 7 and GCD(24^(39/2) - 1, 371) = 53
Result: 371 = 7 × 53 ✓The notebook includes solved exercises:
- Prove: 1977 ≡ 1 (mod 247)
- Prove: 16183 ≡ 15442 (mod 247)
Solution provided with both direct computation and divisibility proof methods.
- Factor N = 247 using a = 2
- Step-by-step implementation with visualization
Solution includes:
- GCD verification
- Period computation
- Evenness check
- Factor extraction
- Visual plot of the periodic function
| Concept | Description |
|---|---|
| Modular Arithmetic | Remainder operations and congruence relations |
| GCD Algorithm | Euclidean method for finding greatest common divisors |
| Period Finding | Detecting cycles in modular exponentiation |
| Coprimality | Numbers with no common factors except 1 |
| Quantum Superposition | Evaluating multiple inputs simultaneously |
| Quantum Fourier Transform | Extracting periodicity from quantum states |
- Yanofsky & Mannucci - Quantum Computing for Computer Scientists
- Nielsen & Chuang - Quantum Computation and Quantum Information
- Kaye, Laflamme & Mosca - An Introduction to Quantum Computing
- Qiskit Documentation - IBM's quantum computing framework
- Python - Core implementation language
- NumPy - Numerical computations
- Matplotlib - Data visualization
- Jupyter - Interactive computing environment
Contributions are welcome! Here's how you can help:
- Fork the repository
- Create a feature branch (
git checkout -b feature/AmazingFeature) - Commit your changes (
git commit -m 'Add some AmazingFeature') - Push to the branch (
git push origin feature/AmazingFeature) - Open a Pull Request
- Implement quantum circuit simulation using Qiskit
- Add more complex factorization examples
- Optimize the period-finding algorithm
- Create interactive visualizations with Plotly
- Add unit tests for all functions
This project is licensed under the MIT License - see the LICENSE file for details.
AnderssonProgramming
- GitHub: @AnderssonProgramming
- Repository: shor-algorithm-py
- Peter Shor for the revolutionary algorithm
- The quantum computing community for continued research
- Open-source contributors to Python scientific libraries
- ESCUELA COLOMBIANA DE INGENIERIA JULIO GARAVITO - CNYT Course
⭐ If you found this workshop helpful, please consider giving it a star! ⭐
Made with ❤️ and quantum superposition