11+ stellige Ints funktioniert nicht

Question

Ich benutze Python 3 für eine kleine zusätzliche Kreditvergabe, um einen RSA-Cracker zu schreiben. Der Lehrer hat uns einen ziemlich großen (groß genug, um mehr als 32 Bits zu erfordern) int und den öffentlichen Schlüssel gegeben. Mein Code funktioniert für Primzahlen < 32 Bits. Einer der Gründe, warum ich Python 3 gewählt habe, ist, weil ich gehört habe, dass es beliebig große Ganzzahlen verarbeiten kann. Im Python-Terminal teste ich das mit kleinen Dingen wie 2 ** 35 und faktoriell (70). Dieses Zeug hat gut funktioniert.

Jetzt, da ich den Code geschrieben habe, laufe ich auf Probleme mit Überlauffehlern usw. Warum scheinen Operationen auf großen Zahlen im Terminal zu funktionieren, aber funktioniert nicht in meinem tatsächlichen Code? Die Fehler geben an, dass sie nicht in ihre C-Typen konvertiert werden können. Daher wäre meine erste Vermutung, dass aus irgendeinem Grund das Zeug im Python-Interpreter nicht in C-Typen konvertiert wird, während das codierte Zeug ist. Gibt es das überhaupt, um das funktionieren zu lassen?

Als ersten Versuch habe ich versucht, eine Liste aller Primzahlen zwischen 1 und n (die große Zahl) zu berechnen. Diese Art von funktioniert, bis ich erkannte, dass die Liste Indexer [] nur akzeptieren und explodieren, wenn die Zahl höher als int ist. Außerdem wird das Erstellen eines Arrays mit der Länge n nicht funktionieren, wenn n> 2 ** 32 ist. (Ganz zu schweigen von dem Speicher, den das aufnehmen würde)

Aus diesem Grund wechselte ich zu einer Funktion, die ich fand, die eine sehr genaue Schätzung geben konnte, ob eine Zahl prim war oder nicht. Diese Methoden werden unten eingefügt.

Wie Sie sehen können, mache ich nur , *, /, und% Operationen. All diese scheinen im Interpreter zu funktionieren, aber ich bekomme "kann nicht in c-type" Fehler konvertieren, wenn sie mit diesem Code verwendet werden.

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 

Diese letzten drei Zeilen sind, wo die nicht zu c-Typ erscheint umwandeln kann.

Die folgende Funktion schätzt mit einem sehr hohen Grad der Sicherheit, dass eine Zahl prim ist. Wie oben erwähnt, habe ich dies verwendet, um zu vermeiden, dass massive Arrays erzeugt werden.

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 

Vielleicht sollte ich genauer sein, indem der Fehler einfügen: Leitung 19, in power_mod return (a * power_mod (a, b-1, n))% n OverflowError: Python int zu groß umwandeln in C doppelt

Dies ist die Art von Fehler, die ich beim Ausführen von Arithmetik bekomme. Int-Fehler treten beim Versuch auf, unglaublich große Listen, Mengen usw. zu erstellen.

Answer 1

Ihr Problem (glaube ich) ist, dass Sie mit dem Operator/in Floating Point konvertieren. Ändern Sie es in // und Sie sollten in der int-Domäne bleiben.

Answer 2

Viele C-Routinen haben immer noch C int Einschränkungen. Führen Sie Ihre Arbeit stattdessen mit Python-Routinen aus.