Wie können Computer Exponentialrechnungen ohne Überlauffehler berechnen?

Bei der Untersuchung einiger RSA-Verschlüsselungs- / Entschlüsselungsmethoden habe ich folgenden Artikel gefunden: Ein Beispiel für den RSA-Algorithmus

Dies ist erforderlich, um diese Nachricht zu entschlüsseln

Das Gesamtergebnis von ist so groß, dass es für eine 64-Bit / 32-Bit-Maschine meines Erachtens keinen so großen Wert in einem Register enthalten kann. Wie schafft es der Computer ohne Überlauf?

Diese Frage war eine Super User Frage der Woche .
Lesen Sie den Blog - Eintrag , um weitere Informationen oder tragen zu dem Blog selbst

Da die Ganzzahlmoduloperation ein Ringhomomorphismus ( Wikipedia ) von ℤ -> ℤ / nℤ ist,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

Sie können dies selbst mit ein wenig einfacher Algebra überprüfen. (Beachten Sie, dass das Finale modauf der rechten Seite aufgrund der Definition der Multiplikation in einem modularen Ring angezeigt wird.)

Computer verwenden diesen Trick, um Exponentiale in modularen Ringen zu berechnen, ohne eine große Anzahl von Ziffern berechnen zu müssen.

               / 1 I = 0,
               |
(X ^ I) mod N = <(X * (X ^ (I-1) mod N)) mod NI ungerade,
               |
               \ (X ^ (I / 2) mod N) ^ 2 mod NI gerade & I / = 0.

In algorithmischer Form

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

Sie können dies verwenden, um (855^2753) mod 3233mit nur 16-Bit-Registern zu rechnen , wenn Sie möchten.

Die Werte von X und N in RSA sind jedoch viel größer, zu groß, um in ein Register zu passen. Ein Modul ist typischerweise 1024-4096 Bits lang! Sie können also von einem Computer die Multiplikation auf die "lange" Strecke ausführen lassen, genauso wie wir die Multiplikation von Hand ausführen. Nur anstelle der Ziffern 0-9 verwendet der Computer "Wörter" 0-2 ¹⁶ -1 oder ähnliches. (Mit nur 16 Bit können wir zwei 16-Bit-Zahlen multiplizieren und das vollständige 32-Bit-Ergebnis erhalten, ohne auf die Assemblersprache zurückgreifen zu müssen. In der Assemblersprache ist es normalerweise sehr einfach, das vollständige 64-Bit-Ergebnis zu erhalten, oder für einen 64-Bit-Computer , das vollständige 128-Bit-Ergebnis.)

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

Dies multipliziert X mit Y in einer Zeitspanne, die ungefähr der Anzahl der Wörter in X multipliziert mit der Anzahl der Wörter in Y entspricht. Dies wird als O (N ² ) -Zeit bezeichnet. Wenn Sie sich den obigen Algorithmus anschauen und auseinander nehmen, ist es die gleiche "lange Multiplikation", die sie in der Schule unterrichten. Sie haben keine auf 10 Stellen gespeicherten Zeittabellen, aber Sie können dennoch 1.926.348 x 8.192.004 multiplizieren, wenn Sie sich hinsetzen und es herausarbeiten.

Lange Multiplikation:

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

Tatsächlich gibt es einige schnellere Algorithmen zum Multiplizieren ( Wikipedia ), wie die schnelle Fourier-Methode von Strassen, und einige einfachere Methoden, die zusätzliche Addition und Subtraktion, aber weniger Multiplikation ausführen und so insgesamt schneller enden. Numerische Bibliotheken wie GMP können verschiedene Algorithmen basierend auf der Größe der Zahlen auswählen: Die Fourier-Transformation ist für die größten Zahlen nur die schnellste, kleinere Zahlen verwenden einfachere Algorithmen.

Die einfache Antwort ist, dass sie es nicht können, nicht alleine. Nimmt man das Konzept einer X-Bit-Maschine, so gibt es eine begrenzte Anzahl von Zahlen, die durch eine begrenzte Anzahl von Bits dargestellt werden können, genauso wie es eine begrenzte Anzahl von Zahlen gibt, die durch 2 Ziffern in dargestellt werden können das Dezimalsystem.

Davon abgesehen ist die Computerdarstellung von sehr großen Zahlen ein großer Bestandteil des Gebiets der Kryptographie. Es gibt viele Möglichkeiten, sehr große Zahlen in einem Computer darzustellen, von denen jede so unterschiedlich ist wie die andere.

