Classical Implementation & Testing of Shor’s Algorithm (#12318)

[adityakrmishra]

Hi everyone!

I have worked on implementing and testing a classical simulation of Shor’s Algorithm without using quantum computing libraries like Qiskit or Cirq. The goal is to demonstrate how Shor’s Algorithm factors composite numbers in a classical setting.

✅ Implementation Highlights:

• Uses modular exponentiation and order-finding to determine factors.
• Checks for trivial factors before proceeding with the order-finding method.
• Returns valid non-trivial factors of N.

✅ Added Tests:

• Unit tests cover multiple values of N (e.g., 15, 21, 35, 55).
• Ensures correctness using pytest.

💡 Discussion Points:

• Are there ways to optimize the order-finding process?
• Should we add support for larger numbers?
• Any edge cases we should test?

📌 You can find the PR here: PR #12545
Let me know your thoughts and feedback! 🚀

Thanks!

[Ganesh-403]

@adityakrmishra Nice work! Implementing a classical simulation without relying on Qiskit or Cirq makes the algorithm much more educational and easier to understand.

A few suggestions that may strengthen the implementation:

1. Additional edge cases

   • Prime inputs (e.g. 13, 17) should return that no non-trivial factors exist.
   • Prime powers such as 9, 25, and 49.
   • Even composites (e.g. 14, 22) where trivial factors can be detected immediately.
   • Very small values like 1, 2, 3, and 4.

2. Order-finding performance
   Since the classical simulation computes the order by repeated modular exponentiation, that step quickly becomes the bottleneck for larger values of N. It would be interesting to benchmark how runtime grows as N increases and document the practical limits of the implementation.

3. Testing
   Besides checking that the returned factors multiply back to N, I'd also verify that:

   • Both factors are non-trivial.
   • Each factor divides N.
   • Multiple valid factorizations (when applicable) are accepted.

Overall, I think this would make a valuable educational implementation, especially with some documentation explaining which parts are classically simulated versus which parts would normally rely on quantum computation.

If this solves your problem, feel free to mark it as the accepted answer so others can find it easily.