Implementing Shor's Algorithm: Breaking RSA Encryption

def shors_algorithm(N):
    """
    Factor N = p × q

    Classical: O(exp(n^1/3)) - exponential
    Quantum: O(n^3) - polynomial

    For RSA-2048: Classical = billions of years, Quantum = hours
    """
    # 1. Choose random a < N
    a = random.randint(2, N-1)

    # 2. Quantum period finding (the magic step)
    r = quantum_period_finding(a, N)  # Needs quantum computer!

    # 3. Classical post-processing
    if r % 2 == 0:
        p = gcd(a^(r/2) - 1, N)
        q = N // p
        return p, q
    else:
        return shors_algorithm(N)  # Retry

def quantum_period_finding(a, N):
    """The quantum subroutine - requires quantum computer."""
    # Create superposition
    qc = QuantumCircuit(n_qubits)
    qc.h(range(n_qubits))

    # Modular exponentiation (a^x mod N)
    qc.append(modular_exp_gate(a, N), range(n_qubits))

    # Quantum Fourier Transform
    qc.append(qft(n_qubits), range(n_qubits))

    # Measure to get period
    qc.measure_all()
    return extract_period(execute(qc).result())

def estimate_shors_resources(rsa_bits):
    """
    Estimate quantum resources to break RSA.

    RSA-2048: ~4000 logical qubits, 10^12 gates
    With surface codes (distance=7): ~200,000 physical qubits
    """
    logical_qubits = 2 * rsa_bits
    gates = rsa_bits ** 3
    physical_qubits = logical_qubits * 49  # Distance-7 surface code

    return {
        'logical_qubits': logical_qubits,
        'gates': gates,
        'physical_qubits': physical_qubits,
        'runtime_hours': gates / (10**9),  # 1 GHz gate speed
    }

print(estimate_shors_resources(2048))
# {'logical_qubits': 4096, 'physical_qubits': 200704, 'runtime_hours': 8.6}