Implementación

A continuación se muestra una implementación simplificada del algoritmo de Shor en Python. Esta implementación es para fines educativos y simula los aspectos cuánticos del algoritmo.

import math
import random
import numpy as np

def gcd(a, b):
    """Calcula el máximo común divisor de a y b."""
    while b:
        a, b = b, a % b
    return a

def find_period(a, N):
    """
    Simula la parte cuántica del algoritmo de Shor para encontrar
    el período de f(x) = a^x mod N.
    
    En un ordenador cuántico real, esto utilizaría la transformada
    cuántica de Fourier para encontrar el período eficientemente.
    """
    # En esta simulación, calculamos el período directamente
    x = 1
    for r in range(1, N):
        x = (x * a) % N
        if x == 1:
            return r
    return None

def shor_algorithm(N):
    """
    Implementación simplificada del algoritmo de Shor para factorizar N.
    """
    # Paso 1: Verificar si N es par
    if N % 2 == 0:
        return 2, N // 2
    
    # Paso 2: Verificar si N es una potencia perfecta
    k = 2
    while k**2 <= N:
        if int(N**(1/k)) ** k == N:
            return int(N**(1/k)), k
        k += 1
    
    # Paso 3: Elegir un número aleatorio a < N
    for _ in range(5):  # Intentar varias veces
        a = random.randint(2, N-1)
        
        # Verificar que a y N son coprimos
        if gcd(a, N) > 1:
            return gcd(a, N), N // gcd(a, N)
        
        # Paso 4: Encontrar el período de a^x mod N
        r = find_period(a, N)
        
        if r is None or r % 2 != 0:
            continue  # Intentar con otro valor de a
        
        # Paso 5: Calcular a^(r/2) mod N
        x = pow(a, r // 2, N)
        
        if x == N - 1:
            continue  # Intentar con otro valor de a
        
        # Paso 6: Calcular los factores
        factor1 = gcd(x - 1, N)
        factor2 = gcd(x + 1, N)
        
        if factor1 > 1 and factor1 < N:
            return factor1, N // factor1
        if factor2 > 1 and factor2 < N:
            return factor2, N // factor2
    
    # Si no se encontraron factores después de varios intentos
    return None, None

# Ejemplo de uso
N = 15
factor1, factor2 = shor_algorithm(N)
print(f"Factores de {N}: {factor1} × {factor2}")

Esta implementación es una simulación clásica del algoritmo de Shor. En un ordenador cuántico real, la búsqueda del período se realizaría utilizando registros cuánticos y la transformada cuántica de Fourier, lo que proporcionaría la aceleración exponencial.