Wie führt ein 32-Bit-Betriebssystem den 2 ^ 56 modulo 7 aus?

Bei Arithmetik mit beliebiger Genauigkeit

Ein 32-Bit-Betriebssystem beschränkt Sie nicht auf benutzerdefinierte Typen, die diese Größe überschreiten. Ihre Anwendung kann zwei 32-Bit-Wörter aufnehmen und sie wie eine 64-Bit-Zahl behandeln. Die meisten Programmiersprachen haben sogar einen "Doppelwort" -Eintakttyp, um die Dinge zu vereinfachen.

Sie können das Konzept weiter erweitern, um einen beliebigen ganzzahligen Präzisionsdatentyp zu erstellen, der nur an den begrenzten Speicher gebunden ist. Im Wesentlichen haben Sie ein Array von Wörtern, und Sie speichern Ihre N -Bit-Nummern in den Bits der Wörter dieses Arrays.

Die Tatsache, dass es ein 32-Bit-Betriebssystem ist, beschränkt die numerische Berechnung, die Sie ausführen können, nicht. Ein Java long zum Beispiel ist ein 64-Bit Integraltyp, unabhängig davon, wo er gerade ausgeführt wird. Für eine willkürliche Genauigkeit erhöht java.math.BigInteger den Einsatz und liefert " unendliche Wortgröße "Abstraktion. Und ja, dieses "Feature" ist sogar in 32-Bit-Betriebssystemen verfügbar (weil das zu Beginn nie ein einschränkender Faktor war).

Siehe auch

• Wikipediia / Arbitrary-Genauigkeitarithmetik
• GNU MP BigNum-Bibliothek

In der Mathematik am Ring der ganzen Zahlen

Finden modularen multiplikativen inverse oder Modulare Potenzierung ist eine gängige mathematisch-algorithmische Aufgabe in den Bereichen der Kryptographie.

Eine Identität, die Sie hier verwenden möchten, ist die folgende:

Um x = 2 ⁵⁶ (Mod 7) zu finden, müssen Sie NICHT zuerst 2 ^{56 . Wenn Sie y = 2 55 (mod 7) - eine Zahl zwischen 0..6 - haben, finden Sie x = y * 2 (Mod 7).}

Aber wie findest du y = 2 ⁵⁵ (mod 7)? Nun, eine naive Methode ist, den Prozess linear anzuwenden und zuerst zu versuchen, z = 2 ⁵⁴ (mod 7) und so weiter zu finden. Dies ist eine lineare Potenzierung, aber Sie können es besser machen, indem Sie z. Potenzierung durch Quadrieren .

Das heißt, wenn Sie 2 ⁸ sagen, können Sie es quadrieren, um sofort 2 ¹⁶ zu erhalten. Sie können das dann quadrieren, um sofort 2 ³² zu erhalten.

Zusammenfassung

Es gibt viele ausgeklügelte mathematische Algorithmen, die für die Kryptographie anwendbar sind, und ob sie in einem Programm implementiert sind, das auf einem 32-Bit- oder einem 64-Bit-Betriebssystem läuft, ist nicht direkt relevant. Solange genügend Speicher verfügbar ist, ist der Computer mehr als in der Lage, Arithmetik mit beliebiger Genauigkeit auszuführen.

Gerade weil Arithmetik mit beliebiger Genauigkeit eine nützliche Abstraktion ist, sind viele Hochleistungsbibliotheken verfügbar, so dass Sie Ihre Anwendung auf einem bereits bestehenden Framework aufbauen können, anstatt von Grund auf neu zu bauen.

Einige Hochsprachen verfügen sogar über Arbitrary mit arithmetischer Arbitrary-Genauigkeit. Python zum Beispiel bietet eine beliebige Genauigkeit int und long auf Sprachenebene.

Sie werden feststellen, dass wir uns nie mit großen Zahlen beschäftigt haben (die größte war 56).

Außerdem:

Und damit auch 2**896 %7 = 4 , usw. (seit 896 = 4 * 224 , wo 224 = 4 * 56 ).

Für diese Art von Operation werden modulare Exponentierungsalgorithmen verwendet. Dieser Wikipedia-Artikel erzählt, wie es gemacht wird: Ссылка

Im Allgemeinen, wenn Sie wissen, dass Ihre Zahlen sehr groß werden, verwenden Sie eine Bibliothek wie GMP (Gnu Multi-Precision), um die Mathematik zu handhaben. Es tut, was Sie auf Papier tun würden, wenn Sie 2 ^ 32 Finger auf Ihren Händen hätten.

Welches System? Welche Architektur?

Im Allgemeinen erhalten Sie in einer 32-Bit-Architektur Überlaufergebnisse. Einige Sprachen haben eingebaute, beliebig große Zahlentypen, mit denen diese Berechnungen durchgeführt werden können. Beispiele hierfür sind BigDecimal in Java und das integrierte long int s in Python.

Man benutzt das (a * b) mod c = ((a mod c) * (b mod c)) mod c. Das bedeutet, dass Sie grundsätzlich

1. Beginnen Sie mit x = 1
2. Do x = (x * 2)% 7 56 mal

Ich denke, Ihre Terminologie ist ein wenig verwirrt.

Bei einem 32-Bit-Betriebssystem oder einer 32-Bit-Architektur sind die Maschinenadressen auf 32 Bit beschränkt. Es ist überhaupt nicht ungewöhnlich, dass eine 32-Bit-Architektur über arithmetische Anweisungen verfügt, die mit 64-Bit-Ganzzahlen und / oder 64-Bit-Gleitkommazahlen arbeiten.

Es ist also ziemlich wahrscheinlich, dass eine Maschine mit einer 32-Bit-Architektur (und einem 32-Bit-Betriebssystem) 64-Bit-Arithmetik verwendet und das Ergebnis als 64 Bit long oder long long unter Verwendung von 2 speichert aufeinanderfolgende 32-Bit-Wörter.