11+ dígitos no funciona

Question

Estoy usando python 3 para una pequeña asignación de crédito adicional para escribir un cracker RSA. El profesor nos ha dado una clave int bastante grande (lo suficientemente grande como para requerir más de 32 bits) y pública. Mi código funciona para primos < 32 bits. Una de las razones por las que elegí Python 3 es porque escuché que puede manejar enteros arbitrariamente grandes. En la terminal de Python probé esto haciendo cosas pequeñas como 2 ** 35 y factorial (70). Esto funcionó bien.

Ahora que he escrito el código, estoy incurriendo en problemas con los errores de desbordamiento, etc. ¿Por qué las operaciones en números grandes parecen funcionar en el terminal pero no funcionan en mi código actual? Los errores indican que no se pueden convertir a sus tipos C, así que mi primera conjetura sería que, por alguna razón, las cosas en el intérprete python no están siendo convertidas en C, mientras que las cosas codificadas sí lo están. ¿Hay alguna forma de que esto funcione?

Como primer intento, traté de calcular una lista de todas las primos entre 1 y n (el número grande). Este tipo de trabajo funcionó hasta que me di cuenta de que los indexadores de lista [] solo aceptan enteros y explotan si el número es más alto que int. Además, la creación de una matriz con n de longitud no funcionará si n> 2 ** 32. (por no mencionar la memoria que tomaría esto)

Debido a esto, cambié a usar una función que encontré que podría dar una conjetura muy precisa sobre si un número era primo o no. Estos métodos están pegados a continuación.

Como puede ver, solo estoy haciendo , *, /, y% operaciones. Todos estos parecen funcionar en el intérprete, pero obtengo errores de "no se puede convertir en tipo c" cuando se utilizan con este código.

def power_mod(a,b,n): 
if b < 0: 
    return 0 
elif b == 0: 
    return 1 
elif b % 2 == 0: 
    return power_mod(a*a, b/2, n) % n 
else: 
    return (a * power_mod(a,b-1,n)) % n 

Esas últimas 3 líneas aparecen donde no se puede convertir a tipo c.

La siguiente función estima con un alto grado de certeza que un número es primo. Como mencioné anteriormente, utilicé esto para evitar la creación de matrices masivas.

def rabin_miller(n, tries = 7): 
if n == 2: 
    return True 

if n % 2 == 0 or n < 2: 
    return False 

p = primes(tries**2) 

if n in p: 
    return True 

s = n - 1 
r = 0 
while s % 2 == 0: 
    r = r+1 
    s = s/2 
for i in range(tries): 
    a = p[i] 

    if power_mod(a,s,n) == 1: 
     continue 
    else: 
     for j in range(0,r): 
      if power_mod(a, (2**j)*s, n) == n - 1: 
       break 
     else: 
      return False 
     continue 
return True 

tal vez debería ser más específico pegando el error: línea 19, en power_mod retorno (un power_mod * (a, b-1, n))% n OverflowError: Python int demasiado grande para convertir a C doble

Este es el tipo de error que obtengo cuando realizo la aritmética. Se producen errores de tipo Int al intentar crear listas increíblemente grandes, conjuntos, etc.

Answer 1

Tu problema (creo) es que estás convirtiendo a punto flotante usando el operador /. Cámbielo a // y debe permanecer en el dominio int.

Answer 2

Muchas rutinas C aún tienen limitaciones de C int. Haz tu trabajo usando rutinas de Python en su lugar.