Jede dieser Methoden hat unterschiedliche Vor- und Nachteile, und obwohl ich hier nicht alle Methoden auflisten kann / kann, werde ich eine sehr einfache vorstellen.

Angenommen, eine Ganzzahl kann nur Werte von 0 bis 99 enthalten. Wie könnte man die Zahl 100 darstellen? Das mag zunächst unmöglich erscheinen, aber das liegt daran, dass wir nur eine einzige Variable betrachten. Wenn ich eine ganze Zahl genannt hatte unitsund man rief hundreds, konnte ich leicht 100 darstellen: hundreds = 1; units = 0;. Ich könnte leicht eine größere Anzahl, wie 9223 darstellen: hundreds = 92; units = 23.

Obwohl dies eine einfache Methode ist, kann man argumentieren, dass sie sehr ineffizient ist. Wie die meisten Algorithmen, die die Grenzen dessen, was ein Computer kann, überschreiten, ist es normalerweise ein Tauziehen zwischen Leistung (repräsentieren große Zahlen) und Effizienz (schnelles Abrufen / Speichern). Wie ich bereits sagte, gibt es viele Möglichkeiten, große Zahlen in Computern darzustellen. finde einfach eine methode und experimentiere damit!

Ich hoffe das hat deine Frage beantwortet!

Weitere Lektüre:Dieser und dieser Artikel sind möglicherweise nützlich, um weitere Informationen zu erhalten.

Die Art und Weise, wie dies getan werden kann (es gibt viel schnellere Wege, die wiederholtes Quadrieren und dergleichen beinhalten), ist durch Multiplizieren und nach jeder Multiplikation den Modul zu nehmen. Solange das Quadrat des Moduls kleiner als 2 ^ 32 (oder 2 ^ 64) ist, wird dies niemals einen Überlauf haben.

So wie du es kannst.

Ich gehe davon aus, dass Sie nicht sofort wissen, was 342 * 189 ist. Aber Sie kennen die folgenden Fakten:

9 * 2 = 18
9 * 4 = 36
9 * 3 = 27
8 * 2 = 16
8 * 4 = 32
8 * 3 = 24
1 * 2 = 2
1 * 4 = 4
1 * 3 = 3

18 + 360 + 2700 + 160 + 3200 + 24000 + 200 + 4000 + 30000 = 64638

Wenn Sie diese einfachen Fakten kennen und eine Manipulationstechnik gelernt haben, können Sie rechnen, wie Sie es sonst nicht könnten.

Aus dem gleichen Grund kann ein Computer, der nicht mehr als 64 Bit Mathematik gleichzeitig verarbeiten kann, größere Probleme leicht in kleinere Teile aufteilen, diese kleineren Teile erledigen und sie wieder zusammensetzen, um die Antwort auf die größeren vorher zu bilden unbeantwortbares Problem.

In Bezug auf Addition und Subtraktion haben viele CPUs ein "Übertragsbit", das gesetzt wird, wenn die arithmetische Operation übergelaufen ist. Wenn das Speichern eines Ergebnisses 8 Bytes erfordert und die CPU 32 Bits umfasst (was 4 8-Bit-Bytes entspricht), kann sie zwei Additionsoperationen ausführen, zuerst für das "niedrige Wort" und dann für das "hohe Wort". mit dem Tragebit, das sich um den Überlauf kümmert. Das Übertragsbit muss zuerst gelöscht werden. Dies ist ein Grund, warum höhere Bit-CPUs die Leistung erhöhen, weil dies nicht so viel getan werden muss.

Das liegt natürlich an meiner begrenzten Assembler-Erfahrung mit 8-Bit-CPUs. Ich weiß nicht, wie das Übertragsbit bei modernen CPUs mit Multiplikations- und Divisionsbefehlen funktioniert. Nicht von Intel stammende RISC-CPUs können sich auch anders verhalten.

Ich weiß nicht viel über Gleitkomma-Mathematik, aber im Grunde genommen repräsentieren die Bytes eine feste Anzahl von Stellen, aber keine bestimmten Stellen. Deshalb wird es "Gleitkomma" genannt. So würde beispielsweise die Nummer 34459234 ungefähr den gleichen Speicherplatz belegen wie 3.4459234 oder 3.4459234E + 20 (das sind 3.4459234 x 10 ^ 20).