⚛️ Quantum Implementation of Elliptic Curve Cryptography (ECC) and Shor’s Algorithm

This repository implements Elliptic Curve Cryptography (ECC) over finite fields and extends it to a quantum circuit realization of Shor’s algorithm for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP).
The project demonstrates how classical ECC group operations can be lifted to quantum unitaries, enabling quantum attacks on elliptic-curve-based cryptosystems.

---

📁 Project Structure

File	Description
elliptic_curve.py	Core ECC implementation: finite-field arithmetic, modular inversion, point addition, scalar multiplication, and subgroup generation.
linked_list.py	Linked-list data structure to represent cyclic subgroups, enabling orbit traversal and graph visualization.
working_example.ipynb	Full demonstration notebook combining ECC construction, subgroup visualization, and quantum circuit construction for Shor’s ECDLP algorithm.
requirements.txt	All Python dependencies needed for the project.

---

⚙️ Installation

1. Clone the repository

git clone https://github.com/Mihauk/ECC.git
cd ECC

2. Create and activate a virtual environment

python -m venv .venv
source .venv/bin/activate    # macOS/Linux
.venv\Scripts\activate       # Windows

3. Install all dependencies

pip install -r requirements.txt

---

▶️ Running the Project

Option 1 — Jupyter Notebook

jupyter notebook

Open working_example.ipynb and run all cells.
You’ll see:

• Point generation on elliptic curves over 𝔽_p
• Subgroup graph visualization using networkx
• Quantum circuit construction for $f(a,b) = aP + bQ$
• QFT-based period finding to extract discrete logs

Option 2 — Use as Python Modules

from elliptic_curve import EllipticCurve
from linked_list import LinkedList

curve = EllipticCurve(a=0, b=7, p=13)
P = (11, 5)
Q = curve.point_add(P, P)
print("2P =", Q)

---

⚛️ Quantum Shor’s Algorithm for ECDLP

After defining an ECC instance $\mathbb{E}: y^2 = x^3 + ax + b$ over $\mathbb{F}_p$ , the quantum version constructs a unitary for
$f(a,b) = aP + bQ$ that encodes the ECDLP instance $Q = kP$.

Example:

from elliptic_curve import EllipticCurve
from utils import build_shor_ecdlp_circuit  # defined in your utils folder

curve = EllipticCurve(a=0, b=7, p=13)
P = (11, 5)
Q = curve.scalar_mult(5, P)  # Q = [5]P

qc = curve.shor_ecdlp_circuit_full_parallel(P, Q)

qc.draw('mpl')

The circuit includes:

• Superposition registers for exponents $(a, b)$
• Controlled modular additions for ECC group law
• Inverse Quantum Fourier Transform for period extraction
• Classical post-processing using continued fractions

---

🧩 Dependencies

Installed via requirements.txt:

numpy
matplotlib
networkx
pandas
qiskit
qiskit-aer
qiskit-ibm-runtime
tqdm
ipython

---

🧪 Visualization Example

Visualize the subgroup generated by point $P$:

from elliptic_curve import draw_ecc_subgroup_graph
draw_ecc_subgroup_graph(curve, P)

Displays a directed cyclic graph for the subgroup generated by point $P \mapsto 2P \mapsto 3P \mapsto \cdots rP$ where r is the order of the subgroup using matplotlib and networkx.

---

🌌 Quick Results Preview

Output	Description
	Elliptic curve points for curve $y^2 = x^3 + 7 \mod 13 $.
	Cyclic subgroup generated by $P = (11,5)$.
	Shor’s ECDLP circuit, including controlled point-addition and inverse QFT layers.
	Simulated measurement outcomes after QFT and period extraction (using Qiskit Aer backend).

---

🧠 Research Context

This repository is part of a larger research project:

“Quantum Circuit Construction and Implementation of Shor’s Algorithm for Breaking Elliptic Curve Cryptography on Hardware.”

It demonstrates how structured, permutation-based unitaries can replace dense matrices to achieve scalable, hardware-feasible quantum implementations.

---

🚀 Future Work

• Implement fully reversible modular arithmetic and inversion circuits
• Optimize controlled-addition unitaries for multi-qubit registers
• Test execution on IBM Quantum hardware via qiskit-ibm-runtime
• Benchmark scaling with ECC parameters $p$ and subgroup order $r$

---

🧾 Citation

If you use this repository in research or teaching, please cite:

A. Raj, "Quantum Circuit Implementation of Shor’s Algorithm for Elliptic Curve Cryptography", 2025. GitHub: Mihauk/ECC